Гамильтоновы графы. Достаточные условия существования гамильтонова цикла.

головоломка Уильяма Гамильтона о кругосветном путешествии, где требовалось обойти 20 вершин по развертке тетраэдра и вернуться в исходную точку (рис.3.26). В честь него цикл, содержащий все вершины графа ровно по одному разу, назвали гамильтоновым циклом, а граф, содержащий такой цикл, - гамильтоновым графом.

Рис. 3.26. Гамильтонов граф из головоломки «кругосветное путешествие».

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

Теорема Дирака. Любой граф G с не менее чем тремя вершинами (p ³3) и минимальной степенью вершины d (v)³ p /2 имеет гамильтонов цикл.

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

Теорема Оре. Если в графе G для любой пары вершин u,v выполняется условие r (u)+ r (v)³ p -1, то граф имеет гамильтонову цепь. Если r (u)+ r (v)³ p, то граф имеет гамильтонов цикл.

Ясно, что это достаточно жесткое условие, так как охватывает только графы с очень большим количеством ребер. В головоломке Гамильтона все вершины имеют степень 3, но гамильтонов цикл существует. Можете убедиться в этом сами.

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

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

Вспомним также, что такое k-связный граф. Число вершинной связности графа определяется, как минимальное число вершин, удаление которых приводит к увеличению количества компонент связности.

Теорема Татта. Каждый 4-х связный планарный граф имеет гамильтонов цикл.

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

Рис. 3.10. Граф с двумя точками сочленения, но без мостов.

15. Вершинная и реберная связность графа. Мосты, блоки, точки сочленения. Разделяющие множества и разрезы. Теорема Менгера в вершинной и реберной форме

v

Рис.3.8. Граф с точкой сочленения.

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

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

Справедлива следующая теорема, которую мы рассмотрим здесь без доказательства.

Пусть - v ₀ – точка сочленения связного графа G. Тогда (и только тогда) справедливы следующие утверждения.

1. Существуют две такие вершины u,v Î G, что любой путь между u и v проходит через вершину v ₀.

2. Существуют два такие подграфа G ₁ и G ₂, что путь из одного в другой проходит через вершину v ₀.

Теперь давайте рассмотрим граф на рис.3.9.

e

Рис.3.9. Граф с мостом.

u

v

Если в этом графе удалить ребро e, то граф тоже распадется на две компоненты связности. Ребро, удаление которого из графа приводит к увеличению числа компонент связности, называется мостом.

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

Во-первых, удаление ребра не может привести к образованию более чем двух новых компонент связности. Но при этом удаление любой из инцидентных ему вершин u или v приводит к удалению этого ребра. Следовательно, обе вершины, инцидентные мосту, являются точками сочленения. Но если бы в графе существовал цикл, проходящий через ребро e, то его удаление не привело бы к нарушению связности.

Свойства моста также можно сформулировать в виде теоремы.

Пусть в связном графе G ребро e является мостом. Тогда (и только тогда) справедливы следующие утверждения.

1. Существуют две такие вершины u,v Î G, что любой путь между u и v проходит через ребро e.

2. Существуют два такие подграфа G ₁ и G ₂, что путь из одного в другой проходит через ребро e.

3. Ребро e не принадлежит ни одному простому циклу.

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

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

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

Определение. Числом вершинной связности графа v(G) называют наименьшее число вершин, удаление которых приводит к образованию несвязного или тривиального графа.

Если граф не связен, то v(G)=0.

Если граф имеет точку сочленения, то v(G)=1.

Если v(G)=k, то граф называется k-связным.

Определение. Числом реберной связности графа l(G) называют наименьшее число ребер, удаление которых приводит к образованию несвязного или тривиального графа.

Если граф не связен, то l(G)=0.

Если граф имеет мост, то l(G)=1.

Рис.3.11. Схема просмотра вершин методом поиска в ширину.

A

B

C

G

K

M

H

E

L

D

F

Заметим, что l(K_p)=p-1.

Теорема. v(G)£ l(G)£ d(G), где d(G) – наименьшая степень вершины графа.

Доказательство начнем справа. Если в графе нет мостов, то чтобы разорвать такой граф, достаточно удалить все ребра, связывающие одну из его вершин с остальными. Наименьшее количество таких ребер как раз и равно наименьшей степени его вершин, то есть l(G)=min r(G)= d(G), что и означает l(G)£d(G). Но чтобы разорвать граф, в котором есть точка сочленения, достаточно удалить одну эту точку, то есть v(G)£ l(G).

Ясно, что v(G)=l(G), если в графе есть мост. А вот обратное неверно. Например, для графа на рис. 3.10 v(G)=1, но l(G)=3, так как минимальная степень вершины d(G)=3.

Теорема Менгера.

рассмотрим задачу. Менеджер фирмы, находящейся в городе A, собирается лететь на деловые переговоры в город F, с которым нет прямого воздушного сообщения. Учитывая плохие погодные условия, менеджер выписал для себя все возможные варианты перелетов с пересадками в городах В, С, D, E, G, H, K, L, M, в результате чего получился граф, представленный следующими списками смежности.

А: B,C,G,K,M; B: C,H; C: E,G,M; D: F,H,M; E: C,F,L; F: D,E,H,L,M; G: A,C,L; H: B,D,F,K; K: A,H,L; L: E,F,G,K; M: A,D,F.

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

Поставленное условие означает, что закрытые аэропорты – это вершины, удаление которых разбивает граф на две компоненты связности, причем пункты вылета и назначения находятся в разных компонентах.

Нужно ли для решения этой задачи тупо перебирать все возможные варианты перелета? Вот на этот вопрос, собственно, и отвечает теорема Менгера. Но прежде чем ее сформулировать, нам придется ввести еще несколько определений.

Определение. Пусть u,v – две несмежные вершины связного графа G (V, E). Две цепи S ₁(u, v), S ₂(u, v) называются вершинно непересекающимися, если они у них нет общих вершин, кроме u и v. Соответственно, цепи S ₁(u,v), S ₂(u,v) называются реберно непересекающимися, если у них нет общих ребер.

Говорят, что множество G ’(u,v)Ì G разделяет две вершины u,v, если эти вершины принадлежат разным компонентам связности G ₁Ì G, G ₂Ì G, где G ₁È G ₂È G ’= G.

Здесь, как и раньше, следует выделить два вида разделяющих множеств.

Определение. Разделяющим множеством вершин для пары u, v называется множество R (u,v)Ì V, такое, что u Î G ₁, vÎ G ₂, V ₁È V ₂È R = V, E ₁È E ₂È E ’= E, где E ’= E \(E ₁È E ₂). Соответственно, разделяющим множеством ребер называется P (u, v), такое, что u Î G ₁, v Î G ₂, V ₁È V ₂= V, E ₁È E ₂È E ’= E, где E ’= E \(E ₁È E ₂). Разделяющее множество ребер обычно называют разрезом.

Теорему Менгера сформулируем без доказательства, его можно посмотреть, например, в [1]. Эта теорема может быть сформулирована как в вершинной, так и в реберной форме.

Теорема Менгера в вершинной форме. Мощность наименьшего разделяющего множества вершин R (u, v) для пары вершин u и v равна максимальному количеству вершинно непересекающихся простых цепей S (u,v): min| R (u,v)|=max | S _v(u,v)|.

Теорема Менгера в реберной форме. Мощность наименьшего разреза P (u,v) для пары вершин u и v равна максимальному количеству реберно непересекающихся простых цепей S (u,v): min| P (u,v)|=max | S _e(u,v)|.

Поскольку мы уже видели, что вершинная связность понятие более «сильное», теорему Менгера чаще используют в вершинной форме. Однако реберная форма теоремы Менгера тоже имеет практическое значение.

Итак, для решения задачи про аэропорты нам не нужно перебирать все возможные варианты перелета. Достаточно найти максимальное количество вершинно непересекающихся простых цепей между пунктами A и F. Давайте попробуем это сделать.

Во-первых, заметим, что количество таких цепей не может быть больше, чем число вершин, смежных с вершиной A, и не может быть больше, чем число вершин, смежных с вершиной F. В противном случае цепи неизбежно будут пересекаться по вершинам. Итак, | S |<min(r(A),r(F))=5, и в данном случае обе эти вершины имеют максимальную степень. Для дальнейшего анализа можно воспользоваться схемой поиска в ширину, начиная с концевой вершины маршрута, имеющей минимальную степень. Для нашего случая схема поиска в ширину будет иметь следующий вид (рис.3.11).

В этой схеме уже имеется одна простая цепь (A,M,F). Еще три цепи получаем непосредственным переходом в F из смежных с ней вершин H,E,L. Из вершины К мы не можем непосредственно попасть в F, а все остальные вершины уже задействованы в цепях. Таким образом, в рассматриваемом графе существует 4 вершинно непересекающихся простых цепи. И этого достаточно, чтобы менеджер смог добраться на переговоры, так как при любых трех закрытых аэропортах у него всегда останется один запасной вариант.

 

26. Независимые и покрывающие множества вершин и ребер. Теорема Галаи.

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

Мы знаем, что при удалении вершины из графа вместе с ней уходят и все инцидентные ей ребра. Будем поэтому говорить, что вершина покрывает эти ребра. И, соответственно, будем говорить, что ребро ( i,j ) покрывает вершины i,j, если эти вершины являются его концами.

Определение. Множество вершин, покрывающее все ребра графа G, называется вершинным покрытием графа G. Аналогично, множество ребер, покрывающих все вершины графа G, называется реберным покрытием G.

Рис. 3.29. Графы с различными покрывающими множествами вершин и ребер.

Нетрудно заметить, что мощность вершинного покрытия в связном графе будет меньше числа вершин. Чтобы покрыть все ребра, нам понадобится тем больше вершин, чем меньше ребер покрывает каждая вершина. Больше всего вершин потребуется для покрытия простой цепи, где q = p- 1. А вот мощность реберного покрытия не всегда меньше числа ребер. На рис.3.29 показаны два графа с различными вершинными и реберными покрытиями. В цикле слева вершинное покрытие состоит из трех вершин (через одну), и реберное покрытие также состоит из трех ребер (через одно). В звезде справа вершинное покрытие состоит всего из одной центральной вершины, а реберное покрытие включает все ребра графа.

 

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

Введем обозначения: a₀ – мощность минимального вершинного покрытия (число вершинного покрытия), a₁ – мощность минимального реберного покрытия (число реберного покрытия).

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

Множество вершин называется независимым, если никакие две вершины в нем не смежны. Соответственно, множество ребер называется независимым, если в нем никакие два ребра не имеют общего конца. Мощность максимального независимого множества вершин в графе называется вершинным числом независимости и обозначается b₀. Мощность максимального независимого множества ребер называется реберным числом независимости и обозначается b₁.

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

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

Теорема Галаи. Для любого нетривиального связного графа справедливо следующее соотношение

a₀+b₀=a₁+b₁=p.