Примеры решения задач. Пример 1. Пусть задан граф g = (х, u), изображенный на рис

Пример 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		e	e	b+e	b+c	.
b	e		a+e	e	a+d
c	e	a+e		e	a
d	b+e	e	e		b
e	b+c	a+d	a	b

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		ce+ed	be	be+ce+eb	bd
b	de+ec		ae+de+ea	ae	ac
c	eb	ae+ea+ed		ab+ae	ab	.
d	be+eb+ec	ea	ba+be+ea		ba
e	db	ca	ba	ab

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		ced	bde	ceb		.
	b	dec		dea	ace
P4 =	c	edb	aed		abe+aeb+eab	abd
	d	bec	eca	bae+ bea+ eba		bac
	e			dba	cab

Все ненулевые ячейки матрицы 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.

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

ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ

1. В чем состоит идея алгоритма Робертса–Флореса?

2. Опишите последовательность построения гамильтонова цикла в графе с помощью алгоритма Робертса–Флореса.

3. Какова сложность алгоритма Робертса─Флореса?

4. В чем состоит идея алгебраического метода?

5. Опишите последовательность построения гамильтонова цикла в графе с помощью алгебраического метода.

6. Какова сложность алгебраического метода при построении одного гамильтонова цикла?

7. Какова сложность алгебраического метода при построении всех гамильтоновых циклов в графе?

8. В чем заключается отличие стратегии работы алгоритмов Робертса–Флореса и алгебраического?

9. Для решения каких задач следует применять алгоритм Робертса–Флореса?

10. В каких случаях применение алгебраического метода является эффективным?

Дата добавления: 2015-10-26