Асанов М.О., Баранский В.А., Расин В.В. - Дискретная математика. Графы, матроиды, алгоритмы - 2001

М.О.Асанов, В.А.Баранский, В.В.Расин

ДИСКРЕТНАЯ МАТЕМАТИКА: ГРАФЫ МАТРОИДЫ, АЛГОРИТМЫ

Ижевск: НИЦ "РХД", 2001, 288 стр.

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

Для студентов и аспирантов, специализирующихся в области компьютерных наук.

Содержание
Предисловие	3
1. Основные понятия теории графов	5
Основные определения	5
Маршруты, связность, циклы и разрезы	9
Ориентированные графы	14
Матрицы, ассоциированные с графом	16
2. Деревья	22
Леса, деревья, остовы	22
Блоки и точки сочленения	25
Число остовов в связном обыкновенном графе	30
3. Обходы графов	34
Эйлеровы графы	34
Гамильтоновы графы	38
4. Матроиды	44
Полумодулярные решетки, условие Жордана--Дедекинда	44
Конечномерные геометрические решетки и матроиды	47
Основные понятия теории матроидов	56
Различные аксиоматизации матроидов	59
Двойственный матроид	67
Жадный алгоритм	70
Изоморфизмы матроидов	72
Пространство циклов бинарного матроида	76
Пространство циклов и пространство разрезов графа	79
Монотонные полумодулярные функции. Индуцированный матроид	83
Трансверсальные матроиды	86
Дизъюнктное объединение и сумма матроидов	93
5. Планарность	102
Укладки графов, планарные графы	102
Формула Эйлера для плоских графов	104
Критерий планарности графа	107
Двойственные графы	120
6. Раскраски	126
Хроматические числа	126
Хроматические многочлены	131
Коэффициенты хроматических многочленов	138

7. Введение в алгоритмы	144
Алгоритмы и их сложность	145
Запись алгоритмов	147
Корневые и бинарные деревья	149
Сортировка массивов	152

8. Поиск в графе	159
Поиск в глубину	159
Алгоритм отыскания блоков и точек сочленения	163
Алгоритм отыскания компонент сильной связности в орграфе	168
Поиск в ширину	173
Алгоритм отыскания эйлеровой цепи в эйлеровом графе	177

9. Задача о минимальном остове	180
10. Пути в сетях	188
Постановка задачи	188
Общий случай. Алгоритм Форда--Беллмана	188
Cлучай неотрицательных весов. Алгоритм Дейкcтры	193
Случай бесконтурной сети	196
Задача о максимальном пути и сетевые графики	201
Задача о maxmin-пути	207
Задача о кратчайших путях между всеми парами вершин	210

11. Задача о максимальном потоке		213
Основные понятия и результаты		213
Алгоритм Форда--Фалкерсона		219
12. Паросочетания в двудольных графах		227
Основные понятия		227
Задача о наибольшем паросочетании. Алгоритм Хопкрофта--Карпа		228
Задача о полном паросочетании. Алгоритм Куна		244
Задача о назначениях. Венгерский алгоритм		249
13. Задача коммивояжера		259
Основные понятия		259
Алгоритм отыскания гамильтоновых циклов		260
Алгоритмы решения задачи коммивояжера с гарантированной оценкой		262
точности
Решение задачи коммивояжера методом ветвей и границ		270
Литература		278
Предметный указатель		282
Предметный указатель
Аксиома Штейница о замене 62	- Хопкрофта--Карпа 233
Аксиомы независимости 60	- Ярника--Прима--Дейкстры 185
Алгоритм Борувки--Краскала 181	- венгерский 251
- Куна 245	- линейный 146
- Флойда 211	- пирамидальной сортировки 154
- Форда--Беллмана 190	- полиномиальный 146
- Форда--Фалкерсона 225	- с возвратом 262

- топологической сортировки 197	- планарный 103
- экспоненциальный 146	- плоский 103
Атом решетки 46	- полный 7
База матроида 57	- - двудольный 8
- множества 57	- полуэйлеров 36
Блок 25	- помеченный 16
- висячий 30	- произвольно вычерчиваемый из
Вектор грани циклический 105	вершины 36
- инциденции 123	- связный 10
Величина потока 213	- эйлеров 34
Вершина висячая 7	Графы гомеоморфные 107
- изолированная 7	Дейкстры 194
- концевая 6	Дерево 22
- насыщенная относительно	- бинарное 150
паросочетания 228	- венгерское 246
- свободная относительно	- глубинное 160
паросочетания 228	- корневое 149
Вес остова 33	- кратчайших путей 196
- ребра 33, 180	- остовное 23
- элемента 70	- поиска 151
Высота корневого дерева 150	- - в ширину 175
Геометрия векторная проективная 53	- растущее 181
- комбинаторная 50	- решений 153
- проективная 53	- сортирующее 154
Грань плоского графа 103	Диаграмма 5
Граф 5	Длина маршрута 9
- (n,m)-граф 6	- ормаршрута 15
- (n,m,k)--граф 10	Дополнение 48
- n-граф 6	Дуга 14
- t-раскрашиваемый 126	- обратная в цепи 217
- t-хроматический 126	- прямая в цепи 217
- Петерсена 107	Жорданова кривая 102
- взвешенный 180	Задача коммивояжера 144
- вполне несвязный 7	- о maxmin-пути 207
- гамильтонов 38	- о кратчайшем пути 144, 188
- дважды помеченный 19	- о максимальном потоке 213
- двойственный 120	- о минимальном остове 180
- двудольный 8	- о наибольшем паросочетании 228
- неразделимый 25	- об остове минимального веса 33
- нулевой 7	- оптимального назначения 144
- обыкновенный 5	Изоморфизм графов 6
- одноэлементный 7	- матроидов 72
- ориентированный 14	Интервал решетки 44
- ориентируемый 15	Инцидентность 6

Источник 213	Неравенство полумодулярности 47
Кобаза матроида 67	Объединение матроидов 96
Компонента связности 10	- - дизъюнктное 93
- сильной связности 169	- подграфов 8
Контур 15	Окружение вершины 7
Коцикл матроида 68	Оператор замыкания 49
Лес 22	Орграф 14
- глубинный 160	- гамильтонов 41
- остовный 23	- орсвязный 15
- - в графе 180	- полугамильтонов 41
- продолжаемый до минимального	- связный 14
остова 180	- сильно связный 15
- растущий 181	- топологически отсортированный
Лист корневого дерева 149	197
- матроида 50	Ориентация графа 20
Маршрут 9	Орлемма о рукопожатиях 16
- замкнутый 9	Ормаршрут 14
Матрица Кирхгофа 18	- замкнутый 14
- инцидентности графа 19	Орцепь 15
- - орграфа 20	- гамильтонова 41
- смежности 16	- простая 15
Матроид 50	Орцикл 15
- бинарный 76	- гамильтонов 41
- векторный над телом 62, 63	Основание орграфа 14
- графический 73	Остов 23
- двойственный 67	- минимальный 180
- дискретный 69	Отец 149
- кографический 73	Отношение покрытия 45
- простой 50, 56	- связности 10
- разрезов 70	Очередь 148
- свободный 69	Паросочетание 87, 227
- связный 94	- максимальное 228
- столбцов 63	- наибольшее 228
- строк 63	- полное 244
- трансверсальный 87	- совершенное 244
- тривиальный 69	Пересечение подграфов 9
- циклов 62	Петля 5
Метод критического пути 203	Пирамида 154
Многочлен характеристический 17	- частичная 155
- хроматический 133	Плоскость проективная дезаргова 55
Множество зависимое 57	Подграф 8
- независимое 57	- остовный 8
- ребер разрезающее 10	- порожденный 8
Мост 10	- пустой 8

Подматроид 62	- светлое относительно
Подмножество замкнутое 49	паросочетания 228
Подпространство матроида 50	- темное относительно паросочетания
Поиск в глубину 159	228
- в графе 159	- циклическое 12
- в ширину 173	Редукция графа 8
Покрытие множества вершинное 89	- - хроматическая 133
Полустепень захода 15	Решетка 44
- исхода 15	- конечномерная геометрическая 47
Порождающее множество матроида	- модулярная 44
58	- полумодулярная 45
Последовательность степеней графа	- с дополнениями 48
39	- с относительными дополнениями 48
Поток в сети 213	Сеть 188
Потомок 149	Система коциклов фундаментальная
Предгеометрия комбинаторная 50	78
Предок 149	- различных представителей 90
Произведение подграфов 136	- разрезов графа фундаментальная 80
Пропускная способность разреза 216	- циклов графа фундаментальная 80
Пространство коциклов бинарного	- - фундаментальная 78
матроида 78	Сложность алгоритма временная 145
- разрезов 79	Смежность вершин 6
- циклов 79	- ребер 6
- - бинарного матроида 78	Стек 148
Путь в сети 188	Степень вершины 6
Раздувание матроида 63	Стоимость ребра 180
Размер задачи 145	Сток 213
Размерность геометрическая 54	Стягивание ребра 119
Разрез 10	Сумма матроидов 94
- в орграфе 215	Сын 149
- минимальный 216	Точка сочленения 25
Ранг графа 24	Трансверсаль 89
- матроида 58	- независимая частичная 91
- множества 59	- частичная 87
Раскраска графа 126	Турнир 42
- - несобственная 141	Укладка графа в пространстве 102
Расстояние между вершинами 188	Уровень вершины в корневом дереве
Ребро ациклическое 12	150
- висячее 7	Условие Жордана--Дедекинда 45
- древесное 159	Функция весовая 33
- кратное 5	- монотонная полумодулярная 83
- обратное 159	- размерности на решетке 46
- поперечное 176	- хроматическая 131
	Цепь 9

- M-цепь 233	- гамильтонов 38
- M-чередующаяся 230	- матроида 57
- f-дополняющая 217	Число Стирлинга второго рода 137
- f-ненасыщенная 220	- - первого рода 137
- в сети 217	- древовидности графа 99
- гамильтонова 38	- покрытия матроида 98
- полуэйлерова 36	- упаковки матроида 97
- простая 10	- хроматическое 126
- эйлерова 34	- цикломатическое 24
Цикл 10