Эйлеровы циклы. Гамильтонов контур

Эйлеровы циклы и гамильтоновы циклы (контуры) часто встречаются в практических задачах и поэтому представляют особый интерес.

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

	Рис. 4.41 Рис. 4.42

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

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

Цикл, который проходит ровно один раз по каждому ребру неориентированного графа G, называется эйлеровым циклом.

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

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

Утверждения.

1. Связный неориентированный граф содержит эйлеров цикл (эйлерову цепь) тогда и только тогда, когда число вершин нечетной степени равно 0 (0 или 2).

2. Длясвязного графа G следующие утверждения эквивалентны:

а) G - эйлеров граф;

б) каждая вершина графа G имеет четную степень;

в) множество ребер графа G можно разбить на простые циклы.

3. Пусть G - данный неорграф, a L (G) - его реберный граф, тогда:

а) если G имеет эйлеров цикл, то L (G) имеет как эйлеров так и гамильтонов циклы;

б) если G имеет гамильтонов цикл, то L (G) также имеет гамильтонов цикл.

4. Сильно связный полный граф гамильтонов.

5. Пусть G - сильно связный граф на n вершинах без параллельных дуг и петель. Если для любой вершины х справедливо неравенство d ^-(х)+ d ⁺(х)³ n, то граф G имеет гамильтонов контур.

6. Если орграф G полный, то он имеет ориентированный гамильтонов путь.

4.12.1. Метод Флёри построения эйлерова цикла

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

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

Замечание. Граф G =(X, V) задается множеством X своих вершин и набором реберных окрестностей всех его вершин S (x)={ v |ребро v инцидентно вершине х }.

Шаг 1. Выбрать произвольную вершину х ₀Î X и положить х=x ₀, z = х ₀, С = x ₀, D = x ₀, где С - чередующаяся последовательность вершин и ребер, представляющая строящийся эйлеров цикл; D - чередующаяся последовательность, представляющая начальный отрезок цикла, который будет присоединен к текущему циклу С; х - конечная вершина в последовательности D; z - вершина на цикле С, которая служит началом D.

Шаг 2. В множестве S (x) \ [ V (С) È V (D)] выбрать произвольное ребро 1. Если S (x)=Æ, то прейти к шагу 5. Здесь V (С) и V (D) обозначают множество ребер из С и D.

Шаг 3. К D дописать ребро 1 и его конец у, т.е. положить D = D, 1, у.

Шаг 4. Положить х = у и перейти к шагу 2.

Шаг 5. Присоединить к С в вершине z цикл D, т.е. положить C = C [ x ₀, z), D, C (z, x ₀], где C [ x ₀, z) - начальный отрезок последовательности С до веpшины z, не включая z; C (z, x ₀] – отрезок последовательности С от z до x ₀, не включая z.

Шаг 6. Просматривая последовательность С слева направо, ищем первую такую вершину v, что S (v)\ V (C)=Æ. Если такой вершины нет, то перейти к шагу 8, иначе перейти к шагу 7.

Шаг 7. Положить x = v, z = v, D = v и перейти к шагу 2.

Шаг 8. Выдатьпоследовательность С, которая является эйлеровым циклом.

4.12.2. Метод перебора Робертса и Флореса для построения гамильтоновых путей и контуров

Метод состоит в выполнении следующей последовательности шагов.

Шаг 1. Построить матрицу , n =| X |, m =max[ d (x_i)], m_ij, x _iÎ X. m_ij - есть j -я вершина (скажем, x_k), для которой в графе G =(X, Г) существует дуга (x_i,x_k) (вершины в столбцах упорядочены).

Шаг 2. Положить p = x ₁ (x ₁ – отправная вершина), S ={ x ₁}.

Шаг 3. Если в столбце р существует возможная вершина (под возможной понимается вершина, еще не принадлежавшая S), то перейти к шагу 4, иначе к шагу 7.

Шаг 4. Выбрать первую возможную вершину x_k. Положить S = S È{ x_k }, p = x_k и перейти к шагу 5.

Шаг 5. Если | S |= n -1, то напечатать гамильтонов путь S и перейти к шагу 6, иначе перейти к шагу 3.

Шаг 6. Если существует дуга (p,x₁), то напечатать гамильтонов контур (S È{ x ₁}), иначе перейти к шагу 7.

Шаг 7. Удалить последнюю включенную в S вершину x ₁. Если S =Æ, то процесс заканчивается, так как все пути и контуры найдены. Останов. Иначе положить p = x_{i -1} и перейти к шагу 3.

Пример. Рассмотрим граф, изображенный на рис. 4.43.

Дата добавления: 2014-12-27