3.2. Гамильтоновы графы

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

Граф G называется гамильтоновым, если он имеет гамильтонов цикл.

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

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

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

Рис. 3.5. а - гамильтонов граф; б — негамнльтонов граф, имеющий гамильтонов путь.

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

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

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

Следующий результат получен в работе [3.1].

Теорема 3.4. Простой порядка , имеющий последовательность степеней является гамильтоновым, если

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

Докажем теорему от противного. Пусть существует простой негамильтонов граф, последовательность степеней которого удовлетворяет условию (3.1). Тогда он является остовным подграфом простого максимального негамнльтонова графа , в котором последовательность степеней также удовлетворяет условию (3.1).

Пусть — две такие несмежные вершины графа G, что сумма является по возможности наибольшей и Из того, что G — максимальный

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

Таким образом, в графе G существует гамильтонов путь где и к v — конечные вершины (рис. 3.6).

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

Рис. 3.6.

Так как вершина не принадлежит ни S, ни Т, из этого следует, что . Поэтому где обозначает число элементов множества X.

Так как то ни одна вершина не смежна с вершиной v. Из выбора следует, что для справедливо неравенство . Таким образом, существует по крайней мере вершин, степени которых не превышают . Поэтому если мы положим то получим у и, следовательно, по условию (3.1) k. Это означает, что существует по крайней мере вершин, степени которых не превышают Вершина и может быть смежна, самое большее, с k из вершин, так как Таким образом, существует вершина w с не смежная с вершиной . Но тогда , что противоречит выбору

В следующем следствии мы установим достаточные условия гамильтоновости графа, представленные в работах

Следствие 3.4.1. Простой граф порядка 3 с последовательностью сюпеней является гамильтоновым, если для него выполнено одно из следующих условий:

Доказательство. Докажем эти следствия, показав, что все эти условия влекут за собой выполнение

Очевидно, что любая последовательность степеней, удовлетворяющая условию 1, удовлетворяет также и условию 2.

Пусть из условия 2 не следует условие 3. Тогда существует такое что и . Теперь предположим, что существует, для которого

Тогда выражение противоречит условию 2.

Таким образом, подграф графа G, порожденный на множестве вершин является полным графом.

Так как каждая вершина будет смежной, самое большее, с одной вершиной Далее, из следует, что Таким образом, существует вершина не являющаяся смежной ни с одной

вершиной Поэтому Но тогда Таким образом, мы имеем , что противоречит условию 2.

. Если из условия 3 не следует условие 4, то существует такое что . Тогда . Если теперь мы положим то получим . Поэтому имеем неравенства, противоречащие условию (3.1). Если это не верно, то существует такое t, что Но тогда что противоречит условию 4.

Очевидно, если какая-либо графическая последовательность удовлетворяет условиям теоремы 3.4 или следствия 3.4.1, то тем же условиям удовлетворяет любая графическая последовательность, мажорирующая ее.

Условие Хватала — самое сильное из этих пяти условий и вообще из всех подобных условий. Это означает, что если какая-либо графическая последовательность не удовлетворяет условию Хватала, то она мажорируется последовательностью степеней негамильтонова графа [3.1].

Хотя в общем случае довольно трудно установить, является ли граф негамильтоновым, в определенных случаях это удается сделать с помощью изощренных методов.

Рис. 3.7. Негамильтонов граф.

Это иллюстрируется в работе [3,6] на следующем примере.

Рассмотрим граф G, представленный на рис. 3.7. Покажем, что он не содержит гамильтонова пути.

В гамильтонов путь можно включить не более двух ребер, инцидентных какой-либо вершине. В графе G вершина имеет степень 5, и, следовательно, по меньшей мере три ребра, инцидентных вершине не войдут в гамильтонов путь. То же самое справедливо и для вершин Так как степени вершин равны 3, то по крайней мере одно из ребер, инцидентных каждой из этих вершин, не будет включено в гамильтонов путь. Таким образом, в гамильтонов путь нельзя включить по крайней мере 13 из 27 ребер графа. Следовательно, чтобы составить гамильтонов путь на 16 вершинах графа G, ребер не достаточно. Поэтому граф G гамильтонова пути не содержит.

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

Следующая теорема полностью характеризует произвольно гамильтоновы графы. Доказательство ее можно найти в работе [3.7].

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

Закончим этот раздел рассмотрением задачи о коммивояжере. Она заключается в следующем:

Коммивояжеру необходимо посетить несколько городов. Какой маршрут он должен избрать, чтобы, начав двигаться из своего родного города, по одному разу побывать в каждом городе и затем вернуться домой по наикратчайшему пути?

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

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

Для более полного ознакомления с этой задачей можно использовать работы [3.8-3.11].