Глава I. Первое знакомство с графами
§ 1. Задачи, приводящие к графам б
§ 2. Некоторые основные понятия теории графов 10
1. Полный граф. Дополнение графа —.
2. Степень вершины 11
3. Путь в графе. Цикл 16
4. Связность графа 17
5. Операция удаления ребра. Мост « . . 19
§ 3. Деревья. Лес 21
§ 4. Изображение графа 24
Глава II. Плоские графы
1. Представление о плоском графе 28
2. Формула Эйлера 31
3. Триангулированный граф 33
4. Изображение ребер плоского графа прямолинейными отрезками 34
5. Эйлеровы графы 37
6. Лабиринты 42
7. Гамильтоновы циклы и пути в графах 44
Глава III. Графы с цветными ребрами
1. Свойства полных графов с цветными ребрами 51
2. Графы помогают решать задачи 56
3. Задача о несцепленных треугольниках с одноцветными сторонами . • 59
Глава IV. Ориентированные графы
Г. Исходные понятия 62
2. Полный ориентированный граф 64
1. Круговые бескомпромиссные турниры 65
2. Парадоксы «голосования с предпочтением» 67
Глава V. Отношения
1. Квадрат множества # 71
2. Свойства отношений 74
1. Рефлексивность —
2. Антирефлексивность ♦ 75
3. Симметричность ... * * 76
4. Антисимметричность 77
5. Транзитивность 78
6. Антитранзитивность 79
7. Полное отношение • ♦ 80
3. Отношение эквивалентности 83
4. Отношение порядка 84
5. Определение графа 88
Глава VI. Деревья в работе
1. Деревья и подсчет числа изомеров 90
2. Число деревьев с пронумерованными вершинами 93
3. Отыскание кратчайшего пути 94
4. Деревья в комбинаторике 96
1. Деревья и перестановки из п элементов —
2. Маршруты по местности и число сочетаний СЈ 97
3. Разбиения и композиции натуральных чисел 98
5* Деревья, вероятность, генетика 101
6. Крестики и нолики 103
Глава VII. Сетевое планирование и управление
1. Сетевой график 105
2. Построение сетевого графика 110
3» Критический путь 115
4. О резервах времени 119
5. Из истории систем сетевого планирования и управления 123
Глава VIII. Графы и матрицы
§ 1. Матрицы графа 125
§ 2. Операции над матрицами 127
Что читать дальше 131
Ответы и указания 135