Понятие гамильтонова графа очень близко к понятию эйлерова графа, но между ними пропасть, как вскоре выяснится!
ОПРЕДЕЛЕНИЕ 28.Цикл в графе называется гамильтоновым, если каждая вершина графа (кроме начальной) входит в него один раз. (Гамильтонов цикл по определению является простым!) Граф называется гамильтоновым, если в нем существует гамильтонов цикл. Не замкнутый путь в графе называется гамильтоновым, если каждая дуга графа входит в него один раз. Граф называется полугамильтоновым, если в нем существует гамильтонов путь.
Понятия эйлерова и гамильтонова графа независимы: для любой комбинации свойств «эйлеров – не эйлеров», «гамильтонов – не гамильтонов» найдется соответствующий граф! Попробуйте их построить.
В отличие от эйлеровости критерий гамильтоновости неизвестен, да и вряд ли простой критерий существует! Известны некоторые необходимые и некоторые достаточные условия. Докажем одно из достаточных условий.
Теорема 21(Дирак). Неориентированный граф с p вершинами, степени всех вершин которого не менее p/2, гамильтонов.
Пример цикла показывает, что необходимым условие теоремы не является.
Доказательство. Пусть существует граф Г, для которого утверждение нарушается. Поскольку полный граф очевидно является гамильтоновым, то граф Г неполный. Будем добавлять в него дуги, пока он не станет гамильтоновым. Степени вершин при этом могут только вырасти. В полученном гамильтоновом цикле удалим последнюю добавленную дугу, тем самым получим гамильтонову цепь. Занумеруем вершины графа в порядке прохождения вдоль этой цепи от 1 до p. Окрасим в красный цвет вершины, смежные с первой вершиной, и в синий – вершины предшествующие красным. Красных вершин (а тогда и синих) по условию не менее p/2. Значит, вершин, не окрашенных в синий цвет, меньше p/2. Поскольку степень p-й вершины не менее p/2, то существует синяя вершина, смежная с p-й (пусть ее номер k), при этом по построению (k+1)-я вершина смежна с первой. Цикл 1-2-…-k-p-(p-1)-…-(k+1)-1 гамильтонов, что противоречит предположению. При построении цикла использована неориентированность графа.
Проверка гамильтоновости графа и построение гамильтонова цикла в общем случае задача трудоемкая. Для этого применяются различные методы направленного перебора, наиболее распространенным из которых является поиск с возвращением. Суть этого метода состоит в том, что строится простая цепь, пока это возможно. При невозможности дальнейшего построения делается шаг назад, выбирается следующая вершина
Этот метод применим к широкому спектру задач. Полезно, например, рассмотреть задачу о расстановке на доске 6´6 шести ферзей таким образом, чтобы они не били друг друга.
К задаче о построении гамильтоновых циклов примыкает, возможно, самая известная задача комбинаторной оптимизации – задача коммивояжера(в русскоязычной литературе ее иногда называют задачей о бродячем торговце). Пусть есть сеть пунктов, где коммивояжеру необходимо побывать со своим товаром, причем по окончании надо вернуться домой. При этом известны расстояния между всеми парами пунктов (если проезд есть). Естественно, при этом маршрут коммивояжера должен быть кратчайшим. На языке теории графов необходимо найти гамильтонов цикл минимальной длины. Здесь также применим поиск с возвращением, который в этом случае называется методом ветвей и границ. Это название отражает то обстоятельство, что если один гамильтонов цикл уже построен, то его длина становится границей, переступать за которую нецелесообразно: если вес части пути превосходит границу, то надо делать шаг назад. Таким образом, если быстро получим гамильтонов цикл с длиной, близкой к минимальной, то это позволит ускорить поиск.