16.2.2. Алгебраический метод

Идея алгоритма состоит в построении всех простых цепей в графе путем последовательного перемножения матриц графа. В качестве исходных матриц для перемножения используются модифицированная матрица смежности графа B и матрица перемножений P_L. Модифицированная матрица смежности B = ||b_ij||, представляет собой матрицу, в которой если x_i и x_j смежны, то в ячейку матрицы вместо единицы заносится x_j. На первом этапе матрица перемножений P_L = ||p_L(i, j)|| идентична матрице B, а элемент матрицы p_{L(i, j)} представляет собой сумму внутренних произведений все простых цепей длиной l. Выражение вида x₂  x₃   x_k-1, получаемое в ячейке на пересечении строки x₁ и столбца x_k, представляет собой цепь x₁, x_2, x₃, , x_k-1, x_k.

Алгебраическое произведение матриц P^’_L+1 = B  P_L представляет собой матрицу P^’_L+1 = p_{L+1(s, t)}, где элемент p_{L+1(s, t)} = .

Из полученной таким образом матрицы алгебраического произведения P^’_L+1 исключаются элементы, расположенные на главной диагонали. Кроме того, из ячеек, содержащих суммы внутренних произведений, исключаются слагаемые, содержащие начальный элемент простой цепи в качестве сомножителя. Полученная после подобного преобразования матрица, обозначается нами как P_L+1, после чего процесс повторяется. По достижении n ─ 1 шага все непустые элементы матрицы P_n-1 представляют собой гамильтоновы цепи, которые при наличии ребра u(x_k ─ x₁) образуют гамильтоновы циклы.

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

Пример 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 и матрицу перемножений P₁ для заданного графа. Матрица P₁ на первом этапе совпадает с матрицей.

B = .

2. После перемножения матриц B и P₁, получим матрицу:

		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’₂ элементов, находящихся на главной диагонали, получим матрицу:

		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 и P₂, получим матрицу:

		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’₂ всех вышеуказанных элементов получим матрицу:

		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 и P₃, получим матрицу:

		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’₄ можем записать матрицу:

		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

Все ненулевые ячейки матрицы P₄ представляют собой гамильтоновы цепи. Концами этих цепей являются вершины, на пересечении которых располагается рассматриваемая ячейка. Например, ячейка на пересечении строки a и столбца d представляет собой гамильтонову цепь a – c– e – b – d. Те из построенных цепей, для которых существует замыкающее ребро, образовывают гамильтонов цикл. Анализ полученной матрицы P₄ позволяет сделать вывод о наличии в исходном графе G следующего ГЦ:

a – c – e – d – b.

Все остальные цепи либо не имеют замыкающего ребра, либо являются вариантами обнаруженного цикла. Например, c – e – d – b – a или d – b – a – c – e.

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