От редактора перевода б
Предисловие ?
часть I
ОСНОВЫ ТЕОРИИ
Глава 1. Основные понятия: неориентированные графы . . 11
Введение 11
1.2. Геометрические графы 12
'.3. Абстрактные графы 14
.4. Изоморфизмы и реализации 16
.5. Термины, описывающие локальные свойства ... 19
.6, Маршруты, цепи и циклы 21
,7. Связность 24
.8. Деревья и леса 26
.9. Разделяющие множества и разрезы 29
.10. Некоторые специальные классы графов .... 32
Литература 35
Глава 2. Основные понятия: ориентированные графы , . 37
2.1. Введение 37
2.2. Ориентированные графы 37
2.3. Термины для описания локальной структуры , . , 40
2.4. Ориентированные маршруты, пути, и контуры ... ^1
2.5. Сильная связность .'.... 43
2.6. Деревья и разрезы 44
2.7. Ориентированные графы и бинарные отношения . , 46
ГлаваЗ. Разбиения и расстояния на графах 49
3.1. Введение . 49
3.2. Разбиения ребер 49
3.3. Разбиения дуг 54
3.4. Гамильтоновы цепи и циклы 61
3.5. Разбиения вершин 75
3.6. Радиус и диаметр 80
3 7. Задачи о минимальных расстояниях 82
Литература 89
Глава 4. Плоские и неплоские графы. Теорема о раскраске 90
4.1. Введение 90
4.2. Плоские графы 91
4.3. Дополнительный граф 108
4.4. Раскраска ребер графа 112
4.5. Раскраска граней и вершин. Задача о четырех красках 115
4.6. Графы и поверхности 127
Литература 133
Глава 5. Матричное представление графов 136
5.1. Введение 136
5.2. Матрица инцидепций 139
5.3. Матрица циклов 143
5.4. Матрица разрезов 144
5.5. Матрица смежности вершин 149
5.6. Матрица путей 157
5.7. Реализуемость матриц циклов и разрезов .... 158
5.8. Матрица графов и комбинаторная топология . . . i-oi
Литература 164
часть и.
ПРИЛОЖЕНИЯ ТЕОРИИ ГРАФОВ
Глава 6. Прикладные задачи теории графов '66
6.1. Введение 166
Приложения к экономике и исследованию
операций '"'
6.2. Экономика и снабжение 167
6.3. Линейное программирование и потоки в сетях . . '72
6.4. Задачи типа ПЕРТ 173
Комбинаторные задачи 183
6.5. Примеры комбинаторных задач в теории графов . . '83
6.6. Минимальное число аварий на кирпичном заводе . . '97
6.7. Минимальное число пересечений в полных графах . . 202
Головоломки к игры 205
6.8. Задача соединения раскрашенных кубов .... 205
6.9. Задачи изменения состояний системы 207
6.10. Матричная форма задачи о переправе . ... . 213
6.11. Задача деления треугольника 219
6.12. Игра двух лиц 220
6.13. Игры на шахматной доске 224
Паросочетания 226
6.14. Максимальные паросочетания 226
Технические приложения 238
6.15. Анализ технических систем 238
6.16. Сети связи 244
6.17. Граф потока сигналов 248
6.18. Переключательные сети (схемы) 254
6.19. Объединение электростанций в энергосистему . . 257
6.20. Печатные схемы 258
Естественные науки 269
6.21. Идентификация в химии 2jO
6.22. Простая модель нз органической химии . . . . 265
6.23. Два примера из статистической механики . . . 2о8
G.24. Генетическая задача 270
Задачи изучения человека и общества , 272
6.25. Графы и кибернетика 272
6.26. Применения в социологии 277
6.27. Математические модели разоружения .... 281
6.28. Лингвистика "... 284
Литература к разделу 6.28 2S9
Дополнительные приложения . . . . 289
6.29. Математические машины и цепи Маркова . . . 289
6.30. Группы и обыкновенные графы 295
6.31. Построение деревьев минимальной общей длины . 297
6.32. Графы и собственные значения неотрицательных
матриц 298
6.33. Задача ранжирования 300
Литература 304
Глава 7. Потоки в сетях 309
7.1. Введение 309
7.2. Основная терминология 309
7.3. Отношения между потоками и операции над ними . 313
7.4. Простые потоки 314
7.5. Другое представление потока 315
7.6. Потоки с ограничениями на дугах 318
7.7. Максимальный поток в транспортном сети . . . 325
7.8. Максимальные потоки в сетях общего вида с ограни-
ограниченными пропускными способностями дуг .... 327
7.9. Потоки минимальной стоимости 332
7.10. Некоторые специальные задачи о потоках . . . 338
7.11. Задачи о многопродуктовых потоках 349
7.12. Стохастические потоки в сетях 343
Литература 346
Ответы к упражнениям ," 348
Краткий терминологический словарь 352