Построение эйлерова цикла

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

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

Перебор вариантов в задаче о гамильтоновом цикле (построить гамильтонов цикл или убедиться, что его не существует) можно организовать с помощью дерева путей. Это дерево представляет всевозможные простые пути в данном графе, начинающиеся в некоторой вершине а. Его вершины соответствуют вершинам графа, при этом каждая вершина графа может быть представлена в дереве несколько раз. Оно может быть построено следующим образом. Выберем в графе произвольно вершину а и объявим ее корнем дерева. Вершины, смежные с а, добавим к дереву в качестве сыновей вершины а. Для каждой вершины b, добавленной к дереву, рассмотрим все смежные с ней вершины и те из них, которые не лежат на пути (в дереве) из a в b, добавим к дереву в качестве сыновей вершины b. Процесс построения дерева заканчивается, когда к нему уже невозможно добавить новую вершину. Очевидно, что каждому пути в дереве, начинающемся в корне, соответствует точно такой же (простой) путь в графе, и обратно, каждому простому пути в графе с началом в вершине а соответствует такой же путь в дереве. Каждой вершине, находящейся в дереве на расстоянии от корня, соответствует гамильтонов путь в графе с началом в вершине а, а если последняя вершина этого пути смежна с а, то получаем гамильтонов цикл. Если высота дерева путей не превосходит , то в графе нет гамильтоновых путей, начинающихся в а, и нет гамильтоновых циклов. На рисунке 7 показаны граф и его дерево путей из вершины 1.

Рис. 7.

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

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

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

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

Орграф называется турниром, если для каждых двух вершин в нем имеется единственное ребро, соединяющее эти вершины.

Теорема о гамильтоновых путях в турнирах. В любом турнире имеется гамильтонов путь.

Для нахождения гамильтонова пути в турнире можно использовать следующее легко доказываемое свойство: если – ориентированный простой путь в турнире, y – вершина, не принадлежащая этому пути, то хотя бы одна из последовательностей , , …, тоже является ориентированным простым путем.

Аналогично обстоит дело с гамильтоновыми циклами в турнирах (см. задачу 5.25).