ях НЕ є ейлеровім циклом, ВІН назівається власним ейлеровім путем.
Теорема (про ейлерів шлях). Граф має власний ейлерів шлях тоді и только тоді, коли ВІН зв'язного и Рівно две его вершини мают непарний степінь.
Так як граф для задачі про кенігсбергські мости має Чотири вершини з непарним ступенями, то можна сделать Висновок про том, что Сейчас граф НЕ має власного ейлерова шляху, а отже, Неможливо пройти КОЖЕН міст по одному разі, даже Якщо не нужно повертатіся у віхідну точку маршруту.
5.6 Шляхи и цикли Гамільтона
У 1857 году математик Вільям Роуен Гамільтон придумавши іграшку-головоломку. Ця іграшка являла собою додекаедр - правильний багатограннік, 12 граней которого? це правильні п'ятікутнікі. У шкірному з 20 кутів просвердлувалась дірка, у якові вставляли кілочок, что зображував місто. Помощью мотузки Було нужно найти шлях через міста, відвідав Кожне місто один раз, и вернуться у віхідне місто. Додекаедр на площіні зображується так, як показано на рис. 5.17.
Малюнок 5.17 - Зображення додекаедра на площіні
Завдання головоломки зводу до знаходження циклу в графі, что проходити через шкірні вершину, крім початкової, только один раз.
Визначення. Шляхом Гамільтона (або гамільтоновім Ланцюг) назівається простий ланцюг, что проходити через всі вершини графа, з качаном и кінцем у різніх вершинах.
Визначення. Цикл Гамільтона - це простий цикл, что проходити через всі вершини графа.
Гамільтонів цикл у Деяк змісті протилежних ейлерову циклу, что проходити через всі ребра один раз, хоча до Певного моменту обидвоє цикли могут здаватіся схожими. Цикл Гамільтона віявляється набагато складніше, и для его знаходження поки немає ефективних алгоритмів, что вімагають істотно меншого годині, чім Пряме перебирання варіантів. Проти пріведемо ряд теорем без доведення, что дозволяють нам судити про можлівість відшукаті гамільтонів цикл у досліджуваному графі. А для качана покажемо одна з варіантів решение головоломки, запропонованої Гамільтоном (рис. 5.18).
Малюнок 5.18 - Варіант розв язання головоломки Гамільтона
Теорема. Для будь-якої вершини Із циклу Гамільтона існує Рівно два ребра Із цього циклу, інцідентні даній вершіні.
Визначення. Граф, что має цикл Гамільтона, назівається гамільтонів.
Віходячі з наведення визначення, як наслідок теореми 6.5, робимо Висновок про том, что будь-який граф, что має вершину степені 1, що не є гамільтонів. Помітімо такоже, что для того, щоб граф МАВ цикл Гамільтона, необходимо, щоб ВІН БУВ зв'язного.
Приклад. Граф Петерсона, збережений на рис. 5.19, а, має шлях Гамільтона (рис. 5.19, б), но НЕ має цикл Гамільтона.
Малюнок 5.19 - Граф Петерсона
Теорема. Если граф має ребро розрізу, то ВІН НЕ может мати цикл Гамільтона. Если компоненти графа, отрімані путем відалення ребра розрізу, мают цикл Гамільтона, то граф має шлях Гамільтона.
Теорема. Если - зв'язного граф з вершинами и для кожної парі несуміжніх вершин, сума степенів вершин задовольняє умові, тоді граф має цикл Гамільтона.
Наслідок. Если - зв'язного граф з вершинами и для кожної вершини віконується Умова, то граф має цикл Гамільтона.
Приклад. Знайдіть цикл Гамільтона, если ВІН існує, для графа, збережений на рис. 5.20, а.
Малюнок 5.20 - Знаходження циклу Гамільтона
розв язання: Граф - зв'язного, Кількість вершин графа -. Степінь кожної з вершин дорівнює 3, тобто Кожна з вершин графа задовольняє умові. Отже, Сейчас граф є гамільтонів, тобто існує цикл Гамільтона. Знайте его Можемо только методом перебирання. Результати прямого перебирання - цикл (рис. 6.41, б).
Практичне! застосування ціклів Гамільтона знаходімо в рішенні класичної задачі комівояжера, яка цікава для людей, у чіє коло обов язків входити знаходження оптимальних Шляхів, например, про їзду філій фірми, транспортування вантажів, доставки товарів и інше.
Завдання комівояжера. Комівояжер винен відвідаті кілька міст и вернуться у вихідний пункт. Відстані между містамі відомі. Потрібно найти дорогу найкоротшої довжина. При такій постановці задачі схема доріг представляет собою граф, у Якій будь-якому ребру предложено Певна довжина. Завдання комівояжера зводу до знаходження в отриманий графі Із завданні довжина ребер циклу Гамільтона мінімальної довжина.
Існує ряд алгоритмів, й достатньо громіздкіх, что дозволяють знаходіті найкоротшій шлях від вершини до вершин...
