Гамильтонов граф

Гамильтоновы графы

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

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

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

Легко найти тэта-подграф в негамильтоновом блоке, приведенном на рисунке

Гамильтонов граф

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

Теорема .Пусть G имеет р > 3 вершин. Если для всякого n, 1

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

Покажем сначала, что всякая вершина, степень которой не меньше (р—1)/2, смежна с каждой вершиной со степенью, большей чем (р—1)/2. Допустим (не теряя общности), что deg v1> (р-1)/2 и deg vp>p/2, но вершины v1 и vp не смежны. Тогда существует простая остовная цепь v1v2. vp, соединяющая v1 и vp. Обозначим вершины смежные с v1 через vi1. vin, где n-deg v1 и 2=i1< in Ясно, что вершина vp не может быть смежной ни с одной вершиной из G вида vt-i, поскольку тогда в G был бы гамильтонов цикл

v1v2. vij-ivpvp-1. vijv1

Далее, так как п>(р-1)/2, то р/2

Отсюда следует, что если degv>p/2 для всех вершин v, то G — гамильтонов граф. (Ниже это сформулировано в виде следствия (б).) В силу изложенного выше каждая пара вершин графа G смежна, т. е. G — полный граф. Мы пришли к противоречию, поскольку Кр — гамильтонов граф для всех р>3.

Таким образом, в G есть вершина v с degv

vp. Как и выше, обозначим через vi. vim вершины графа G, смежные с v1 и заметим, что вершина vр не может быть смежной ни с одной из т вершин vij —1 для 1< j

Приведенное достаточное условие не является необходимым. Кубический граф G1 изображенный на рисунке, гамильтонов, хотя ясно, что он не удовлетворяет условиям теоремы. Однако условия теоремы неулучшаемы, поскольку при их ослаблении новое условие уже не будет достаточным для гамильтоновости графа. Например, выберем р>3 и 1 < n< (р—1)/2 и образуем граф G2 с одной точкой сочленения и двумя блоками Kn+1 и Кp-nЭтот граф не гамильтонов; для него нарушается только одно условие теоремы: граф G2 содержит точноnвершин степени п. Это иллюстрируется на рисунке где р=8 и п=3. Если выбрать р=2n+1,

n> 1 и образовать граф G = Kn, n+1> то он не будет гамильтоновым; для него нарушается только одно условие теоремы: в нем (р—1)/2+1 вершин имеют степень (р—1)/2. Граф G3 = K2,3, приведенный на рисунке, иллюстрирует это для случая р=5.

Ограничивая условия теоремы Поша, получаем более простые, но менее сильные достаточные условия, найденные Оре и Дираком соответственно:

Следствие (а).Если р>3 и degu + degv> р для любой парыuи v несмежных вершин графа G, то G — гамильтонов граф.

Гамильтонов граф

Следствие (6).Если р>3 и deg v> р/2 для любой вершины v графа G, то G — гамильтонов граф.

Кубический гамильтонов граф G1 показанный на рисунке, имеет четыре остовных простых цикла. Наименьший кубический гамильтонов граф К4 имеет три остовных простых цикла. Эти замечания иллюстрируют теорему Смита

Теорема .В каждом кубическом гамильтоновом графе существует по крайней мере три остовных простых цикла .

Тейт высказал предположение, что каждый плоский трехсвязный граф содержит остовный простой цикл. Татт показал, что это не верно, приведя пример плоского трехсвязного графа с 46 вершинами, не являющегося гамильтоновым

Гамильтонов граф

Наименьший известный в настоящее время негамильтонов трехсвязный плоский граф, имеющий 38 вершин, был построен независимо Ледербергом, Босаком и Барнеттом; эти результаты можно найти в монографии Грюнбаума .

Гамильтонов граф

Кажущееся отсутствие взаимосвязи между эйлеровыми и гамильтоновыми графами иллюстрируется рис; здесь каждый

граф — это блок с 8 вершинами. Однако в следующей главе мы свяжем эйлеровы и гамильтоновы графы с помощью так называемых «реберных графов».

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

Гамильтоновы графы

В 1857 году ирландский математик предложил У. Гамильтон предложил игру, названную «Кругосветное путешествие/путешествие по додекаэдру». Игра сводилась к обходу по рёбрам по рёбрам всех вершин правильного додекаэдра, при условии, что нужно обойти все вершины ровно по одному разу и вернуться в исходную точку. Додекаэдр – это правильный (платонов) многогранник, гранями которого служат 12 правильных пятиугольников. У него 20 вершин и 30 рёбер. В каждой его вершине сходятся по 3 ребра (регулярный граф). Плоское изображение графа показано на рисунке.

1, 2, 3, 4, 5, 6, 19, 18, 14, 15, 16, 17, 7, 8, 9, 10, 11, 12, 13, 20.

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

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

Поиск критерия гамильтоновости графа – одна из основных нерешённых проблем теории графов. О гамильтоновых графах известно ещё очень мало.

Необходимые условия гамильтоновости графа неизвестны. Ясно, что гамильтонов граф должен быть связным. Ясно, что гамильтонов цикл не обязательно содержит все рёбра графа; гамильтонов путь всегда простой. Известны только некоторые достаточные условия – так, полный граф всегда гамильтонов. Чем больше степень каждой вершины тем, очевидно, вероятней существование гамильтонова пути. Один из наиболее известных результатов общего характера предлагается в такой теореме.

Теорема Дирака. Если в графе G = с n ³ 3 вершинами deg(vi ) ³ n/2,то граф G является гамильтоновым.

Поиск гамильтонова цикла в графе является одной из классических задач теории графов и теории алгоритмов. Решить её можно следующим образом. Если в графе G = с n вершинами зафиксировать одну из вершин и обход графа всегда начинать с неё, то всякому гамильтоновому циклу будет соответствовать перестановка множества вершин (v1. v(i1 ), …, v(in-1 )). Следовательно, найти гамильтонов цикл или убедиться в его отсутствии можно путём перебора (n-1)! перестановок. Если граф гамильтонов, то этот перебор в полном необходимо будет выполнить лишь в случае большого невезения, т.е. когда перестановка, соответствующая гамильтонову циклу, встретится в этом процессе последней. Если же граф негамильтонов или необходимо найти все гамильтоновы циклы, то, действуя таким образом, необходимо перебрать все (n-1)! перестановок. Хотя на практике пользуются разными алгоритмами частичного перебора, но всё равно сложность этих алгоритмов остаётся высокой – пропорциональной (n-1)!

Для примера: нахождение гамильтонова цикла в графе, содержащем 14 вершин, требует суточной работы самых мощных машин; увеличение быстродействия в 10 раз приведет к решению в сутки задачи с 15-ю городами; для 50 городов потребуется

Существует класс так называемых переборных задач, сложность которых аналогична задаче Гамильтона. Если хотя бы для одной из этих задач существует эффективный алгоритм[1], то также существует эффективный алгоритм решения целого класса аналогичных задач – так называемых NP-полных задач. Верно и обратное – доказательство отсутствия эффективного алгоритма для одной задачи распространяется на весь класс. На этом основано общепринятое мнение, что таких алгоритмов не существует.

Задача коммивояжёра формулируется следующим образом.

Имеется n городов, расстояния между которыми известны. Коммивояжёр должен посетить все n городов по одному разу, вернувшись в тот, с которого начал. Требуется найти такой маршрут, при котором суммарное пройденное расстояние (стоимость/надёжность пути) будет минимальным.

Задача коммивояжёра состоит из 2-х частей – сначала надо найти все гамильтоновы циклы в графе, а затем для каждого найденного цикла вычислить вес и выбрать минимальный (максимальный). Практически следует рассматривать и варианты без возврата в начальную вершину.

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

Жордановой кривой на плоскости (на сфере, в пространстве, etc…) называется непрерывная кривая, не имеющая самопересечений. Замкнутой жордановой кривой называется жорданова кривая, начало и конец которой совпадают.

Гамильтонов граф

Рис. 1. Примеры жордановых кривых

Теорема Жордана. Пусть W – область, границей которой служит замкнутая жорданова кривая L, точки x, y Î L. Тогда: любая жорданова кривая Г, имеющая началом и концом точки x и y: а) лежит целиком в W; б) лежит целиком вне W; в) пересекает L в точках, отличных от x и y.

Определение. Граф G(V,E) обладает укладкой (может быть уложен) в данном пространстве, если он изоморфен некоторому графу, изображённому в этом пространстве при помощи точек, представляющих вершины V и жордановых кривых, представляющих рёбра E, причём эти жордановы кривые не пересекают друг друга.

а) жордановы кривые, соответствующие разным рёбрам, пересекаются в точках, не соответствующих вершинам;

б) жорданова кривая, соответствующая ребру, проходит через вершину, не инцидентную ребру.

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

Лемма. Любой граф может быть уложен в трехмерном пространстве .

&#&668; Рисуем вершины графа на прямой линии. Для любого ребра еi. соединяющего 2 вершины проводим плоскость, содержащую эту прямую, а ребро рисуем на плоскости. &#&658;

Граф называется планарным . если существует его укладка на плоскости. Сама же укладка графа на плоскости называется плоским графом .

Граф планарен, если существует его укладка на сфере . Доказательство – стереографическая проекция.

Доказательство следует из взаимно однозначного соответствия точек на сфере с точками плоскости из стереографических проекций.

Следствие. Граф любого выпуклого многогранника планарен.

Ребра плоского графа разбивают плоскость на несколько частей, одна из которых бесконечна. Эти части и являются гранями плоского графа.

Теорема Эйлера (формула Эйлера). В связном планарном графе справедливо следующее соотношение между числами вершин, ребер и граней :

В – Р + Г = 2, или n – m + g = 2.

Докажем индукцией по числу граней

&#&658;Если g = 1, то в графе нет ни одного цикла (такой граф называется деревом). У дерева число вершин больше числа ребер на 1, т.е. n = m + 1 ” n – (n–1) + 1 = 2 – формула справедлива.

Пусть формула Эйлера верна при g = k–1. Рассмотрим граф с числом граней g = k.

Возьмём ребро, отделяющее бесконечную грань от внутренних и удалим его из графа. Полученный граф останется связным (мы выбрали именно такое ребро) и будет иметь n вершин, m–1 ребро и k–1 грань. По предположению индукции n – (m–1) + (k–1) = 2, т.е. n–m+k=2. &#&668;

Следствие 1. Для плоского связного простого графа справедливо соотношение: n £ 3(m–2).

Следствие 2. Для плоского связного простого графа без треугольных граней справедливо соотношение: n £ 2(m–2).

Гамильтонов граф

Граф К5 Изоморфизмы графа К3,3

Рис. 2. Непланарные графы

Гамильтонов граф это:

Гамильтонов путь (чёрным)

Гамильтонов граф  — в теории графов это граф. содержащий гамильтонову цепь или гамильтонов цикл .

Гамильтонов путь (или гамильтонова цепь ) — путь (цепь ), содержащий каждую вершину графа ровно один раз. Гамильтонов путь, начальная и конечная вершины которого совпадают, называется гамильтоновым циклом . Гамильтонов цикл является простым остовным циклом (см. Словарь терминов теории графов ). Задача определения содержит ли данный граф гамильтонов цикл является NP-полной .

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

Содержание

Условия существования

Необходимое условие

Если неориентированный граф G содержит гамильтонов цикл, тогда в нём не существует ни одной вершины x(i) с локальной степенью p(x(i)) < 2. Доказательство следует из определения.

Условие Дирака (англ. ) (1952)

Пусть Гамильтонов граф — число вершин в данном графе; если степень каждой вершины не меньше, чем Гамильтонов граф, то граф называется графом Дирака. Граф Дирака — гамильтонов.

Условие Оре (1960)

Пусть Гамильтонов граф — количество вершин в данном графе. Если для любой пары несмежных вершин Гамильтонов граф выполнено неравенство Гамильтонов граф, то граф называется графом Оре (словами: степени любых двух несмежных вершин не меньше общего числа вершин в графе). Граф Оре — гамильтонов.

Теорема Бонди-Хватала

Теорема Бонди-Хватала (англ. ) обобщает утверждения Дирака и Оре. Для графа G с n вершинами замыкание определяется добавлением в G ребра (u ,v ) для каждой пары несмежных вершин u и v. сумма степеней которых не меньше n .

Граф является гамильтоновым тогда и только тогда, когда его замыкание — гамильтонов граф.

Смотреть что такое «Гамильтонов граф» в других словарях:

Граф Петерсена — Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей … Википедия

Граф Мура — Граф Петерсена Граф Хивуда Граф Макджи … Википедия

Граф Гамильтона — граф, содержащий цикл (замкнутый путь), в который входят все вершины, причем по одному разу (гамильтонов цикл), т.е. который можно обойти; эффективный общий алгоритм выяснения, является ли данный граф гамильтоновым, не известен, и задача… … Мир Лема — словарь и путеводитель

Граф Арран — Клан Гамильтон Hamilton Девиз «Сквозь!» (гэльск. Troimh, англ. Through) Земли Арран, Ренфрушир Символ Листья лавра … Википедия

ГРАФ СЛУЧАЙНЫЙ — вероятностная модель, предназначенная для изучения частотных характеристик различных параметров графов. Под Г. с. обычно понимается нек рый класс графов на к ром задано распределение вероятностей. Произвольный конкретный граф Gиз наз. реализацией … Математическая энциклопедия

Вершина (граф) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия

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

Стюарт, Джеймс, граф Арран — В Википедии есть статьи о других людях с именем Джеймс Стюарт. Джеймс Стюарт (англ. James Stuart; ум. 1595), граф Арран (с 1581 г.) шотландский дворянин, фаворит короля Якова VI, глава умеренно консервативного правительства Шотландии в 1583… … Википедия

Джеймс Стюарт, граф Арран — Джеймс Стюарт (англ. James Stuart; ум. 1595), граф Арран (с 1581 г.) шотландский дворянин, фаворит короля Якова VI, глава умеренно консервативного правительства Шотландии в 1583 1585 гг. Содержание 1 Молодые годы 2 Приход к власти … Википедия

3.2. Гамильтоновы графы

Гамильтоновым циклом в графе G называется цикл, содержащий все вершины графа G. Гамильтонов путь в графе G — это путь, содержащий все вершины графа

Граф G называется гамильтоновым, если он имеет гамильтонов цикл.

Граф представленный на рис. 3.5, а, является гамильтоновым, так как последовательность его ребер образует гамильтонов цикл. Граф на рис. 3.5, б имеет гамильтонов путь, состоящий из ребер но не имеет гамильтонова цикла.

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

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

Рис. 3.5. а — гамильтонов граф; б — негамнльтонов граф, имеющий гамильтонов путь.

Однако известно несколько достаточных условий того, что простой граф является гамильтоновым. (Напомним, что простым называется граф, не содержащий параллельных ребер и петель.) Некоторые из таких условий мы рассмотрим в этом разделе.

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

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

Следующий результат получен в работе [3.1].

Теорема 3.4. Простой порядка , имеющий последовательность степеней является гамильтоновым, если

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

Докажем теорему от противного. Пусть существует простой негамильтонов граф, последовательность степеней которого удовлетворяет условию (3.1). Тогда он является остовным подграфом простого максимального негамнльтонова графа , в котором последовательность степеней также удовлетворяет условию (3.1).

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

негамильтонов граф, следует, что добавление ребра, соединяющего вершины и и v, преобразует граф в гамильтонов.

Таким образом, в графе G существует гамильтонов путь где и к v — конечные вершины (рис. 3.6).

Пусть существует так как если существует, то граф G будет содержать ребра а тогда циклическая последовательность вершин и у, образует в графе G гамильтонов цикл.

Так как вершина не принадлежит ни S, ни Т, из этого следует, что . Поэтому где обозначает число элементов множества X.

Так как то ни одна вершина не смежна с вершиной v. Из выбора следует, что для справедливо неравенство . Таким образом, существует по крайней мере вершин, степени которых не превышают . Поэтому если мы положим то получим у и, следовательно, по условию (3.1) k. Это означает, что существует по крайней мере вершин, степени которых не превышают Вершина и может быть смежна, самое большее, с k из вершин, так как Таким образом, существует вершина w с не смежная с вершиной . Но тогда , что противоречит выбору

В следующем следствии мы установим достаточные условия гамильтоновости графа, представленные в работах

Следствие 3.4.1. Простой граф порядка 3 с последовательностью сюпеней является гамильтоновым, если для него выполнено одно из следующих условий:

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

Очевидно, что любая последовательность степеней, удовлетворяющая условию 1, удовлетворяет также и условию 2.

Пусть из условия 2 не следует условие 3. Тогда существует такое что и . Теперь предположим, что существует, для которого

Тогда выражение противоречит условию 2.

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

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

вершиной Поэтому Но тогда Таким образом, мы имеем , что противоречит условию 2.

. Если из условия 3 не следует условие 4, то существует такое что . Тогда . Если теперь мы положим то получим . Поэтому имеем неравенства, противоречащие условию (3.1). Если это не верно, то существует такое t, что Но тогда что противоречит условию 4.

Очевидно, если какая-либо графическая последовательность удовлетворяет условиям теоремы 3.4 или следствия 3.4.1, то тем же условиям удовлетворяет любая графическая последовательность, мажорирующая ее.

Условие Хватала — самое сильное из этих пяти условий и вообще из всех подобных условий. Это означает, что если какая-либо графическая последовательность не удовлетворяет условию Хватала, то она мажорируется последовательностью степеней негамильтонова графа [3.1].

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

Рис. 3.7. Негамильтонов граф.

Это иллюстрируется в работе [3,6] на следующем примере.

Рассмотрим граф G, представленный на рис. 3.7. Покажем, что он не содержит гамильтонова пути.

В гамильтонов путь можно включить не более двух ребер, инцидентных какой-либо вершине. В графе G вершина имеет степень 5, и, следовательно, по меньшей мере три ребра, инцидентных вершине не войдут в гамильтонов путь. То же самое справедливо и для вершин Так как степени вершин равны 3, то по крайней мере одно из ребер, инцидентных каждой из этих вершин, не будет включено в гамильтонов путь. Таким образом, в гамильтонов путь нельзя включить по крайней мере 13 из 27 ребер графа. Следовательно, чтобы составить гамильтонов путь на 16 вершинах графа G, ребер не достаточно. Поэтому граф G гамильтонова пути не содержит.

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

Следующая теорема полностью характеризует произвольно гамильтоновы графы. Доказательство ее можно найти в работе [3.7].

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

Закончим этот раздел рассмотрением задачи о коммивояжере. Она заключается в следующем:

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

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

В полном графе порядка существует гамильтоновых циклов. Подход «грубой силы» к задаче о коммивояжере состоит в порождении всех гамильтоновых циклов и последующем выборе кратчайшего. Объем затрат при таком подходе слишком велик (даже для ЭВМ) уже для величин , меньших 50. Для произвольного алгоритма решения этой проблемы просто не существует.

Для более полного ознакомления с этой задачей можно использовать работы [3.8-3.11].

Гамильтоновы графы

Напомним основные определения из теории графов. Пусть V непустое конечное множество. Через V (2) обозначим множество всех двухэлементных подмножеств из V. Графом G называется пара множеств ( V. E ), где E — произвольное подмножество из V (2). Элементы множеств V и E называют соответственно вершинами и ребрами графа G. Граф G ( V. E ) называется полным. если любая пара его вершин соединена хотя бы в одном направлении.

Маршрутом (или путем ) в графе G называется чередующаяся последовательность вершин и ребер v 0. e 1. v 1. …, v t −1. e t. v t +1. в которой e i = v i −1 v i (1 ≤ i ≤ t ). Такой маршрут кратко называют ( v 0. v t )-маршрутом и говорят, что он соединяет v 0 c v t ; в свою очередь вершины v 0. v t — это концевые вершины указанного маршрута. Длиной маршрута называют количество содержащихся в нем ребер. Заметим, что в обыкновенном графе маршрут полностью определяется последовательностью v 0. v 1. …, v t своих вершин. Если v 0 = v t. то ( v 0. v t )-маршрут называется замкнутым.

Цепь — это маршрут без повторяющихся ребер. Цепь называется простой цепью, если в ней нет повторяющихся вершин, кроме, быть может, совпадающих концевых вершин. Замкнутая простая цепь называется циклом (или контуром ).

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

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

Гамильтонов граф

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

  1. ( Задача про банкет ) Компанию из нескольких человек требуется рассадить за круглым столом таким образом, чтобы по обе стороны от каждого сидели его знакомые. Очевидно, для решения этой задачи нужно найти гамильтонов цикл в графе знакомств компании.
  2. ( Задача о шахматном коне. ) Можно ли, начиная с произвольного поля шахматной доски, обойти конем последовательно все 64 поля по одному разу и вернуться в исходное поле? (решение будет рассмотрено ниже).

Следующая теорема, доказанная Поша (Posa L.), дает достаточное условие того, что неориентированный граф является гамильтоновым. Она обобщает результаты, полученные ранее Оре (Ore O.) и Дираком (Dirac G.A.), которые приводятся здесь в виде следствий.

Пусть G имеет p ≥ 3 вершин. Если для всякого n. 1 ≤ n ≤ ( p −1) ⁄ 2, число вершин со степенями, не превосходящими n. меньше чем n. и для нечетного p число вершин степени ( p −1) ⁄ 2 не превосходит ( p −1) ⁄ 2, то G — гамильтонов граф.

Доказательство. Предположим, что теорема неверна, и пусть G — максимальный негамильтонов граф с p вершинами, удовлетворяющий условиям теоремы. Легко видеть, что добавление любого ребра в граф, обладающий указанными в теореме свойствами, приводит к графу, который так же обладает этими свойствами. Таким образом, поскольку добавление к G произвольного ребра приводит к гамильтонову графу, любые две несмежные вершины соединимы простой остовной (содержащей все вершины графа) цепью.

Покажем сначала, что всякая вершина, степень которой не меньше ( p −1)/2, смежна с каждой вершиной со степенью, большей чем ( p −1)/2. Допустим (не теряя общности), что deg v 1 ≥ ( p −1)/2 и deg v p ≥ p /2, но вершины v 1 и v p не смежны. Тогда существует простая остовная цепь v 1 v 2 … v p. соединяющая v 1 и v p.

Гамильтонов граф

Обозначим вершины, смежные с v 1. через v i 1 ,…, v i n . где n = deg v 1 и 2 = i 1 < i 2 <9hellip;9lt; i n. Ясно, что вершина v p не может быть смежной ни с одной вершиной из G вида v i j −1. поскольку тогда в G был бы гамильтонов цикл
v 1 v 2 … v i j −1 v p v p −1 … v i j v 1.

Гамильтонов граф

Далее, так как n ≥ ( p −1)/2, то p /2 ≤ deg v p ≤ p −19minus; n < p /2, что невозможно. Поэтому v 1 и v p должны быть смежны.

Отсюда следует, что если deg v ≥ p /2 для всех вершин v. то G — гамильтонов граф. (Ниже это сформулировано в виде следствия 2.) В силу изложенного выше каждая пара вершин графа G смежна, т.е. G — полный граф. Мы пришли к противоречию, поскольку полный граф является гамильтоновым для всех p ≤ 3.

Таким образом, в G — есть вершина v с deg v < p /2. Обозначим через m наибольшую среди степеней всех таких вершин. Выберем такую вершину v 1. что deg v 1 = m. По принятому предположению число вершин со степенями, не превосходящими m. не больше чем m < p /2, поэтому должно быть более чем m вершин со степенями, превосходящими m. и, следовательно, не меньшим, чем p /2. В результате найдется некоторая вершина, скажем v p. степени по крайней мере p /2, не смежная с v 1. Так как v 1 и v p не смежны, то существует остовная простая цепь v 1 … v p. Как и выше, обозначим через v i 1 ,…, v i m вершины графа G. смежные с v 1. и заметим, что вершина v p не может быть смежной ни с одной из m вершин v i j −1 для 1 < j ≤ m. Но поскольку v 1 и v p не смежны, а v p имеет степень не меньше p /2, то, как было показано в первой части доказательства, m должно быть меньше чем ( p -1)/2. Так как по предположению число вершин, со степенями, не превосходящими m. меньше чем m. то хотя бы одна из m вершин v i j -1. скажем u. должна иметь степень не меньше p /2. Итак, мы установили, что степени двух несмежных вершин v p и u не меньше p /2. Полученное противоречие завершает доказательство теоремы. ♦

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

Гамильтонов граф

Ограничивая условия теоремы Поша, получаем более простые, но менее сильные достаточные условия, найденные Оре и Дираком соответственно:

Следствие 1

Если p ≥ 3 и deg u + deg v ≥ p для любой пары u и v несмежных вершин графа G. то G — гамильтонов граф.

Следствие 2

Если p > 3 и deg v ≥ p / 2 для любой вершины v графа G. то G — гамильтонов граф.

В полном графе G ( V. E ) всегда существует гамильтонов путь.

Доказательство. Пусть m = a 1 a 2 … a p — путь длины p −1, причем все вершины в m различны. x — вершина ∉ m. Покажем, что можно составить путь вида

Пусть не существует такого целого числа k. заключенного между 1 и p. что

Имеем, следовательно, для 1 ≤ k ≤ p.

( a k. x ) ∈ E ⇒ ( x. a k +1 ) ∉ E ⇒ ( a k +1. x ) ∈ E.

Если не существует пути m 0 = x a 1 … a p. то ( a 1. x ) ∈ E ⇒ ( a 2. x ) ∈ E. ( a p. x ) ∈ E. и путь m p = a 1 … a p x существует, вопреки допущению. Таким образом, можно шаг за шагом построить путь, содержащий все вершины графа. ♦

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

Задача о шахматном коне

Поставим задачу обойти конем шахматную доску так, что побывать в каждой клетке ровно по одному разу. Эта задача интересовала многих математиков, особенно Эйлера (Euler L.), де Муавра (de Moivres), Вандермонда (Vandermonde) и др.

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

Другой способ состоит в нахождении маршрута по половинке доски, симметричном дублировании его и соединении обоих маршрутов.

Гамильтонов граф

Фактором графа ( V. E ) называется частичный граф ( V. E 0 ), в котором каждая вершина обладает полустепенями исхода и захода, равными 1. Всякий гамильтонов контур является фактором, но обратное неверно, ибо фактор может состоять из нескольких контуров без общих вершин.

Гамильтонов граф

EA = ∪ u ∈ A Eu.

т.е. EA является образом множества вершин A.

Определим простой граф ( V. V *. E ), соответствующий данному произвольному графу ( V. E ), следующим образом: V * есть дубликат множества V. a v * k ∈ Ev i в ( V. V *. E ) тогда и только тогда, когда v k ∈ Ev i в ( V. E ).

Гамильтонов граф

Теорема 3 (Кенига-Холла (Konig D. Hall P.))

Паросочетание, отображающие V в U. существует тогда и только тогда, когда | EW | ≥ | W | для любого множества W ⊂ V.

Пусть ( V. U. E ) — простой граф, a

тогда всегда существует паросочетание, использующее все те вершины v. для которых | Ev | = m. и все те вершины u. для которых | E −1 u | = m.

Необходимое и достаточное условие существования фактора у графа ( V. E ) состоит в том, чтобы | EW | ≥ | W | при всех W ⊂ V.

Доказательство. Действительно, в силу теоремы 3 это условие выражает тот факт, что в простом графе ( V. V *. E ), существует паросочетание, отображающее V на V *. ♦

Если граф ( V. E ) таков, что | Ev | = | E −1 v | = m для любой вершины v. то дуги этого графа можно распределить по m непересекающимся множествам W 1. W 2. …, W m. каждое из которых образует фактор.

Доказательство. Простой граф ( V. V *. E ) обладает свойством | Ev | = m. | E −1 v * | = m. В силу следствия из теоремы 3. можно отобразить V на V * и тем самым определить W 1. В частичном графе, остающимся после удаления дуг W 1. можно отобразить V на V * и тем самым определить W 2 и т.д. ♦

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

Так же можно «склеивать9raquo; различные контуры фактора. Рассмотрим вновь задачу о шахматном коне. Благодаря симметрии шахматной доски получается фактор, указанный на рисунке. Клетки, помеченные одинаковыми буквами, образуют контур. Два контура можно объединить тогда и только тогда, когда две последовательные вершины одного соответственно смежны с двумя последовательными вершинами другого. Различные соединения показаны при помощи вспомогательного графа. Вспомогательный граф имеет очевидный гамильтонов путь aDbCdAcB.

Гамильтонов граф

Алгоритм нахождения гамильтонова цикла

Рассмотрим рекурсивную функцию searchHamiltonianCycle. которая возвращает true. если граф является гамильтоновым, и false в противном случае.

  • numberOfVertices — число вершин в графе
  • v — последняя найденная вершина
  • w — начальная вершина (с нее начинается поиск)
  • d — оставшаяся длина гамильтонова цикла

Данный алгоритм напоминает алгоритм поиска в глубину (DFS). Основные отличия отмечены красным цветом:

  • функция принимает начальную вершину w и длину гамильтонова цикла в качестве второго и третьего параметров соответственно;
  • в строке 1, функция проверяет, все ли вершины были посещены ( d == 1 ), и если это так, то существует ли ребро, соединяющее начальную вершину с конечной. Если оба условия выполнены, то гамильтонов цикл найден;
  • в строке 7, функция переустанавливает значение маркера visited. прежде чем возвратит значение, означающие неуспех.

Рекурсивный поиск гамильтонова цикла может потребовать экспоненциального времени.

Доказательство. Рассмотрим граф, у которого одна вершина изолирована, а ребра, связывающие остальные | V |−1 вершин, образуют полный граф. Функция searchHamiltonianCycle никогда не найдет гамильтонова цикла, но она исследует все (| V |−2)! путей, начинающихся в выбранной начальной вершине, каждый из которых использует | V |−1 рекурсивных вызовов. Следовательно, общее число рекурсивных вызовов равно ( V −1). ♦

Список литературы

  1. Берж К. Теория графов и ее применения. — М. Издательство иностранной литературы, 1962.
  2. Седжвик Р. Фундаментальные алгоритмы на C++. Алгоритмы на графах. — СПб: ООО «ДиаСофтЮП9raquo;, 2002.
  3. Харари Ф. Теория графов. — М. Мир, 1973.

Визуализаторы

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *