На рис. 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 вершинами, не являющийся простой цепью, то граф Up(G) ─ Гамильтонов граф, для всех p ³ n ─ 3. Un(G) ─ итерированный реберный граф графа G.
Примеры, подтверждающие теорему 16.6, показаны на рис. 16.13. Как видно из рисунка начальный граф G удовлетворяет требованиям теоремы, т. е. не является простой цепью. Число вершин n графа G равно 6. Тогда p = 3 и следовательно, из всех двойственных графу G гамильтоновым явлется только граф Up(G) = U3(G). В то время как предшествующие ему графы U(G) и U2(G) не являются гамильтоновыми графами.
Процесс пострения двойственных графов аналогичен описанному выше алгоритму. В графе для которого строится двойственный граф на каждом ребре ставим точку, которая преобразуется в вершину двойственного графа. После того как таким образом определили все вершины двойственного графа, мы соединяем их между собой ребрами. Причем ребром в двойственном графе соединяются вершины, соответствующие ребрам, которые являются смежными в исходном графе. Так, например, ребро u 13 в графе G (рис. 16.13) смежно ребрам u 23 и u 34. Следовательно, вершина x 1,3 в двойственном графе U(G) будет соединена ребрами с вершинами x 2,3 и x 3,4. Аналогично каждое ребро (a, b, …, e) графа U(G) дает одну вершину двойственного ему графа U2(G), а каждое ребро (u 1, u 2, u 6) графа U2(G) преобразуется в вершину графа U3(G), который является уже гамильтоновым графом. Таким образом, мы получили практическое подтверждение справедливости теоеремы 16.6.
Рис. 16.13. Примеры нетривиальных и реберных графов
Приведем известные утверждения, упрощающие алгоритмы определения ГЦ.
Утверждение 16.1. Если граф G = (X, U) имеет ГЦ, тогда для всех xi Î X r (xi) ³ 2.
Утверждение 16.2. Если xi Î X и r (xi) = 2, тогда 2 ребра, инцидентные вершине xi, должны находиться в ГЦ, если он существует, для графа G.
Утверждение 16.3. Если xi Î X и r (xi) > 2 и при построении ГЦ мы уже прошли через вершину xi, то оставшиеся ребра, инцидентные xi, исключаются из дальнейшего рассмотрения. На рис 16.14 показан граф G из класса графов, не содержащих ГЦ.
Введем понятие жордановой кривой и приведем один из вариантов теоремы Жордана. Жордановой кривой на плоскости называется непрерывная кривая, не имеющая самопересечений. Соответственно замкнутой жордановой кривой называется жорданова кривая, начало и конец которой совпадают.
Теорема 16.7 (Жордана). Если L ─ замкнутая жорданова кривая, а xi, xj ─ две различные точки, расположенные на ней, то любая жорданова кривая, соединяющая xi и xj, должна лежать целиком внутри L или вне L (за исключением точек xi, xj), или пересекать L в некоторой точке, отличной от точек xi, xj.
Рис. 16.14. Пример графа, не содержащего Гамильтонов цикл
Если вершины графа G = (X, U) расположить так, чтобы ГЦ представлял собой самонепересекающуюся кривую, аналогичную замкнутой жордановой кривой, то ГЦ разделит плоскость на две области ─ внутреннюю и внешнюю. Естественно, что внутренняя и внешняя области взаимно обратимы. Вообще говоря, согласно теореме 2.7 любой простой цикл, расположенный на плоскости, разбивает ее на внешнюю и внутреннюю области. Причем, если имеются две вершины: xi (расположенная во внутренней области) и xj (расположенная во внешней области), то соединить их ребром без пересечения ребер цикла невозможно. Пример такого расположения вершин графа показан на рис. 16.15.
Здесь и далее под пересечением понимается соединение двух ребер графа в точке, не соответствующей никакой вершине. Если множество вершин графа G = (X, U) расположить на предполагаемой замкнутой самонепересекающейся кривой, то ребра, соединяющие соседние вершины графа, образуют гамильтонов псевдоцикл (ГПЦ), содержащий как ребра ui Î U, так и фиктивные ребра 
Ï U, которые на самом деле отсутствуют. Пример гамильтонова псевдоцикла показан на рис. 16.16.
Рис. 16.15. Построение жордановой кривой
Рис. 16.16. Гамильтонов псевдоцикл
Здесь Сгпц = {(x 1, x 2), (x 2, x 3), (x 3, x 4), (x 4, x 5), (x 5, x 6), (x 6, x 7), (x 7, x 8), (x 8, x 1)}, u 1 = (x 1, x 2), u 3 = (x 3, x 4), u 5 = (x 5, x 6), u 7 = (x 7, x 8) ─ существующие ребра, а фиктивными ребрами являются 
, 
, 
, 
. Очевидно, что полный граф всегда содержит ГЦ.
ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ
Пример 1. Привести примеры графов:
а) содержащих одновременно ЭЦ и ГЦ,
б) содержащих ГЦ и не содержащих ЭЦ,
в) содержащих ЭЦ и не содержащих ГЦ,
г) не содержащих ни ЭЦ и ГЦ.
На рис. 16.17 приведены примеры графов, соответствующих заданным в данном примере условиям. Для эйлеровых графов на рисунке стрелками показан порядок обхода ребер графа.
а б
в г
Рис. 16.17. Примеры эйлеровых и гамильтоновых графов
Пример 2. Для графа G = (X, U), заданного на рис. 16.17,в, построить ЭЦ, используя алгоритм Флери.
Решение: Из рисунка 16.17,в видно, что граф G ─ связный, поэтому переходим к алгоритму построения ЭЦ в графе.
1.1. Производим подсчет локальных степеней графа G. Все вершины имеют четные степени. Переходим к п. 1.2.
1.2. Выбираем вершину x 1.
1.3. Выбираем ребро u (x 1 – x 4). Здесь и далее в алгоритме примем следующее обозначение: u (x 1 – x 4) = u 14. Заносим его в список L и вычеркиваем из матрицы смежности R.
1.4. |L| ¹ m, где m ─ число ребер в графе G, переходим к п. 1.5.
1.5. Переходим к вершине x 4.
2.3. Выбираем ребро u 45.Заносим его в список L и вычеркиваем из матрицы смежности.
2.4. |L| ¹ m, переходим к п. 2.5.
2.5. Переходим к вершине x 5.
3.3. Выбираем ребро u 56 и заносим его в список L.
3.4. |L| ¹ m, переходим к п. 3.5.
3.5. Переходим к вершине x 6.
4.3. Выбираем ребро u 67 (ребро u 61 не выбираем, поскольку в данный момент имеется возможность выбрать другое ребро).
4.4. |L| ¹ m, переходим к п. 4.5.
4.5. Переходим к вершине x 7.
5.3. Выбираем ребро u 73. Заносим его в список L.
5.4. |L| ¹ m, переходим к п. 5.5.
5.5. Выбираем вершину x 3.
6.3. Выбираем ребро u 34, и заносим его в список L.
6.4. |L| ¹ m, переходим к п. 6.5.
6.5. Выбираем вершину x 4.
7.3. Выбираем ребро u 46, заносим его в список L.
7.4. |L| ¹ m, переходим к п. 7.5.
7.5. Выбираем вершину x 6.
8.3. Поскольку иных вариантов нет, выбираем ребро u 61.
8.4. |L| ¹ m, переходим к п. 8.5.
8.5. Выбираем вершину x 1.
9.3. Выбираем ребро u 12, заносим его в список L.
9.4. |L| ¹ m, переходим к п. 9.5.
9.5. Выбираем вершину x 2.
10.3. Выбираем ребро u 25, заносим его в список L.
10.4. |L| ¹ m, переходим к п. 10.5.
10.5. Выбираем вершину x 5.
11.3. Выбираем ребро u 58, заносим его в список L.
11.4. |L| ¹ m, переходим к п. 11.5.
11.5. Выбираем вершину x 8.
12.3. Выбираем ребро u 81, заносим его в список L.
12.4. |L| = m, переходим к п. 12.6.
12.6. Построен ЭЦ (u 14 – u 45 – u 56 – u 67 – u 73 – u 34 - u 46 – u 61 – u 12 – u 25 – u 58 – u 81).
Поставленная задача выполнена. Работа алгоритма закончена.
Пример 3. Привести пример гамильтонова графа и показать на нем порядок обхода вершин.
Решение: На рис. 16.18 показан граф G, в котором имеется гамильтонов цикл. Ребра, входящие в гамильтонов цикл, выделены жирной линией. Последовательность обхода вершин графа в гамильтоновом цикле может быть следующей: ГЦ = (x 1 ─ x 2 ─ x 15 ─ x 13 ─ x 18 ─ x 16 ─ x 14 ─ x 6 ─ x 7 ─ x 17 ─ x 20 ─ x 19 ─ x 11 ─ x 12 ─ x 3 ─ x 4 ─ x 10 ─ x 9 ─ x 8 ─ x 5 ─ x 1).
Рис. 16.18. Пример гамильтонова цикла в графе
ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ
1. Какой цикл в графе называется эйлеровым? Что такое полуэйлеров граф?
2. Какие условия существования эйлерова цикла в графе?
3. Что такое гамильтонов цикл в графе?
4. Существуют ли условия, позволяющие однозначно определить наличие гамильтонова цикла в произвольном связном графе?
5. В чем заключается основная идея алгоритма Флери?
6. Что такое граф подразбиений?
7. Какой граф называется тотальным?
8. В каком случае ребра и вершины графа называются соседними?
9. Поясните понятие жордановой кривой?
10. Что такое замкнутая жорданова кривая?
