2020-04-07
226
Пример 1. Пусть задан граф G = (Х, U), изображенный на рис. 16.20. Построить ГЦ для заданного графа, используя алгоритм Робертса ─ Флореса.
Рис. 16.20. Исходный граф
Решение: Построим матрицу М для заданного графа. Она будет иметь следующий вид:
.
Теперь воспользуемся описанным ранее алгоритмом.
1.1. Выбираем из матрицы М вершину a и заносим ее в список: L = { а }.
2.1. По матрице смежности выбираем из столбца с индексом a вершину, расположенную в первой ячейке. Это вершина b: L = { a, b }.
2.2. Проверяем условие |L| = n. Условие не выполняется, поэтому переходим к п. 3.1.
3.1. Выбираем столбец b, рассматриваем вершину из первой ячейки ─ это вершина a. Такая вершина уже есть в списке L, поэтому из второй ячейки столбца b берем вершину c. Переходим к следующему шагу.
3.2. Вершины с в списке L нет. Заносим ее в список: L = { a, b, c }.
3.3. Проверяем условие |L| = n. Условие не выполняется, поэтому переходим к п. 4.1.
4.1. В столбце c рассматриваем вершину из первой ячейки ─ это вершина b. Такая вершина уже есть в списке L, поэтому из второй ячейки столбца c берем вершину d. Переходим к следующему шагу.
|
|
|
4.2. Вершины d в списке L нет. Заносим ее в список: L = { a, b, c, d }.
4.3. Проверяем условие |L| = n. Условие не выполняется, поэтому переходим к п. 5.1.
5.1. В столбце d все вершины уже рассмотрены. Поэтому возвращаемся на шаг назад и пытаемся построить другой вариант построения пути. Вершина d вычеркивается из списка L = { a, b, c }. Переходим к п. 6.1.
6.1. В столбце c из третьей ячейки столбца берем вершину e. Переходим к следующему шагу.
6.2. Вершины e в списке L нет. Заносим ее в список: L = { a, b, c, e }.
6.3. Проверяем условие |L| = n. Условие не выполняется, поэтому переходим к пункту 7.1.
7.1. В столбце e все вершины уже рассмотрены. Поэтому возвращаемся на шаг назад и пытаемся построить другой вариант построения пути. Вершина e вычеркивается из списка L = { a, b, c }. Переходим к пункту 8.
8.1. В столбце c все вершины уже рассмотрены. Поэтому возвращаемся на шаг назад и пытаемся построить другой вариант построения пути. Вершина c вычеркивается из списка L = { a, b }. Переходим к п. 9.1.
9.1. В столбце b из третьей ячейки столбца берем вершину d. Переходим к следующему шагу.
9.2. Вершины d в списке L нет. Заносим ее в список: L = { a, b, d }.
9.3. Проверяем условие |L| = n. Условие не выполняется, поэтому переходим к п. 10.1.
10.1. В столбце d из третьей ячейки столбца берем вершину c. Переходим к следующему шагу.
10.2. Вершины c в списке L нет. Заносим ее в список: L = { a, b, d, c }.
10.3. Проверяем условие |L| = n. Условие не выполняется, поэтому переходим к п. 11.1.
11.1. В столбце c из третьей ячейки столбца берем вершину e. Переходим к следующему шагу.
11.2. Вершины e в списке L нет. Заносим ее в список: L = { a, b, d, c, e }.
|
|
|
11.3. Проверяем условие |L| = n. Условие выполняется. Следовательно, в графе G построена гамильтонова цепь и нам необходимо проверить, есть ли в исходном графе замыкающее ребро, чтобы завершить гамильтонов цикл.
11.4. В столбце e имеется вершина a, следовательно, поставленная задача выполнена, в графе G построен гамильтонов цикл:
{ a ─ b ─ d ─ c ─ e ─ a }.
11.5. Конец работы алгоритма.
Пример 2. Пусть задан граф G = (X, U), изображенный на рис. 16.21. Построить ГЦ для данного графа алгебраическим методом.
Рис. 16.21. Исходный граф
Решение:
1. Запишем матрицу смежности B и матрицу перемножений P1 для заданного графа. Матрица P1 на первом этапе совпадает с матрицей.
B = 
.
2. После перемножения матриц B и P1, получим матрицу:
| a | b | c | d | e | |||
| P2= | a | b+c+e | e | e | b+e | b+c | . |
| b | e | a+d+e | a+e | e | a+d | ||
| c | e | a+e | a+e | e | a | ||
| d | b+e | e | e | b+e | b | ||
| e | b+c | a+d | a | b | a+b+c+d |
После исключения из матрицы P’2 элементов, находящихся на главной диагонали, получим матрицу:
| a | b | c | d | e | |||
| P2’= | a | 0 | e | e | b+e | b+c | . |
| b | e | 0 | a+e | e | a+d | ||
| c | e | a+e | 0 | e | a | ||
| d | b+e | e | e | 0 | b | ||
| e | b+c | a+d | a | b | 0 |
3. После перемножения матриц B и P2, получим матрицу:
| a | b | c | d | e | |||
| P3’= | a | be+ce+eb+ec | ca+ce+ea+ed | ba+be+ea | be+ce+eb | ba+bd+ca | . |
| b | de+db+eb+ec | ae+de+ea+ed | ae+de+ea | ab+ae+eb | ab+ac+db | ||
| c | eb+ec | ae+ea+ed | ae+ea | ab+ae | ab+ac | ||
| d | be+eb+ec | ea+ed | ba+be+ea | be+eb | ba+bd | ||
| e | be+ce+db+de | ae+ca+ce+de | ae+ba+be+de | ab+ae+be+ce | ab+ac+ba+bd+ca+db |
В полученной матрице сначала обнуляем ячейки главной диагонали, а затем из всех ячеек матрицы исключаем элементы, в которые в качестве сомножителя входят концевые вершины цикла. Например, в строке a исключаем все элементы, включающие в качестве сомножителя вершину a. Для наглядности такие элементы выделены в матрице жирным шрифтом. После исключения из матрицы P’2 всех вышеуказанных элементов получим матрицу:
| a | b | c | d | e | |||
| P3= | a | 0 | ce+ed | be | be+ce+eb | bd | |
| b | de+ec | 0 | ae+de+ea | ae | ac | ||
| c | eb | ae+ea+ed | 0 | ab+ae | ab | . | |
| d | be+eb+ec | ea | ba+be+ea | 0 | ba | ||
| e | db | ca | ba | ab | 0 |
4. После перемножения матриц B и P3, получим матрицу:
| a | b | c | d | e | |||
| P’4 = | a | bde+bec+ceb+edb | cae+cea+ced+eca | bde+bae+bea+eba | bae+cab+cae+ceb+eab | bac+cab | . |
| b | dbe+deb+dec+edb | ace+aed+dea+eca | abe+dba+dbe+dea+eba | abe+ace+aeb+eab | abd+dba | ||
| c | edb | ace+eca+aed | abe+eba | abe+ace+aeb+eab | abd | ||
| d | bde+edb+bec | eca | bae+bde+bea+eba | bae+eab | bac | ||
| e | bde+bec+ceb+dbe+deb+ dec | ace+aed+cae+cea+ced | abe+bae+bde+bea+dba+ dbe+dea | abe+ace+aeb+bae+cab+ cae+ceb | abd+bac+cab+dba |
После аналогичного преобразования матрицы P’4 можем записать матрицу:
| a | b | c | d | e | |||
| a | 0 | ced | bde | ceb | 0 | . | |
| b | dec | 0 | dea | ace | 0 | ||
| P4 = | c | edb | aed | 0 | abe+aeb+eab | abd | |
| d | bec | eca | bae+ bea+ eba | 0 | bac | ||
| e | 0 | 0 | dba | cab | 0 |
Все ненулевые ячейки матрицы P4 представляют собой гамильтоновы цепи. Концами этих цепей являются вершины, на пересечении которых располагается рассматриваемая ячейка. Например, ячейка на пересечении строки a и столбца d представляет собой гамильтонову цепь a – c – e – b – d. Те из построенных цепей, для которых существует замыкающее ребро, образовывают гамильтонов цикл. Анализ полученной матрицы P4 позволяет сделать вывод о наличии в исходном графе G следующего ГЦ:
a – c – e – d – b.
Все остальные цепи либо не имеют замыкающего ребра, либо являются вариантами обнаруженного цикла. Например, c – e – d – b – a или d – b – a – c – e.
Очевидно, что различные эвристические алгоритмы определения гамильтонова цикла, например, алгоритм Робертса–Флореса не могут дать точного решения задачи, но обеспечивают нахождение результата за полиномиальное время. В худшем случае, например, когда гамильтонова цикла в графе не существует, они могут свестись к полному перебору всех возможных вариантов. При анализе всех цепей можно получить точный результат, но для задач практически большой размерности такой вариант является неприемлемым. Алгоритм перемножения матриц позволяет всегда найти гамильтонов цикл в графе, если он существует, однако этот алгоритм сложно реализовать с вычислительной точки зрения.
|
|
|
