3.4. Гамильтоновы цепи и циклы

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

Если граф обладает гамильтоновым циклом 5, то, очевидно, он обладает и гамильтоновой цепью. Обратное, вообще говоря, неверно. Так, например, двудольный граф на рис. 3.5 обладает несколькими гамильтоновыми цепями, но не обладает гамильтоновым циклом. И, конечно, многие графы не содержат ни того, ни другого. Для некоторых специальных классов конечных графов факт существования или отсутствия гамильтоновой цепи или цикла легко устанавливается. Например, дерево не может содержать гамильтоновой цепи, если оно само не является цепью. (Докажите это!) Аналогично, рис. 3.5 иллюстрирует общий факт, что двудольный граф, имеющий нечетное число вершин, не содержит гамильтонового цикла. (Каждый простой цикл в двудольном графе имеет четное число ребер и, следовательно, содержит четное число вершин.) С другой стороны, каждый полный граф, очевидно, содержит множество гамильтоновых ццклов,

Рис. 3.5,

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

Знаменитый математик Гамильтон придумал в свое время деловую игру, цель которой состояла в нахождении гамильтоиова цикла в графе, определенном вершинами и ребрами заданного многогранника. Описание ее можно найти в работе [20] (библ. к гл. 1).

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

Упражнения

(см. скан)

(см. скан)

Вернемся теперь к очень интересной теме, связанной с понятием гамильтоновых циклоз. Неориентированный граф является гипогамильтоновым для краткости), если, он не имеет гамильтонового цикла, но каждый его подграф, имеющий на 1 меньший порядок, содержит такой цикл [8]. Задача состоит в том, чтобы найти НН-граф минимального порядка и показать, что найденное. решение единственно. Будем предполагать, что искомый граф имеет вершин и ребер и является обыкновенным.

Лемма 3.9. Если является НН-графом, то

Лемма 3.10. Если является НН-графом, то для каждой вершины

Доказательство. Каждая вершина принадлежит простому циклу длины следовательно, Если смежна с и, то в подграфе, полученном удалением мы тоже имеем Таким образом

Лемма 3.11. Если является НН-графом и если и х—последовательные вершины простого цикла длины в графе, в котором вершина удалена, то не смежна ни с и, ни с х.

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

Лемма 3.12. Если является НН-графом, то для каждой

Доказательство. Утверждение непосредственно следует из леммы 3.11.

Лемма 3.13. Если является однородным графом со степенью вершин то

Лемма 3.14. Если — различные вершины графа такие, что смежна с до и до и смежны с х, и если и два ребра одного и того же гамильтоиова цикла в графе, полученном удалением то граф содержит гамильтоиов цикл.

Доказательство. Искомый цикл показан на рис. 3.8.

Теорема 3.15. Если является НН-графом, то

Доказательство. Утверждение следует из лемм 3.10 и 3.12.

Теорема 3.16. Если является НН-графом, то Доказательство. Из лемм 3.10 и 3.12 следует, что при имеет место для каждой а это противоречит лемме 3.13.

Рис. 3.8.

Рис. 3.9 и 3.10.

Теорема 3.17. Если является НН-графом, то Доказательство. Из лемм 3.10 и 3.12 следует, при имеет место Если является

НН-графом порядка 8, то по лемме 3.11 он является одним из двух графов, приведенных на рис. 3.9 и 3.10, каждый из которых имеет гамильтоиов цикл в соответствии с леммой 3.14.

Теорема 3.18. Если является НН-графом, то

Доказательство. По лемме 3.13, если является НН-графом порядка 9, то он не может быть однородным графом степени 3, а по лемме 3.12 он имеет, но крайней мере, одну вершину степени 4. Из леммы 3.11 следует, что часть вершин и ребер образуют граф, показанный на рис. 3.11. При этом вершина 2 должна быть смежной, по крайней мере, с одной из вершин тая как Но каждое из ребер 2—4, 2—6 и 2—8 приводит к гамильтонову циклу (по лемме 3.14). Поэтому, если вершина 2 смежна с вершиной 5, то вершина 8, которая по той же причине не может быть смежна ни с какой вершиной, кроме, вершин 3 и 5, не смежна с 5, так как в противном случае всегда что противоречит лемме 3.12. Таким образом, вершина 8 смежна с вершиной 3. Аналогично, вершина 6 смежна с вершиной 1, а вершина 4 с вершиной 7. Граф не может иметь других ребер, так как вершины 9, 1, 3, 5, 7 насыщены.

Ту же картину можно было бы получить (рис. 3.12), если вершина 2 оказалась смежна с вершиной 7. Заметим, что каждое ребро соединяет две вершины, номера которых имеют разную четность. Таким образом, граф, полученный из удалением вершины не имеет гамильтоиова цикла, и, следовательно, не может быть НН-графом.

Теорема 3.19. Если является НН-графом порядка 10, то он является однородным степени 3.

Доказательство. Пусть некоторая вершина имеет степень 4, тогда содержит в качестве своей части граф, показанный на рис. 3.13. По лемме 3.14 каждая вершин 2, 4, 5, 7, 9 не может быть смежна с одной вершиной, кроме одной или двух вершин из набора 1, 3, 6, 8. Так как каждая из последних вершин не может быть смежна ни с какой другой, кроме, еамое большое, с одной из вершин первого набора, то мы получаем противоречие.

Теорема 3.20. Граф рис. 3.14 является НН-графом.

Доказательство. Удаляя вершину мы получим цикл а удаляя вершину 2, получаем цикл (10, 1, 9, 8, 3, 4, 5, 6, 7, 10).

Рис.

Рис. 3.12.

Рис. 3.13.

Рис. 3.14.

Другие случаи получаются симметрично. Таким образом, исходный граф не содержит гамильтоиова цикла, Последовательность вершин (10, 1 и 2) является началом максимальных простых цепей (6, 5, 4, 3, 8, 7), (6, 5, 4, 3, 8, 9), (6, 5, 9, 8, 3, 4), (6, 5, 9, 8. 7), (6, 7, 8, 3, 4, 5, 9), (6, 7, 8, 9, 5, 4, 3), (3, 4, 5, 6, 7, 8, 9), (3, 4, 5, 9, 8, 7, 6), (3, 8, 7, 6, 5, 4), (3, 8, 7, 6, 5, 9), (3, 8, 9, 5, 4), (3, 8, 9, 5, 6, 7) и ни одна из них не образует гамильтоиова цикла. В силу симметрии то же самое справедливо для всех других цепей.

Теорема 3.21. Если является НН-графом порядка 10, то он изоморфен графу теоремы 3.20.

Доказательство. Перенумеруем вершины цикла в графе. В зависимости от положения вершины 10 получим три возможных типа графа

1. Граф, в котором вершина 10 смежна с вершинами 1, 4,7 и который по лемме 3.14 и теореме 3.19 дает граф рис. 3.13 или граф рис. 3.15. Но последний имеет гамильтоиов цикл (10, 1, 2, 9, 8, 7, 6, 5, 4, о, 4, 10).

2. Граф, в котором вершина 10 смежна с вершинами и который приводит к графу рис. 3.16, имеющему гамильтоиов цикл (10, 6, 7, 5, 4, 3, 2, 8, 9, 1, 10).

Рис. 3.15.

Рис. 3.16.

Рис. 3.17.

Рис.

3. Граф, в котором вершина 10 смежна с вершинами 1, 3, 5 и который приводит к графам, показанным на рис. 3.17 и 3.18, имеющим соответственно гамильтоповы циклы (10, 1, 2, 3, 4, 7, 8,9,6, 5,10) и (10,1,2,7,8,9,6, 5, 4, 3, 10).

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

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

Если мы не требуем возвращения в начальную вершину (т. е. ищем гамильтоиов путь), то задача несколько упрощается. Кёниг доказал, что каждый антисимметрический полный граф содержит, по крайней мере, один гамильтоиов путь. (Доказательство см. на стр. 30 и 31 у Кёнига в книге [16] библ. к главе 1.) Редей [12] показал, что на самом деле в таком графе существует нечетное число гамильтоновых путей. Камьон [2], исследуя единственность, получил следующую теорему.

Теорема 3.22. Антисимметрический полный граф содержит единственный гамильтоиов путь тогда и только тогда, когда он не содержит контуров.

Доказательство. Если содержит два различных гамильтоновых пути, то они определяют две

перестановки вершин и отличаются, по крайней мере, одной инверсией. Следовательно, существуют две вершины, каждая из которых соединяется с другой путем. Это означает существование контура. С другой стороны, если контур существует, то способ построения, предложенный Кёнигом и описанный в его книге [16, библ. к гл. 1], отмеченной выше, приводит к различным гамильтоновым путям.

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

Теорема 3.23. Необходимым и достаточным условием того, что ориентированный граф без контуров содержит в точности один гамильтонов путь, является тотальность графа.

Интересной задачей, связанной с поиском кратчайшего гамнльтонова контура, является задача коммивояжера. Коммивояжер должен посетить по одному разу каждый из городов (каждая пара городов связана дорогой) и вернуться в исходный город. При этом он должен выбрать кратчайший маршрут. Очевидно, что определение кратчайшего маршрута с помощью просмотра всех гамильтоновых циклов приводит к перебору возможных циклов, а эта величина является астрономической для больших Необходимо найти эффективный алгоритм решения этой задачи. Заметим, что такого алгоритма до сих пор не существует. Вычислительные алгоритмы, предложенные для решения задачи коммивояжера, приведены в работах [3, 7, 9].

(см. скан)

(см. скан)

Интересно заметить, что кратчайший замкнутый маршрут, связывающий точек на плоскости в случае, если не все точки находятся на одной прямой, является замкнутой ломаной с непересекающимися сторонами. В частности, если выпуклая оболочка множества не содержит ни одной из точек внутри себя, то ее граница является кратчайшим замкнутым маршрутом. (Таким образом, в соответствующей задаче коммивояжера не будет каких-либо пересечений маршрутов.) Чтобы доказать это [15], соединим точек любым замкнутым путем и заметим, что более короткий путь получается при соединении точек в том же самом порядке отрезками прямых линий. (Рассматриваемые точки соответствуют вершинам.) Если отрезки пересекаются в точке то мы полагаем, что выбран следующий путь Если не совпадает ни с одной из заданных точек, то образует более короткий кусочно-линейный путь, который не содержит пересечения Если же принадлежит заданному множеству точек, то образует кусочно-линейный путь, который не содержит в качестве точки пересечения. (Смысл сказанного удобно пояснить с помощью рисунка).

Рассмотрим интересный и простой подход к решению задачи коммивояжера, предложенный П. С. Райяном (Р. С. Ryan), сотрудником Лаборатории военно-морских исследований. Этот подход не более эффективен, чем другие, однако он способствует несколько более глубокому пониманию существа вопроса.

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

Предлагаемый алгоритм за конечное число шагов находит кратчайший гамильтоиов цикл или устанавливает его отсутствие.

Будем предполагать, что рассматриваемый граф является плоским и обыкновенный плоский граф имеет, по крайней мере, одну вершину степени 5 или меньше (факт, установленный в главе 4). Кроме того, предполагается также, что длины ребер выражаются положительными числами.

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

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

1. , если Случай является единственным исключением, оговоренным выше.

2. не разделяет оставшийся граф в том смысле, что любые две вершины могут быть связаны цепью из ребер, не инцидентных ни одной вершине

Условия 1 и 2 гарантируют, что полученная цепь является простым циклом. Возможно, на некотором шаге несколько ребер могут удовлетворять условиям добавления к цепи в одной и той же вершине. В этом случае выбирается ребро наименьшей длины, а остальные ребра запоминаются. Позднее должно быть проверено каждое из оставшихся ребер.

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

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

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

Поясним метод на примере графа рис. 3.19. Целые числа обозначают длины ребер. На рис. и с показаны три подграфа, полученных при определенном выборе и соответствующих значений

На рис. 3.21 показана последовательность шагов, требуемых для построения первого гамильтоиова цикла

Рис. 3.19.

в Ребра, показанные жирными линиями, являются ребрами цикла. Условие 2 исходного метода эквивалентно требованию того, чтобы граф, получаемый из удалением жирных и пунктирных ребер и обведенных жирными кружками вершин (на каждом шаге), был связным.

Рис. 3.20.

Числа в круглых скобках у вершин означают число ребер (отмеченных), оставшихся для исследования в данной вершине.

Рис. 3.21.

Возвращаясь к рассмотрению альтернатив на шаге 2 (см. выше), получим картину, показанную на рис. 3.22.

Рис. 3 22.

Заметим, что ребро длины 5 не является допустимой альтернативой на шаге 2 (рис. 3.22), ибо мы уже

(кликните для просмотра скана)

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

Рис. 3.23 и 3.24 поясняют шаги, необходимые для полного рассмотрения графов Заметим, что неиспользованная альтернатива на второй картинке рис. 3.23 отбрасывается (ввиду ограничения на длину цепи) после того, как найден гамильтоиов цикл длины 10 (см. рис. 3.23).

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

(см. скан)