Page 47 - 4386
P. 47
Задача головоломки зводиться до знаходження циклу в
графі, що проходить через кожну вершину, крім початкової,
тільки один раз.
Шляхом Гамільтона (або гамільтоновим ланцюгом)
називається простий ланцюг, що проходить через усі вершини
графа, з початком і кінцем у різних вершинах v, w∈V.
Цикл Гамільтона - це простий цикл, що проходить через усі
вершини графа G. Граф, що має цикл Гамільтона, називається
гамільтоновим.
Так, на рис. 4.4 а, зображений граф Петерсона, що має
ланцюг Гамільтона (рис. 4.4 б), але не має циклу Гамільтона.
а б
Рисунок 4.4 – Граф Петерсона
Гамільтонів цикл у деякому змісті протилежний ейлеровому
циклу, що проходить через усі ребра один раз, хоча до певного
моменту обидва цикли можуть здаватися схожими. Цикл
Гамільтона виявляється набагато складніше і для його
знаходження поки що немає ефективних алгоритмів, що
потребують істотно меншого часу, чим пряме перебирання
варіантів.
Один з варіантів рішення головоломки, запропонованої
Гамільтоном наведений на (рис. 4.5).
46
