Page 70 - 4496

один раз і сумарна вага всіх ребер, що ввійшли в цикл,
мінімальна. Помітимо, що якщо граф є Ейлеровим, то будь-
який Ейлеровий цикл вирішує поставлену задачу (для
Ейлерова графа ваги ролі не грають).
Ця задача має багато додатків, наприклад, поливання
вулиць однією машиною (тут ребра графа - дороги, а
перехрестя - вершини; ваги - це довжини доріг), а також збір
сміття, доставка пошти або навіть найкращий маршрут для
огляду музею або збирання приміщень і коридорів у великих
установах.
Коротко розглянемо проблему, пов'язану з можливим
обходом всіх вершин у графі: чи існує в даному (зв'язаному)
графі цикл (або маршрут), що обходить кожну вершину (крім
першої) тільки один раз. Якщо такий цикл (маршрут) існує (у
цьому випадку такий цикл буде контуром, а маршрут –
шляхом), то граф називається гамільтоновим
(напівгамільтоновим), і відповідний цикл (шлях) також
називають гамільтоновим циклом (шляхом).
На рис. 3.5 зображені гамільтонів, напівгамільтонов і не
гамільтонів графи.

а) б) в)

Рисунок 3.5 - Гамільтонів, напівгамільтонов і не
гамільтонів графи

Незважаючи на подібність постановки задач для
гамільтонових графів з Ейлеровими, задовільного рішення для
гамільтонових графів немає. Взагалі, про гамільтонові графи
відомо дуже мало.
Приведемо без доказу найвідомішу теорему.

67