Page 49 - 4386

двочасткового графа K , з частками V ={v , v , …, v },
1
1
n n
n
2
V ={v n+1 , v n+2 , …, v }, n≥2, також існує гамільтоновий цикл
2
2n
v v v v …v v v v v .
n-1 2n-1 n 2n 1
1 n+1 2 n+2
Приклад 4.2. Знайти цикл Гамільтона, якщо він існує, для
графа G, зображеного на рис. 4.6 а.

а б

Рисунок 4.6

Розв'язок.

Граф G є зв'язним. Кількість вершин графа – n=6. Степінь

кожної з вершин дорівнює 3, тобто кожна з вершин графа

задовольняє умову δ(v)≥n/2. Отже, даний граф є гамільтоновим,

тобто існує цикл Гамільтона. Знайти його можна тільки методом

перебору. Результатом прямого перебору є цикл v v v v v v v
1 6 3 2 4 5 1
(рис. 4.6 б).

Практичне застосування циклів Гамільтона знаходимо в

рішенні класичної задачі комівояжера, яка цікава для людей, у

чиє коло обов'язків входить знаходження оптимальних шляхів,

наприклад, об'їзду філій фірми, транспортування вантажів,

доставки товарів і інше.

Задача комівояжера. Комівояжер повинен відвідати кілька

міст і повернутися у вихідний пункт. Відстані між містами відомі.

Необхідно знайти дорогу найкоротшої довжини. При такій

постановці задачі схема доріг являє граф, у якому будь-якому

48