Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

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

Читайте также:
  1. EQ С ВИЗУАЛЬНОЙ ОБРАТНОЙ СВЯЗЬЮ
  2. EQ с Визуальной Обратной связью
  3. Exersice II. Найдите соответствие между словосочетаниями в колонках А
  4. I Международный многожанровый фестиваль на острове Тасос (Греция)
  5. I. Стандарты Международного телекоммуникационного союза электросвязи - Сектор стандартизации (ITU-T)
  6. II. Поддержка и обеспечение взаимопомощи деятельности школ Международного Бакалавриата
  7. Japan Tobacco International (JTI) — международная табачная компания.

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


Дата добавления: 2015-10-26; просмотров: 388 | Нарушение авторских прав


Читайте в этой же книге: Для выбора «лучшего» алгоритма необходимо получение оценок или границ для объема памяти и времени работы ЭВМ, которое потребуется алгоритму для обработки конкретных данных. 4 страница | Графический способ. | Теорема о функциональной полноте | КРИТЕРИИ ОЦЕНКИ | Способы задания графов | Примеры РЕШЕНИЯ ЗАДАЧ | Маршруты, цепи, циклы | ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ | Алгоритм Форда | ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ |
<== предыдущая страница | следующая страница ==>
Эйлеровы и гамильтоновы цепи и циклы| ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

mybiblioteka.su - 2015-2024 год. (0.007 сек.)