ОПРЕДЕЛЕНИЕ. Цикл в некотором графе называется циклом Гамильтона, если он содержит все вершины этого графа по одному разу

Цикл в некотором графе называется циклом Гамильтона, если он содержит все вершины этого графа по одному разу.

То есть любые две вершины цикла Гамильтона, одна из которых является внутренней вершиной цикла, - разные.

Исторически понятие такого цикла относится к головоломке, предложенной в 1859 году Уильямом Гамильтоном. Она называлась задачей о кругосветном путешествии.

В этой задаче предлагалось составить план проезда по странам, имеющим общие границы, так, чтобы побывать в каждой стране ровно по одному разу и вернуться в исходную страну. Данная задача является задачей нахождения циклов Гамильтона в графах, соответствующих географическим картам. Каждой такой карте можно поставить в соответствие граф, вершины которого представляют отдельные государства, а ребра указывают на наличие общей границы между парами государств.

В общем случае граф может не иметь циклов Гамильтона. Например, граф G ₁, изображенный на рис. 5.20 не имеет таких циклов, так как вершина v при всяком прохождении по всем вершинам этого графа должна проходиться не менее двух раз. Граф G ₂ имеет цикл Гамильтона. Такой цикл представлен ребрами, изображенными более толстыми линиями.

v

G ₁ G ₂

Рис. 5.20

Вершина v графа G называется разделяющей, если удаление из G вершины v вместе с соответствующими ей ребрами разбивает граф на несколько компонент связности.

Упражнение. Показать, что если связный граф G имеет разделяющую вершину, то G не имеет цикла Гамильтона.

Практически важная задача, приводящая к поиску циклов, близких по свойствам к циклам Гамильтона, носит название задачи коммивояжёра.

В этой задаче требуется определить такой маршрут движения торговца между населенными пунктами (магазинами), чтобы торговец побывал в каждом пункте, вернулся в начало пути, и суммарная длина пройденного пути оказалась минимальной.

Разновидностью приведенной задачи является задача нахождения цикла Гамильтона.

Для нахождения циклов Гамильтона в произвольных графах можно воспользоваться процедурой перебора вариантов. Для произвольно заданного графа G, имеющего n вершин, достаточно организовать последовательную проверку всех перестановок вершин этого графа. Каждая такая перестановка дополняется вершиной, равной её первому элементу, после чего проверяется свойство полученной последовательности вершин быть циклом Гамильтона в G.

Практическая применимость такого переборного метода сомнительна, поскольку число перестановок вершин, равное n!, уже для небольших по размерам графов является слишком большим.

Замечание. Для циклов Гамильтона, в отличие от циклов Эйлера, неизвестны непереборные алгоритмы нахождения таких циклов в произвольных графах. Более того, существующая теория решения комбинаторных задач относит задачу отыскания таких циклов в графах к классу наиболее длительных по времени решения задач.

Поэтому рассмотрение задачи нахождения циклов Гамильтона в графах естественно ограничить рассмотрением отдельных классов графов, для которых могут быть получены простые по сложности проверки условия существования таких циклов.

В качестве примера рассмотрим одно простое достаточное условие существования циклов Гамильтона для графов без петель, основанное на специальном свойстве степеней вершин таких графов.

Пусть G = (V, U) - некоторый граф без петель и V = { a ₁,..., a_n }. Будем считать, что n 3.