7 Методические указания по выполнению расчетно-графической работы № 7 на тему: «Нахождение всех гамильтоновых циклов на ориентированном графе»

11.1 Задание на расчетно-графическую работу № 7

Задание на выполнение РГР № 7 формулируется следующим образом: «Задан неориентированный граф на пяти вершинах. Построить его модифицированную матрицу смежности. Определить является ли граф гамильтоновым. Используя алгебраический метод, найти все гамильтоновы циклы на графе».

На рис. 11.1 изображен исходный граф G для получения варианта РГР 7. Граф G для выполнения расчетов получается из исходного графа удалением двух или трех ( в зависимости от варианта) дуг, указанных в табл. 11.1.

Таблица 11.1 — Данные по вариантам

Первая цифра номера зачетной книжки	Последняя цифра номера зачетной книжки
	0	1	2	3	4	5	6	7	8	9
0	ab ag	ab ga	ab dg	ab gd	ab cd	ab dc	ab bc	ab cb	ab bg	ab gb
1	ba ag	ba ga	ba dg	ba gd	ba cd	ba dc	ba bc	ba cb	ba bg	ba gb
2	bd ab	bd ba	bd gc	bd cg	bd cd	bd dc	bd bc	bd cb	bd ac	bd ca
3	db ab	db ba	db gc	db cg	db cd	db dc	db bc	db cb	db ac	db ca
4	cg ab	cg ba	cg ag	cg ga	cg gd	cg dg	cg ag	cg da	cg ac	cg ca
5	gc ab	gc ba	gc ag	gc ga	gc gd	gc dg	gc ad	gc dg	gc ac	gc ca
6	ab ba	ag ga	bg gb	cg gc	bd db	gd dg	ad da	cd dc	cb bc	ac ca
7	ab ba ag	ag ba dg	bg gb gd	cg gc cd	bd db dc	gd dg bc	ad da cb	cd dc bg	cb bc gb	ac ca bc
8	ab ba bc	ag ba bd	bg gb bd	cg gc ab	bd db bc	gd dg ad	ad da bc	cd dc ab	cb bc ag	ac ca bd
9	ab ba bccb	ag ba db	bg gb db	cg gc ba	bd db cb	gd dg da	ad da cb	cd dc ba	cb bc ga	ac ca db

11.2 Краткие теоретические сведения

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

Существует только достаточные условия существования гамильтоновых циклов на графе. Приведем несколько таких признаков.

Граф, обладающий гамильтоновым циклом, будем называть гамильтоновым.

Теорема Дирака. Граф гамильтонов, если степень любой его вершины удовлетворяет неравенству , гдеn — число вершин графа.

Теорема Оре. Граф гамильтонов, если степень любых двух его несмежных вершин иудовлетворяет неравенству.

Для нахождения всех гамильтоновых циклов на гамильтоновом гарфе будем использовать алгебраический подход. Его суть состоит в следующем

Пусть граф G задан своей булевой матрицей смежности H. Заменим малоинформативные единицы в этой матрице на имена соответствующих вешин. Возведение в степень такой модифицированной матрицы даст уже больше информации о маршрутах. Введем таким образом модифицированную матрицу B следующим правилом: элемент матрицыB равен , если существует путь из вершиныв вершину. Далее последовательно находим матрицы, где под произведением вершин понимается некоммутативная бинарная операция заданная на множестве слов. Слово — это упорядоченная последовательность вершин (букв). Произведение словаи словаесть слово. Оператор, действующий на элементыматрицы, вычеркивает (обнуляет) те элементы, в которых содержатся вершиныили. Такие элементы указывают на контуры, замыкающиеся наили. Для упрощения расчетов можно обнулять главную диагональ матрицы, кроме последней, т.к. ее диагональ и содержит все искомые гамильтоновы циклы, без начальной и конечной вершины, которые необходимо добавить.

11.3 Пример выполнения расчетов по поиску всех гамильтоновых циклов

на ориентированном графе.

Пусть в результате удаления дуг на исходнеом графе (рис. ) получен следующий граф G (рис. ).

Рис. 11.2 — ГрафG

a

b

c

d

g

11.3.1. Определяем гамильтонов или негамильтонов граф G. Для этого этого рассчитываем степени его вершин и используем теорему Дирака (теорему Оре применить нельзя так как все вершины графа попарно смежны друг другу). Результаты расчетов сведены в табл. 11.2

Табл. 11.2 – Определение наличия гамильтоновых циклов

на графе G

Характеристика графа G	Вершины графа G
	a	b	c	d	g
	4	3	4	4	3
	2	3	4	4	3
+	6	6	8	8	6
	да	да	да	да	да

Анализ данных из табл. 11.2 позволяет сделать вывод, что граф гамильтотнов.

11.3.2. Находим все гамильтоновы циклы на графе G.

Матрица H графа G показана на рис. 11.3. На рис. 11.3 показана модифицированная матрица смежности B графа G.

0	1	1	1	1
0	0	1	0	1
1	1	0	1	0
1	0	1	0	1
0	1	0	1	0

0	b	c	d	g
0	0	c	0	g
a	b	0	d	0
a	0	c	0	g
0	b	0	d	0

Рис. 11.2 — Матрица Hсмежности графаG

Рис. 11.3 — Модифицированная матрица смежности графа G

Умножаем матрицу H=на матрицуB. Получаем матрицу (рис. 11.4).

c+d	c+g	b+d	c+g	b+d
c	c+g	0	c+g	0
d	a	a+b+d0	a	a+b+d0
c	a+c+g	a	a+c+g	a
d	0	b+d	0	b+d

Рис. 11.3 — Матрица

Применяем к матрицеоператор. Получаем матрицу(рис. 11.4).

0	c+g	b+d	c+g	b+d
c	0	0	c+g	0
d	a	0	a	a+b+d0
c	a+c+g	a	0	a
d	0	b+d	0	0

Рис. 11.4 — Матрица

Умножаем матрицу B на матрицу , получаем матрицу(рис. 11.5).

bc+cd+dc+gd	ca+da+dc+dg	da+gb+gd	bc+bg+ca	ca+cb+cd+da
cd+gd	ca	gb+gd	ca	ca +cb+cd
bc+dc	ac+ag+da+dc+dg	ab+ad+da0	ac+ag+bc+bg	ab+ad+da
cd+gd	ac+ag+ca	ab+ad+gb+gd	ac+ag+ca	ab+ad+ca+cb+cd
bc+dc	da+dc+dg	da	bc+bg	da

Рис. 11.5— Матрица

Применяем к матрицеоператор. Получаем матрицу.

0	dc+dg	gb+gd	bc+bg	cb+cd
cd+gd	0	gd	ca	ca +cd
0	ag+da+dg	0	ag+bg	ab+ad+da
0	ac+ag+ca	ab+gb	0	ab+ca+cb
bc+dc	da+dc	da	bc	0

Рис. 11.5— Матрица

Ниже, на рис. 11.6 приводим матрицу , опуская промежуточные вычисления (при выполнении РГР 7 все расчеты приводятся полностью).

0	сdg+gbc	bgd+dgb	cbg+gbc	bcd+dcb
gdc	0	gda	cag	cad +cda
bgd	adg+dag	0	abg	dab
gbc	cag	agb	0	acb+cab
bcd	dac+dca	dab	bca	0

Рис. 11.6 — Матрица

Матрица получается диагональной (рис. 11.7). Процесс вычисления матриц завершен.

bgdc+cbgd+ +dgbc+gbcd	0	0	0	0
0	cadg+cdag+ +gdac+gdca	0	0	0
0	0	abgd+adgb+ +bgda+dagb	0	0
0	0	0	acbg+agbc+ +cabg+gbca	0
0	0	0	0	bcad+bcda+ +dacb+dcab

Рис. 11.6 — Матрица

К полученным слагаемым в элементе матрицыдобавляем в начале или в конце (в данном примере в начале) по вершине (рис. 11.7).

abgdc+acbgd+adgbc+agbcd

bcadg+bcdag+bgdac+bgdca

cabgd+cadgb+cbgda+cdagb

dacbg+dagbc+dcabg+dgbca

gbcad+gbcda+gdacb+gdcab

Рис. 11.7 — Диагональные элементы матрицыс добавленными в начале слагаемых вершинами

Выполним круговую перестановку в каждом слагаемом диагональных элементов матрицыс добавленными в начале вершинами . Получим список на рис. 11.8.

Рис. 11.7 — Диагональные элементы матрицыс добавленными в начале слагаемых вершинами

abgdc+acbgd+adgbc+agbcd

adgbc+agbcd+acbgd+abgdc

abgdc+adgbc+agbcd+agbcd

acbgd+agbcd+abgdc+adgbc

adgbc+agbcd+acbgd+abgdc

Удаляем из списка на рис. 11.7 одинаковые слагаемые. Получаем список гамильтоновых циклов графа G (рис. 11.8).

abgdс ,adgbcc,agbcd,acbgd

Рис. 11.8 — Список гамильтоновых циклов графа G

На этом расчеты закончены.