Материал: Решение задач теории графов методические указания к практическим занятиям по дисциплине «Дискретная математика». Белецкая С.Ю

Рис. 11

4. Построение эйлеровых и гамильтоновых циклов в графе

4.1. Теоретические сведения

Цикл (цепь) в графе G называется эйлеровым (эйлеровой), если он (она) проходит по одному разу через каждое ребро этого графа. Если в графе существует эйлеров цикл, то его можно нарисовать, не отрывая карандаша от бумаги и не повторяя линий. Связный граф называется эйлеровым, если он содержит эйлеров цикл, и полуэйлеровым, если в нем существует незамкнутая эйлерова цепь. Согласно теореме Эйлера, связный граф является эйлеровым, тогда и только тогда, когда степени всех его вершин четны. Если число вершин нечетной степени в связном графе равно 2, то данный граф содержит эйлерову цепь. При этом вершины нечетной степени являются начальной и конечной вершинами цепи. На рис. 12, а, б изображены полуэйлеров и эйлеров графы. Порядок обхода этих графов показан стрелками с номерами соответствующих шагов (движение начинается из вершины x₁).

а б

Рис. 12

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

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

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

Рис. 13

Для построения гамильтоновых циклов может быть использован алгоритм Робертса и Флореса.

Алгоритм Робертса и Флореса для построения гамильтонова цикла включает следующие шаги:

1. Строится матрица М с элементами m_ij, число строк в которой равно максимальной степени вершин графа, число столбцов равно количеству вершин n. Элемент m_ij - i-я вершина, (например x_k) смежная с вершиной x_j. Вершины в столбцах матрицы M упорядочены.

2. p = x₁, где x₁ - начальная вершина. S={x₁}, где S - множество вершин строящегося гамильтонова цикла.

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

4. В столбце, соответствующем вершине p, выбирается первая возможная вершина x_k; эта вершина присоединяется к множеству S и p = x_k.

5. Если мощность множества S равна |S| = n, то найдена гамильтонова цепь, переход к шагу 6, а если |S| < n, то переход к шагу 3.

6. Если существует дуга или ребро (p, x₁), то найден гамильтонов цикл. Если надо найти все гамильтоновы циклы, то переход к шагу 7; иначе останов алгоритма.

7. Возвращение. Из множества S удаляется последняя включённая вершина x_r. Если при этом S =  (множество S пустое), то следует остановка алгоритма, т.е. все цепи и циклы найдены (или нет).

Если S, то p = x_r-1, где (r-1) - номер вершины, включенной в гамильтонов цикл.

8. Если в столбце p существуют возможные вершины, т.е. вершины, следующие за x_r, то переход к шагу 4. В противном случае x_r = x_r-1 и переход к шагу 7.

4.2. Примеры решения задач

Задача 1. Построить эйлеров цикл графа с использованием алгоритма Флери

Рис. 14

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

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

Рис. 15

Решение. Матрица M приводится ниже, вершины в каждом столбце расположены в алфавитном порядке:

Поиск всех гамильтоновых циклов производится следующим образом (вершина a выбирается в качестве или начальной вершины):

Множество S Комментарии

1. a Добавляем первую возможную верши-

ну в столбце a (то есть вершину b).

2. a, b Добавляем первую возможную верши-

ну в столбце b (то есть вершину c).

3. a, b, c Первая вершина (a) в столбце с не

является возможной (aS), добавляем

следующую вершину в столбце

(то есть вершину d).

4. a, b, c, d Добавляем вершину f.

5. a, b, c, d, f В столбце f нет возможной вершины.

Возвращение.

6. a, b, c, d В столбце d не существует возможной

вершины , следующей за f.

Возвращение.

7. a, b, c Аналогично предыдущему.

Возвращение.

8. a, b Добавляем вершину e.

9. a, b, e Добавляем вершину c.

10. a, b, e, c Добавляем вершину d.

11. a, b, e, c, d Добавляем вершину f.

12. a, b, e, c, d, f Гамильтонов цикл, замыкающийся дугой

(f, a). Возвращение.

13. a, b, e, c, d Возвращение.

14. a, b, e, c Возвращение.

15. a, b, e Добавляем вершину d.

16. a, b, e, d Добавляем вершину f.

17. a, b, e, d, f Добавляем вершину c.

18. a, b, e, d, f, c Гамильтонов цикл, замыкающийся

дугой (c, a). Возвращение.

19. a, b, e, d, f Возвращение.

20. a, b, e, d Возвращение.

21. a, b, e Возвращение.

22. a, b Возвращение.

23. a Возвращение.

24.  Конец поиска.

4.3. Упражнения

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

а б

Рис. 16

5. Определение кратчайшего пути между двумя вершинами графа. Алгоритм дейкстры

5.1. Теоретические сведения

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

Алгоритм Дейкстры — алгоритм поиска кратчайшего пути во взвешенном графе между двумя заданными вершинами s и t при неотрицательных весах всех дуг. Пусть s - начальная вершина пути, t - конечная.

На каждой итерации алгоритма каждая вершина x_i графа имеет метку l(x_i), которая может быть постоянной или временной. В первом случае l(x_i) является длиной кратчайшего (s, x_i)-пути; во втором случае l(x_i) - длина кратчайшего (s, x_i)-пути, проходящего через вершину x_i и вершины с постоянными метками. Таким образом временная метка l(x_i), является оценкой сверху для длины кратчайшего (s, x_i)-пути, и, став на некоторой итерации постоянной, она остается такой до конца работы алгоритма.

Кроме l(x_i), с вершинами графа связывается еще одна метка Q(x_i).На каждой итерации Q(x_i) является номером вершины, предшествующей х_i в кратчайшем (s, x_i)-пути.

После того, как последняя вершина t получила постоянную метку, с помощью меток Q(x) легко указать последовательность вершин, составляющих кратчайший (S,t)-путь: