Алгоритм Робертса-Флореса.

Выберем вершину 10 в качестве начальной.

0) S={}; 1) S={10}; 2) S={10,7}; 3) S={10,7,8}; 4) S={10,7,8,4}; 5) S={10,7,8,4,5}; 6) S={10,7,8,4,5,12}; 7) S={10,7,8,4,5,12,1}; 8) S={10,7,8,4,5,12,1,13}; 9) S={10,7,8,4,5,12,1,13,9}; 10) S={10,7,8,4,5,12,1,13,9,2}; 11) S={10,7,8,4,5,12,1,13,9,2,3}; 12) S={10,7,8,4,5,12,1,13,9,2,3,11}; 13) S={10,7,8,4,5,12,1,13,9,2,3,11,6}

V={1,2,3,4,5,6,7,8,9,10,11,12,13}; V={1,2,3,4,5,6,7,8,9,11,12,13}; V={1,2,3,4,5,6,8,9,11,12,13}; V={1,2,3,4,5,6,9,11,12,13}; V={1,2,3,5,6,9,11,12,13}; V={1,2,3,6,9,11,12,13}; V={1,2,3,6,9,11,13}; V={2,3,6,9,11,13}; V={2,3,6,9,11}; V={2,3,6,11}; V={3,6,11}; V={6,11}; V={6}; V={};

 

Так как цепь, проходящая через вершины множества S, имеет длину
p-1=13-1=12, и в графе G2 существует ребро, соединяющее последнюю и первую вершины цепи, замыкая ее, то в графе существует гамильтонов цикл и множество S={10,7,8,4,5,12,1,13,9,2,3,11,6,10} – множество вершин этого цикла.

 

Вывод: изучены понятия гамильтоновых и эйлеровых циклов, приобретены практические навыки построения матрицы циклов и матрицы фундаментальных циклов.

ЛАБОРАТОРНАЯ РАБОТА №4

Тема: «Ориентированные графы».

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

 

1. Используя алгоритм генерации варианта GV, построить ориентированный граф G1:GV(9,{6,7}).

 

Построим граф G1, используя алгоритм генерации варианта GV(9,{3,4}).

S=<юфаеленаяковлевна>;

S=< ю,ф,а,е,л,н,я,к,о,в>;

n(S_i)={32,22,1,6,13,15,33,12,16}.

 

Y

Матрица смежности

A

 

 

G1=(V1,A1):

V1={1,2,3,4,5,6,7,8,9} – множество вершин графа;

A1={(3,2),(3,5),(3,7),(3,9),(4,2),(4,6),(4,7),(4,8),(5,2),(5,7),(5,9),(8,1),(8,6),

(8,7),(8,9),(9,1),(9,2)} – множество дуг графа.

 

Построим графическое изображение графа G1.

 

2. Построить матрицу смежности и матрицу инцидентности заданного графа.

 

Матрица смежности

 

A

 

Матрица инцидентности

B	(3,2)	(3,5)	(3,7)	(3,9)	(4,2)	(4,6)	(4,7)	(4,8)	(5,2)	(5,7)	(5,9)	(8,1)	(8,6)	(8,7)	(8,9)	(9,1)	(9,2)	deg+	deg -	deg
												-1				-1
	-1				-1				-1								-1
		-1
						-1							-1
			-1				-1			-1				-1
								-1
				-1							-1				-1

 

3. Построить основание и обратный граф. Определить, является ли граф симметричным.

 

Основание орграфа – это неориентированный граф, полученный из орграфа в результате снятия ориентации дуг.

Обратный граф– это граф, дуги которого переориентированы по отношению к исходному орграфу.

 

Основание: Обратный граф:

Граф G симметричным не является, так как для каждой его дуги (u,v) не существует дуга (v,u).

4. Построить ормаршрут, цепь, путь, полумаршрут, полуцепь, полупуть, замкнутый маршрут, цикл и контур.

М1={4,8,9,2} – ормаршрут: чередующаяся последовательность вершин и дуг графа такая, что каждая дуга исходит из предыдущей вершины и заходит в последующую вершину;

М2={4,8,9,1} – цепь: ориентированный маршрут без повторяющихся дуг;

M3={3,5,9,2} – путь: цепь без повторяющихся вершин;

M4={3,2,5,9,1,7,4,2,5,9} – полумаршрут: маршрут основания орграфа;

M5={2,3,5,2,4,7,8,6} – полуцепь: цепь в основании графа;

M6={1,8,7,3,2,4} – полупуть: простой цикл в основании графа.

Замкнутый маршрут – это маршрут, который начинается и заканчивается в одной и той же вершине.

Цикл – это замкнутая цепь.

Контур – это замкнутый путь.

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

5. Построить матрицу достижимости, контрдостижимости, взаимной достижимости. Представить ограниченно достижимую матрицу для числа достижимости, равного 2.

Матрица достижимости

R

 

Матрица контрдостижимости

Q

 

Матрица взаимной достижимости

S

 

Ограниченно достижимая матрица для числа достижимости, равного 2.

R2

 

6. Определить тип связности орграфа, выделить сильные компоненты.

Так как в графе любые две вершины соединены полумаршрутом, то граф G слабосвязанный.

Так как в матрице взаимодостижимости единицы стоят только на главной диагонали, то сильными компонентами графа G являются вершины графа 1, 2, 3, 4, 5, 6, 7, 8, 9.

 

7. Построить конденсацию. Определить базы и антибазы.

Так как сильными компонентами графа G1 являются его вершины, то конденсацией является исходный граф G1.

Так как в графе нет контуров, то базу образуют вершины, которые имеют полустепень захода равную нулю, то есть вершины {3,4}, а антибазу – вершины, имеющие полустепень исхода равную нулю, то есть вершины {1,2,6,7}.

 

Вывод: в данной лабораторной работе изучены основные понятия ориентированных графов, приобретены практические навыки построения матрицы смежности, матрицы инцидентности, определен тип связности графа, построена конденсация орграфа, определены его базы и антибазы.

ЛИТЕРАТУРА

 

1. Берж К. Теория графов и ее применения. – М.: Изд-во иностр. лит., 1962.

2. Оре О. Теория графов. – М.: Наука, 1968.

3. Харари Ф. Теория графов. – М.: Мир, 1973.

4. Басакер Р. Саати Т. Конечные графы и сети. – М.: Наука, 1974.

5. Кристофидес Н.. Теория графов. Алгоритмический подход. – М.: Мир, 1973.

6. Ахо А., Хопфорд Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979.

7. Майника Э. Алгоритмы оптимизации на сетях и графах. – М.: Мир, 1981.

8. Свами М., Тхуласироман К. Графы, сети и алгоритмы. – М.: Мир, 1984.

9. Яблонский С. В. Введение в дискретную математику. – М.: Наука, 1986.

10. Липский В. Комбинаторика для программистов. – М.: Мир, 1988.

11. Лекции по теории графов/ Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. и др. – М.: Наука, 1990.

12. Нефедов В.Н., Осипова В.А. Курс дискретной математики. – М.: Изд-во МАИ, 1992.

13. Ловас Л., Планер М. Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии. – М.: Мир, 1998.

 

 

СОДЕРЖАНИЕ

 

1 ВВЕДЕНИЕ В ТЕОРИЮ НЕОРИЕНТИРОВАННЫХ ГРАФОВ.. 3

1.1 СВЕДЕНИЯ ИЗ ИСТОРИИ.. 3

1.2 ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ.. 3

1.3 СПОСОБЫ ЗАДАНИЯ ГРАФОВ.. 4

1.4 СТЕПЕНИ ВЕРШИН ГРАФА.. 5

1.5 ОПЕРАЦИИ НАД ГРАФАМИ.. 6

1.6 СПЕЦИАЛЬНЫЕ ГРАФЫ... 8

1.7 ПОДГРАФЫ... 9

1.8 ДВУДОЛЬНЫЕ ГРАФЫ... 11

1.9 ИЗОМОРФИЗМ ГРАФОВ.. 12

1.10 НЕЗАВИСИМОЕ МНОЖЕСТВО ВЕРШИН.. 13

1.11 КЛИКА.. 14

1.12 ДОМИНИРУЮЩИЕ МНОЖЕСТВА.. 15

1.13 Контрольные вопросы... 16

2 МАРШРУТЫ И СВЯЗНОСТЬ НЕОРИЕНТИРОВАННЫХ ГРАФОВ.. 17

2.1 ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ.. 17

2.2 СВЯЗНОСТЬ, КОМПОНЕНТЫ СВЯЗНОСТИ.. 18

2.3 МЕТРИЧЕСКИЕ ХАРАКТЕРИСТИКИ ГРАФА.. 19

2.4 ВЕРШИННАЯ И РЕБЕРНАЯ СВЯЗНОСТЬ.. 22

2.5 КРАТЧАЙШИЕ МАРШРУТЫ В ГРАФАХ.. 24

2.5.1 АЛГОРИТМ ДЕЙКСТРЫ... 24

2.5.2 АЛГОРИТМ ФОРДА.. 27

2.5.3 АЛГОРИТМ ФлойДА.. 30

2.6 Контрольные вопросы... 35

3 ДЕРЕВЬЯ И ОСТОВЫ... 36

3.1 ОСНОВНОЕ ОПРЕДЕЛЕНИЕ ДЕРЕВА.. 36

3.2 ДРУГИЕ ОПРЕДЕЛЕНИЯ ДЕРЕВА.. 36

3.3 ЯРУСНАЯ ФОРМА ПРЕДСТАВЛЕНИЯ ДЕРЕВЬЕВ.. 37

3.4 СПОСОБЫ ОБХОДА ДЕРЕВЬЕВ.. 37

3.5 ОСТОВЫ... 38

3.6 Алгоритмы построения ОСТОВа.. 39

3.7 МАТРИЧНАЯ ТЕОРЕМА КИРХГОФА.. 39

3.8 АЛГОРИТМЫ ПОИСКА ОСТОВОВ КРАТЧАЙШИХ МАРШРУТОВ.. 40

3.8.1 Алгоритм Краскала. 40

3.8.2 Алгоритм Прима. 41

3.9 КОНТРОЛЬНЫЕ ВОПРОСЫ... 43

4 ЦИКЛОМАТИКА.. 44

4.1 ЭЙЛЕРОВЫ ГРАФЫ... 44

4.2 АЛГОРИТМ ПОСТРОЕНИЯ ЭЙЛЕРОВОГО ЦИКЛА, 45

ИЛИ АЛГОРИТМ ФЛЁРИ.. 45

4.3 ГАМИЛЬТОНОВЫ ГРАФЫ... 46

4.4 ДОСТАТОЧНЫЕ УСЛОВИЯ СУЩЕСТВОВАНИЯ ГАМИЛЬТОНОВА ЦИКЛА В ГРАФЕ.. 47

4.5 АЛГОРИТМ ПЕРЕБОРА РОБЕРТСА - ФЛОРЕСА.. 48

4.6 ЗАДАЧА КОММИВОЯЖЕРА И ЗАДАЧА КИТАЙСКОГО ПОЧТАЛЬОНА.. 50

4.7 ОСНОВЫ ЦИКЛОМАТИКИ.. 51

4.8 МАТРИЦА ЦИКЛОВ.. 53

4.9 МАТРИЦА БАЗИСНЫХ ЦИКЛОВ.. 53

4.10 КОНТРОЛЬНЫЕ ВОПРОСЫ... 55

5 ОРИЕНТИРОВАННЫЕ ГРАФЫ... 56

5.1 ОПРЕДЕЛЕНИЕ И СПОСОБЫ ЗАДАНИЯ.. 56

5.2 МАРШРУТЫ И СВЯЗНОСТЬ.. 57

5.3 ТИПЫ СВЯЗНОСТИ ОРГРАФА.. 58

5.4 ТЕОРЕМЫ О СВЯЗНОСТИ ОРГРАФА.. 59

5.5 ТИПЫ КОМПОНЕНТ СВЯЗНОСТИ.. 59

5.6 АЛГОРИТМ ПОСТРОЕНИЯ КОНДЕНСАЦИИ.. 60

5.7 БАЗА И АНТИБАЗА.. 62

5.8 АЛГОРИТМ ПОСТРОЕНИЯ БАЗЫ... 63

5.9 АЛГОРИТМ ПОСТРОЕНИЯ АНТИБАЗЫ... 63

5.10 ОБХОДЫ ОРГРАФА.. 63

5.11 КОНТРОЛЬНЫЕ ВОПРОСЫ... 64

6 ЗАДАНИЯ ДЛЯ ЛАБОРАТОРНЫХ РАБОТ.. 65

6.1 ЛАБОРАТОРНАЯ РАБОТА №1. 65

6.2 ЛАБОРАТОРНАЯ РАБОТА №2. 65

6.3 ЛАБОРАТОРНАЯ РАБОТА №3. 66

6.4 ЛАБОРАТОРНАЯ РАБОТА №4. 67

6.5 Алгоритмы генерации вариантов.. 68

7 ПРИМЕРЫ ВЫПОЛНЕНИЯ ЛАБОРАТОРНЫХ РАБОТ.. 69

7.1 ЛАБОРАТОРНАЯ РАБОТА №1. 69

7.2 ЛАБОРАТОРНАЯ РАБОТА №2. 76

7.3 ЛАБОРАТОРНАЯ РАБОТА №3. 88

7.4 ЛАБОРАТОРНАЯ РАБОТА №4. 103

ЛИТЕРАТУРА.. 108