Гамільтонові цикли

Визначення. Гамільтонів цикл – це цикл, який проходить по кожній вершині графа і рівно один раз.

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

Незважаючи на подібність у формулюванні для ейлерових і гамільтонових циклів, відповідні теорії мають мало спільного. Критерій існування ейлеревих циклів був встановлений достатньо просто; для гамільтонових циклів ніякого загального правила невідомо. Більше того, для конкретних графів іноді тяжко встановити, чи існує взагалі такий цикл. Тому обмежимось одним критерієм.

Твердження. (Дірак). Якщо в графі G(V) з n вершинами для довільної вершини v Î V : r(v) ³ n / 2, то в графі існує гамільтонів цикл.

На закінчення зауважимо, що є різні задачі пошуку маршрутів у графі:

- з’ясування чи граф є ейлеревим та знаходження відповідного ейлеревого циклу

- знаходження найменшої кількості ланцюгів, які не мають спільних ребер та покривають увесь граф

- з’ясування чи граф є гамільтоновим

- знаходження маршрут, що зв’язує дві довільні задані вершини

- знайти найкоротший шлях з однієї заданої вершини в іншу задану вершину (зокрема для зважених графів)