Связь между эйлеровыми и гамильтоновыми графами

На рис. 16.8 показан ряд классических графов. Причем на рис. 16.8,а – граф и эйлеров, и гамильтонов, на рис. 16.8,б – граф эйлеров, но не гамильтонов, на рис. 16.8,с – граф гамильтонов, но не эйлеров и на рис. 16.8,d – граф не эйлеров и не гамильтонов.

 

Рис. 16.8. Примеры эйлеровых и гамильтоновых графов

Теорема 16.3. Пусть G имеет n ³ 3 вершин. Если для всякого p, 1 £ p < (n-1)/2, число вершин со степенями, не превосходящими p, меньше чем p, и для нечетного n число вершин степени (n ─ 1)/2 не превосходит этого числа, то G ─ гамильтонов граф (ГГ).

Теорема 16.4. Если G ─ эйлеров граф, то граф U(G) = Gs ─ двойственный графу G является эйлеровым и гамильтоновым графом. Если G ─ гамильтонов граф, то Gs ─ также гамильтонов граф.

Можно привести контрпримеры обратным утверждениям. Так, например, граф G (рис. 16.9) является неэйлеровым, но гамильтоновым, а двойственный ему граф Gs является как эйлеровым, так и гамильтоновым графом.

  

Рис. 16.9. Примеры графов

Например, граф G ─ неэйлеров и негамильтонов граф, а граф Gs ─ неэйлеров и Гамильтонов граф Gs = G(U) = U(G) (рис. 16.10).

Рис. 16.10. Примеры графов

Если каждое ребро графа G подразбито путем введения дополнительной вершины, то граф G называется графом подразбиений и обозначается S(G) (рис. 16.11).

Рис. 16.11. Пример графа подразбиений

Теорема 16.5. Для того чтобы граф U(S(G)) был гамильтоновым графом, достаточно, чтобы G ─ был гамильтоновым графом, и необходимо, чтобы U(G) был гамильтоновым графом.

Тотальным графом T(G) называется граф, у которого множеством вершин является (X È U) и две вершины смежны, тогда и только тогда, когда они соседние в G. Вершины и ребра соседние, если они смежны и инцидентны. На рис. 16.12,а показан граф G, а на рис. 16.12,б его тотальный граф. Видно, что T(G) содержит в качестве порожденных подграфов G и U(G).

                                         а                      b

Рис. 16.12. Пример тотального графа

Теорема 16.6. Если G ─ нетривиальный связный граф с n вершинами, не являющийся простой цепью, то граф U^p(G) ─ Гамильтонов граф, для всех p ³ n ─ 3. Uⁿ(G) ─ итерированный реберный граф графа G.

Примеры, подтверждающие теорему 16.6, показаны на рис. 16.13. Как видно из рисунка начальный граф G удовлетворяет требованиям теоремы, т. е. не является простой цепью. Число вершин n графа G равно 6. Тогда p = 3 и следовательно, из всех двойственных графу G гамильтоновым явлется только граф U^p(G) = U³(G). В то время как предшествующие ему графы U(G) и U²(G) не являются гамильтоновыми графами.

Процесс пострения двойственных графов аналогичен описанному выше алгоритму. В графе для которого строится двойственный граф на каждом ребре ставим точку, которая преобразуется в вершину двойственного графа. После того как таким образом определили все вершины двойственного графа, мы соединяем их между собой ребрами. Причем ребром в двойственном графе соединяются вершины, соответствующие ребрам, которые являются смежными в исходном графе. Так, например, ребро u ₁₃ в графе G (рис. 16.13) смежно ребрам u ₂₃ и u ₃₄. Следовательно, вершина x _1,3 в двойственном графе U(G) будет соединена ребрами с вершинами x _2,3 и x _3,4. Аналогично каждое ребро (a, b, …, e) графа U(G) дает одну вершину двойственного ему графа U²(G), а каждое ребро (u ₁, u ₂, u ₆) графа U²(G) преобразуется в вершину графа U³(G), который является уже гамильтоновым графом. Таким образом, мы получили практическое подтверждение справедливости теоеремы 16.6.

Рис. 16.13. Примеры нетривиальных и реберных графов

Приведем известные утверждения, упрощающие алгоритмы определения ГЦ.

Утверждение 16.1. Если граф G = (X, U) имеет ГЦ, тогда для всех x_i Î X r (x_i) ³ 2.

Утверждение 16.2. Если x_i Î X и r (x_i) = 2, тогда 2 ребра, инцидентные вершине xi, должны находиться в ГЦ, если он существует, для графа G.

Утверждение 16.3. Если x_i Î X и r (x_i) > 2 и при построении ГЦ мы уже прошли через вершину x_i, то оставшиеся ребра, инцидентные x_i, исключаются из дальнейшего рассмотрения. На рис 16.14 показан граф G из класса графов, не содержащих ГЦ.

Введем понятие жордановой кривой и приведем один из вариантов теоремы Жордана. Жордановой кривой на плоскости называется непрерывная кривая, не имеющая самопересечений. Соответственно замкнутой жордановой кривой называется жорданова кривая, начало и конец которой совпадают.

Теорема 16.7 (Жордана). Если L ─ замкнутая жорданова кривая, а x_i, x_j ─ две различные точки, расположенные на ней, то любая жорданова кривая, соединяющая x_i и x_j, должна лежать целиком внутри L или вне L (за исключением точек x_i, x_j), или пересекать L в некоторой точке, отличной от точек x_i, x_j.

Рис. 16.14. Пример графа, не содержащего Гамильтонов цикл

Если вершины графа G = (X, U) расположить так, чтобы ГЦ представлял собой самонепересекающуюся кривую, аналогичную замкнутой жордановой кривой, то ГЦ разделит плоскость на две области ─ внутреннюю и внешнюю. Естественно, что внутренняя и внешняя области взаимно обратимы. Вообще говоря, согласно теореме 2.7 любой простой цикл, расположенный на плоскости, разбивает ее на внешнюю и внутреннюю области. Причем, если имеются две вершины: x_i (расположенная во внутренней области) и x_j (расположенная во внешней области), то соединить их ребром без пересечения ребер цикла невозможно. Пример такого расположения вершин графа показан на рис. 16.15.

Здесь и далее под пересечением понимается соединение двух ребер графа в точке, не соответствующей никакой вершине. Если множество вершин графа G = (X, U) расположить на предполагаемой замкнутой самонепересекающейся кривой, то ребра, соединяющие соседние вершины графа, образуют гамильтонов псевдоцикл (ГПЦ), содержащий как ребра u_i Î U, так и фиктивные ребра  Ï U, которые на самом деле отсутствуют. Пример гамильтонова псевдоцикла показан на рис. 16.16.

Рис. 16.15. Построение жордановой кривой

 

Рис. 16.16. Гамильтонов псевдоцикл

Здесь С_гпц = {(x ₁, x ₂), (x ₂, x ₃), (x ₃, x ₄), (x ₄, x ₅), (x ₅, x ₆), (x ₆, x ₇), (x ₇, x ₈), (x ₈, x ₁)}, u ₁ = (x ₁, x ₂), u ₃ = (x ₃, x ₄), u ₅ = (x ₅, x ₆), u ₇ = (x ₇, x ₈) ─ существующие ребра, а фиктивными ребрами являются , , , . Очевидно, что полный граф всегда содержит ГЦ.

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

Пример 1. Привести примеры графов:

а) содержащих одновременно ЭЦ и ГЦ,

б) содержащих ГЦ и не содержащих ЭЦ,

в) содержащих ЭЦ и не содержащих ГЦ,

г) не содержащих ни ЭЦ и ГЦ.

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

а                               б

в                               г

Рис. 16.17. Примеры эйлеровых и гамильтоновых графов

Пример 2. Для графа G = (X, U), заданного на рис. 16.17,в, построить ЭЦ, используя алгоритм Флери.

Решение: Из рисунка 16.17,в видно, что граф G ─ связный, поэтому переходим к алгоритму построения ЭЦ в графе.

1.1. Производим подсчет локальных степеней графа G. Все вершины имеют четные степени. Переходим к п. 1.2.

1.2. Выбираем вершину x ₁.

1.3. Выбираем ребро u (x ₁ – x ₄). Здесь и далее в алгоритме примем следующее обозначение: u (x ₁ – x ₄) = u ₁₄. Заносим его в список L и вычеркиваем из матрицы смежности R.

1.4. |L| ¹ m, где m ─ число ребер в графе G, переходим к п. 1.5.

1.5. Переходим к вершине x ₄.

2.3. Выбираем ребро u ₄₅.Заносим его в список L и вычеркиваем из матрицы смежности.

2.4. |L| ¹ m, переходим к п. 2.5.

2.5. Переходим к вершине x ₅.

3.3. Выбираем ребро u ₅₆ и заносим его в список L.

3.4. |L| ¹ m, переходим к п. 3.5.

3.5. Переходим к вершине x ₆.

4.3. Выбираем ребро u ₆₇ (ребро u ₆₁ не выбираем, поскольку в данный момент имеется возможность выбрать другое ребро).

4.4. |L| ¹ m, переходим к п. 4.5.

4.5. Переходим к вершине x ₇.

5.3. Выбираем ребро u ₇₃. Заносим его в список L.

5.4. |L| ¹ m, переходим к п. 5.5.

5.5. Выбираем вершину x ₃.

6.3. Выбираем ребро u ₃₄, и заносим его в список L.

6.4. |L| ¹ m, переходим к п. 6.5.

6.5. Выбираем вершину x ₄.

7.3. Выбираем ребро u ₄₆, заносим его в список L.

7.4. |L| ¹ m, переходим к п. 7.5.

7.5. Выбираем вершину x ₆.

8.3. Поскольку иных вариантов нет, выбираем ребро u ₆₁.

8.4. |L| ¹ m, переходим к п. 8.5.

8.5. Выбираем вершину x ₁.

9.3. Выбираем ребро u ₁₂, заносим его в список L.

9.4. |L| ¹ m, переходим к п. 9.5.

9.5. Выбираем вершину x ₂.

10.3. Выбираем ребро u ₂₅, заносим его в список L.

10.4. |L| ¹ m, переходим к п. 10.5.

10.5. Выбираем вершину x ₅.

11.3. Выбираем ребро u ₅₈, заносим его в список L.

11.4. |L| ¹ m, переходим к п. 11.5.

11.5. Выбираем вершину x ₈.

12.3. Выбираем ребро u ₈₁, заносим его в список L.

12.4. |L| = m, переходим к п. 12.6.

12.6. Построен ЭЦ (u ₁₄ – u ₄₅ – u ₅₆ – u ₆₇ – u ₇₃ – u ₃₄ - u ₄₆ – u ₆₁ – u ₁₂ – u ₂₅ – u ₅₈ – u ₈₁).

Поставленная задача выполнена. Работа алгоритма закончена.

Пример 3. Привести пример гамильтонова графа и показать на нем порядок обхода вершин.

Решение: На рис. 16.18 показан граф G, в котором имеется гамильтонов цикл. Ребра, входящие в гамильтонов цикл, выделены жирной линией. Последовательность обхода вершин графа в гамильтоновом цикле может быть следующей: ГЦ = (x ₁ ─ x ₂ ─ x ₁₅ ─ x ₁₃ ─ x ₁₈ ─ x ₁₆ ─ x ₁₄ ─ x ₆ ─ x ₇ ─ x ₁₇ ─ x ₂₀ ─ x ₁₉ ─ x ₁₁ ─ x ₁₂ ─ x ₃ ─ x ₄ ─ x ₁₀ ─ x ₉ ─ x ₈ ─ x ₅ ─ x ₁).

Рис. 16.18. Пример гамильтонова цикла в графе

ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ

1. Какой цикл в графе называется эйлеровым? Что такое полуэйлеров граф?

2. Какие условия существования эйлерова цикла в графе?

3. Что такое гамильтонов цикл в графе?

4. Существуют ли условия, позволяющие однозначно определить наличие гамильтонова цикла в произвольном связном графе?

5. В чем заключается основная идея алгоритма Флери?

6. Что такое граф подразбиений?

7. Какой граф называется тотальным?

8. В каком случае ребра и вершины графа называются соседними?

9. Поясните понятие жордановой кривой?

10. Что такое замкнутая жорданова кривая?