dln001

Предметный указатель

Àбстрактный граф, 10 алгоритм:

Дейкстры, 82Демукрона, 29Краскала, 56Ли, 79Прима, 63

Уоршолла, 39Флери, 105Флойда, 87

ациклический орграф, 27 Áаза графа, 41

Âектор инцидентности, 20 вершинно-порожденный подграф, 11

волновой алгоритм, 80, 81

Ãамильтонов:граф, 112контур, 112цикл, 112

гамильтонова цепь, 113 граф конденсации, 33

Äвудольный граф, 15 дерево, 14, 44 диаметр графа, 22 длина цепи, 14

дополнительный граф, 14

Çадача:

коммивояжера, 126почтальона, 109трассировки, 78

Èзоморфизм, 7 инвариант, 8

k дольный граф, 17 код Прюфера, 48

компонента связности, 13, 32 коцикл, 101 коцикломатическое число, 101 критический путь, 96 кубический граф, 15

Ìаршрут, 30 матрицa:

(прямых) достижимостей, 36инцидентности, 20инцидентности орграфа, 25Кирхгофа, 19

обратных достижимостей, 37смежности, 18смежности орграфа, 24 матричная теорема

о деревьях, 55 метод ветвей и границ, 128 множество:

базисных разрезов, 100базисных циклов, 98фундаментальных

разрезов, 100фундаментальных циклов, 98 мультиграф, 17

Íадграф, 10 независимое множество

вершин, 124 неориентированное дерево, 43 неориентированный граф, 5 непомеченный граф, 10 несвязный граф, 13

Îграниченная достижимость, 38 однородный граф, 15 односторонне связный граф, 31 односторонняя компонента, 32 ориентированная простая

цепь, 30 ориентированная цепь, 30 ориентированное дерево, 45

141

ориентированный граф, 23 ориентированный маршрут, 30 ормаршрут, 30 орцепь, 30 остов, 44

остовное дерево, 44 остовный лес, 44 остовный подграф, 10

Ïодграф, 10 поиск в ширину, 77 полный граф, 14

полный двудольный граф, 16 полугамильтонов граф, 113 полумаршрут, 30 полупуть, 30 полустепень захода, 24 полустепень исхода, 24 полуцепь, 30 полуэйлеров граф, 102

порядковая функция графа, 28 порядок графа, 6 правильный разрез, 100 простая орцепь, 30 простая цепь, 14 простой разрез, 100 простой цикл, 14 псевдограф, 17 пустой граф, 13 путь, 30

Ðадиус графа, 22 разрез, 100

расстояние между вершинами, 22 реберно-порожденный подграф, 11 регулярный граф, 15 редукция матрицы, 130

Ñамодополнительный граф, 15 связный граф, 13, 14 сильная компонента, 32 сильно связный граф, 31 слабая компонента, 32 слабо связный граф, 31 список вершин, 21 список ребер, 21

степенная последовательность, 6 степень вершины, 6 суграф, 12

Òеорема:

Бине Коши, 53Дирака, 115Кенига, 16Кирхгофа, 55Кэли, 55Оре, 114

Эйлера о сумме степеней вершин графа, 7

Эйлера о существовании эйлерова цикла в графе, 103

топологическая сортировка, 27 транзитивное замыкание

графа, 39 транзитивный граф, 38 турнир, 26

Ôормула Пойа, 10

Öентр графа, 22 центральная вершина, 22 цепь, 14 цикл, 14

цикломатическое число, 99 ×асть графа, 12

Ýйлеров граф, 102 эйлеров цикл, 102 эйлерова цепь, 102

эксцентриситет вершины, 22

142

Содержание

Предисловие	3
1. Введение	5
1.1. Определение графа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	5
1.2. Подграфы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	10
1.3. Виды графов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	13
1.4. Матрицы графов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	18
1.5. Диаметр, радиус и центр графа . . . . . . . . . . . . . . . . . . . . . . .	22
1.6. Ориентированные графы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	23
1.7. Маршруты, цепи и простые цепи . . . . . . . . . . . . . . . . . . . . . .	30

2. Связность в орграфах	31
2.1. Основные понятия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	31
2.2. Компоненты связности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	32
2.3. Конденсация орграфа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	33
2.4. Отыскание сильных компонент . . . . . . . . . . . . . . . . . . . . . . . .	33
2.5. Матрицы достижимостей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	36
2.6. Получение матрицы достижимостей. . . . . . . . . . . . . . . . . . .	38
2.7. Алгоритм Уоршолла . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	39
2.8. База графа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	41

3. Деревья		43
3.1. Основные понятия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		43
3.2. Описание деревьев. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		46
3.3. Задачи с деревьями . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		50
3.3.1.	Перечисление остовных деревьев . . . . . . . . . . . . . . .	50
3.3.2.	Пересчет остовных деревьев. . . . . . . . . . . . . . . . . . . .	53
3.4. Задача о кратчайшем остове графа . . . . . . . . . . . . . . . . . . .		56
3.4.1.	Алгоритм Краскала . . . . . . . . . . . . . . . . . . . . . . . . . . . .	56
3.4.2.	Алгоритм Прима . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	63

143

4. Пути и маршруты в графах	70
4.1. Существование путей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	70
4.2. Пересчет маршрутов и путей . . . . . . . . . . . . . . . . . . . . . . . . . .	71
4.3. Перечисление маршрутов и путей . . . . . . . . . . . . . . . . . . . . .	73
4.4. Задачи о кратчайших путях . . . . . . . . . . . . . . . . . . . . . . . . . . .	75
4.4.1. Графы с дугами единичной длины . . . . . . . . . . . . .	77
4.4.2. Графы со взвешенными дугами (ребрами) . . . . .	81
4.4.3. Ациклические орграфы . . . . . . . . . . . . . . . . . . . . . . . .	92

5. Циклы	98
5.1. Фундаментальные циклы и разрезы . . . . . . . . . . . . . . . . . . .	98
5.2. Эйлеровы циклы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	102
5.2.1. Определение и условия существования . . . . . . . . .	102
5.2.2. Алгоритм поиска эйлерова цикла . . . . . . . . . . . . . .	105
5.2.3. О количестве эйлеровых графов . . . . . . . . . . . . . . .	108
5.2.4. Задача почтальона . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	109
5.3. Гамильтоновы циклы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	112
5.3.1. Определение и условия существования . . . . . . . . .	112
5.3.2. Методы поиска гамильтоновых циклов . . . . . . . . .	116
5.4. Задача коммивояжера . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	126
5.4.1. Применение и методы решения задачи . . . . . . . . .	127
5.4.2. Метод ветвей и границ . . . . . . . . . . . . . . . . . . . . . . . . .	128
Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	140
Указатель обозначений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	141
Предметный указатель . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	142

144