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

На рис. 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 (x_i)  2.

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

Утверждение 16.3. Если x_i  X и (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₈) ─ существующие ребра, а фиктивными ребрами являются , , , . Очевидно, что полный граф всегда содержит ГЦ.