Гамильтонов цикл

Гамильтонов цикл

Содержание

Введение

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

1.1 Основные определения и результаты

1.2 Теоремы достаточности гамильтонова  графа

2.  Методы отыскания гамильтоновых циклов

2.1 Алгебраические методы

2.2 Метод перебора Робертса и  Флореса

2.2.1 Улучшение метода Робертса  и Флореса

Приложение

Заключение

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

 

Введение 

 

Целью моей курсовой работы является:

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

2.  Рассмотреть задачи и методы отыскания гамильтоновых циклов в графах

3. Создание программы для нахождения  гамильтоновых циклов.

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

Маршрутом в графе G(V,E) называется чередующаяся последовательность вершин и ребер:  , , …  ,  , в которой любые два соседних элемента инцидентны. Если   =  , то маршрут замкнут, иначе открыт.

Если все ребра различны, то маршрут  называется цепью. Если все вершины (а значит, ребра) различны, то маршрут  называется простой цепью.

Замкнутая цепь называется циклом; замкнутая  простая цепь называется простым  циклом. Граф без циклов называется ациклическим. Для орграфов цепь называется путем, а цикл — контуром. 

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

1.1 Основные определения  и результаты

Название «гамильтонов цикл» произошло  от задачи «Кругосветное путешествие» предложенной ирландским математиком  Вильямом Гамильтоном в 1859 году. Нужно  было, выйдя из исходной вершины  графа, обойти все его вершины  и вернуться в исходную точку. Граф представлял собой укладку  додекаэдра, каждой из 20 вершин графа  было приписано название крупного города мира.

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

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

Замечание.

Любой граф G можно превратить в гамильтонов граф, добавив достаточное количество вершин. Для этого, например, достаточно к вершинам v1,…, vp графа G добавить вершины u1, , up и множество ребер {(vi, ui)}   {(ui, vi+1)}.

Степенью вершины v называется число  ребер d(v), инцидентных ей, при этом петля учитывается дважды. В случае ориентированного графа различают степень do(v) по выходящим дугам и di(v) по входящим.

В отличии от эйлеровых графов, где имеется критерий для графа быть эйлеровым, для гамильтоновых графов такого критерия нет. Более того, задача проверки существования гамильтонова цикла оказывается NP-полной. Большинство известных теорем имеет вид: «если граф G имеет достаточное количество ребер, то граф является гамильтоновым». Приведем несколько таких теорем.

1.2 Теоремы достаточности  гамильтонова графа

Теорема (Дирак, 1952) 1. Если в простом графе с n ≥ 3 вершинами p(v) ≥ n/2 для любой вершины v, то граф G является гамильтоновым.

Замечание Существует несколько доказательств этой широко известной теоремы, здесь мы приводим доказательство Д. Дж. Ньюмана.

Доказательство. Добавим к нашему графу k новых вершин, соединяя каждую из них с каждой вершиной из G. Будем предполагать, что k — наименьшее число вершин, необходимых для того, чтобы полученный граф G¢стал гамильтоновым. Затем, считая, что k > 0, придем к противоречию.

Пусть v→p→w→…→v гамильтонов цикл в графе G¢, где v, w— вершины из G, а p— одна из новых вершин. Тогда w не является смежной с v, так как в противном случае мы могли бы не использовать вершину p, что противоречит минимальности k. Более того, вершина, скажем, w¢, смежная вершине w, не может непосредственно следовать за вершиной v¢, смежной вершине v, потому что тогда мы могли бы заменить v→p→w→…→v¢→ w¢→v на v→v¢→…→w→w¢→…→v, перевернув часть цикла, заключенную междуw и v¢. Отсюда следует, что число вершин графа G¢, не являющихся смежными с w, не меньше числа вершин, смежных с v (то есть равно, по меньшей мере, n/2 + k); с другой стороны, очевидно, что число вершин графа G¢, смежных с w, тоже равно, по меньшей мере, n/2 + k. А так как ни одна вершина графа G¢не может быть одновременно смежной и не смежной вершине w, то общее число вершин графа G¢, равное n + k, не меньше, чем n + 2k. Это и есть искомое противоречие. 

Теорема (Оре) 2. Если число вершин графа G(V, E) n ≥ 3 и для любых двух несмежных вершин u и v выполняется неравенство:

d(u) + d(v) ≥ n и  (u, v) E, то граф G — гамильтонов.

Граф G имеет гамильтонов цикл если выполняется одно из следующих условий:

Условие Бонди: из d(vi) ≤ i и d(vk) ≤ k => d(vi) + d(vk) ≥ n (k ≠ i)

Условие Хватала: из d(vk) ≤ k ≤ n/2 => d(vn-k) ≥ n - k.

Далее, известно, что почти все  графы гамильтоновы, то есть

 

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

Пример графа, когда не выполняется условие теоремы Дирака, но граф является гамильтоновым.

 

 

N = 8; d(vi) = 3; 3 ≤ 8/2 = 4 не гамильтонов граф, но существует гамильтонов цикл: M = (1, 2, 3, 4, 5, 6, 7, 8, 1)

 

2. Методы отыскания гамильтоновых  циклов

2.1 Алгебраические методы

Пока неизвестно никакого простого критерия или алгебраического метода, позволяющего ответить на вопрос, существует или нет в произвольном графе G гамильтонов цикл. Критерии существования, данные выше, представляют теоретический  интерес, но являются слишком общими и не пригодны для произвольных графов, встречающихся на практике. Алгебраические методы определения гаильтоновых циклов не могут быть применены с более  чем несколькими десятками вершин, так как они требуют слишком  большого времени работы и большой  памяти компьютера. Более приемлемым является способ Робертса и Флореса, который не предъявляет чрезмерных требований к памяти компьютера, но время в котором зависит экспоненциально от числа вершин в графе. Однако другой неявный метод перебора имеет для большинства типов графов очень небольшой показатель роста времени вычислений в зависимости от числа вершин. Он может быть использован для нахождения гамильтоновых циклов в очень больших графах. Этот метод включает в себя построение всех простых цепей с помощью последовательного перемножения матриц. «Внутреннее произведение вершин» цепи x1, x2, … , xk-1, xk определяется как выражение вида x2 * x3 * … xk-1, не содержащее две концевые вершины x1 и xk. «Модифицированная матрица смежности» B = [β(i, j)] — это (n × n)- матрица, в которой β(i, j) — xj, если существует дуга из xi в xj и нуль в противном случае. Предположим теперь, что у нас есть матрица PL = [pL(i, j)], где pL(i, j) — сумма внутренних произведений всех простых цепей длины L (L ≥ 1) между вершинами xi и xjдля xi ≠ xj. Положим pL(i, i)=0 для всех i. Обычное алгебраическое произведение матриц B * PL = P’L+1 = [p’L+1(s, t)] определяется как т.е. p’L+1(s, t) является суммой внутренних произведений всех цепей из xs в xt длины l+1. Так как все цепи из xk в xt, представленные внутренними произведениями из pL(k, t), являются простыми, то среди цепей,

k

p¢1+1(s, t) = ∑b(s, k) * p1(k, t)

получающихся из указанного выражения, не являются простыми лишь те, внутренние произведения которых в pL(k, t) содержат вершину xs. Таким образом, если из p’L+1(s, t) исключить все слагаемые, содержащие xs (а это можно сделать простой проверкой), то получим pL+1(s, t). Матрица PL+1 = [pL + 1(s, t)], все диагональные элементы которой равны 0, является тогда матрицей всех простых цепей длины L + 1.

Вычисляя затем B * PL+1, находим PL+2 и т.д., пока не будет построена матрица Pn-1, дающая все гамильтоновы цепи (имеющие длину n - 1) между всеми парами вершин. Гамильтоновы циклы получаются тогда сразу из цепей в Pn-1 и тех дуг из G, которые соединяют начальную и конечную вершины каждой цепи. С другой стороны, гамильтоновы циклы даются членами внутреннего произведения вершин, стоящими в любой диагональной ячейке матрицы B * Pn-1 (все диагональные элементы этой матрицы одинаковые).

Очевидно, что в качестве начального значения матрицы P (т.е. P1) следует взять матрицу смежности A графа, положив все ее диагональные элементы равными нулю.

Недостатки этого метода совершенно очевидны. В процессе умножения матриц (т.е. когда L увеличивается) каждый элемент матрицы PL будет состоять из все большего числа членов вплоть до некоторого критического значения L, после которого число членов снова начнет уменьшаться. Это происходит вследствие того, что для малых значений L и для графов, обычно встречающихся на практике, число цепей длины L + 1, как правило, больше, чем число цепей длины L, а для больших значений Lимеет место обратная картина. Кроме того, так как длина каждого члена внутреннего произведения вершин увеличивается на единицу, когда L увеличивается на единицу, то объем памяти, необходимый для хранения матрицы PL, растет очень быстро вплоть до максимума при некотором критическом значении L, после которого этот объем снова начинает уменьшаться.

Небольшая модификация вышеприведенного метода позволяет во много раз  уменьшить необходимый объем  памяти и время вычислений. Так  как нас интересуют только гамильтоновы циклы и, как было отмечено выше, они могут быть получены из членов внутреннего произведения любой  диагональной ячейки матрицы B * Pn-1, то необходимо знать только элемент pn-1(1, 1). При этом на каждом этапе не обязательно вычислять и хранить всю матрицу PL, достаточно лишь найти первый столбец PL. Эта модификация уменьшает необходимый объем памяти и время вычислений в n раз. Однако даже при использовании этой модификации программа для ЭВМ, написанная на языке PL/1, который позволяет построчную обработку литер и переменное распределение памяти, не была способна найти все гамильтоновы циклы в неориентированных графах с более чем примерно 20 вершинами и средним значением степени вершины, большим 4. Использовался компьютер IBM 360/65 с памятью 120 000 байтов. Более того, даже для графа с вышеуказанными «размерами» данный метод использовал фактически весь объем памяти и время вычислений равнялось 1.8 минуты. Не такое уж незначительное время для столь небольшого графа.

2.2 Метод перебора Робертса  и Флореса

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

Следующая схема перебора, использующая обычную технику возвращения, была первоначально предложена Робертсом  и Флоресом. Начинают с построения (k × n)-матрицы M=[mij], где элемент mij есть i-я вершина (скажем xq), для которой в графеG(X, Г) существует дуга (xj, xq). Вершины xq во множестве Г(xj) можно упорядочить произвольно, образовав элементы j-го столбца матрицы M. Число строк k матрицы M будет равно наибольшей полустепени исхода вершины.

Метод состоит в следующем. Некоторая  начальная вершина (скажем, x1) выбирается в качестве отправной и образует первый элемент множества S, которое каждый раз будет хранить уже найденные вершины строящейся цепи. К S добавляется первая вершина (например, вершина a) в столбце x1. Затем к множеству S добавляется первая возможная вершина (например, вершинаb) в столбце a, потом добавляется к S первая возможная вершина (например, вершина c) в столбце b и т.д. Под «возможной» вершиной мы понимаем вершину, еще не принадлежащую S. Существуют две причины, препятствующие включению некоторой вершины на шаге r во множество S = {x1, a, b, c, … , xr-1, xr}:

1)  В столбце xr нет возможной вершины.

2)  Цепь, определяемая последовательностью вершин в S, имеет длину n - 1, т.е. является гамильтоновой цепью.

В случае 2) возможны следующие случаи:

a)  В графе G существует дуга (xr, x1), и поэтому найден гамильтонов цикл.

b)  Дуга (xr, x1) не существует и не может быть получен никакой гамильтонов цикл.

В случаях (1) и (2b) следует прибегнуть к возвращению, в то время как в случае (2a) можно прекратить поиск и напечатать результат (если требуется найти только один гамильтонов цикл), или (если нужны все такие циклы) произвести печать и прибегнуть к возвращению.

Возвращение состоит в удалении последней включенной вершины xr из S, после чего остается множество S = {x1, a, b, c, … , xr-1}, и добавлении к S первой возможной вершины, следующей за xr, в столбце xr-1 матрицы M. Если не существует никакой возможной вершины, делается следующий шаг возвращения и т.д.

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

Рассмотрим пример поиска гамильтонова цикла в графе переборным методом  Робертса и Флореса.

Пример:

"2"

1) S = {1}

2) S = {1, 2}

3) S = {1, 2, 3}

4) S = {1, 2, 3, 4}

5) S = {1, 2, 3, 4, 5} - Г 4→3 4→5

6) S = {1, 2, 3, 4}

7) S = {1, 2, 3}  3→1 3→2 3→4

8) S = {1, 2}

9) S = {1}

"3"

10) S = {1, 3}  3→2

11) S = {1, 3, 2} 2→1

12) S = {1, 3} 2→3

13) S = {1, 3, 4} 3→4 4→5

14) S = {1, 3, 4, 5, 4} 5→нет

15) S = {1, 3, 4}

16) S = {1, 3}