Предисловие редактора перевода 5
От автора 7
1. Введение в комбинаторику 9
1.1. Основные понятия 9
1.2. Функции и размещения 14
1.3. Перестановки: разложение на циклы, знак перестановки 17
1.4. Генерирование перестановок 24
1.5. Подмножества множества, множества с повторениями, генерирование подмножеств множества 34
1.6. k-элементные подмножества, биномиальные коэффициенты .... 39
1.7. Генерирование k-элементных подмножеств 45
1.8. Разбиения множества 48
1.9. Числа Стирлинга второго и первого рода 50
1.10. Генерирование разбиений множества 55
1.11. Разбиения чисел 60
1.12. Производящие функции 64
1.13. Принцип включения и исключения 72
1.14. Задачи 76
2. Алгоритмы на графах 84
2.1. Машинное представление графов 84
2.2. Поиск в глубину в графе 88
2.3. Поиск в ширину в графе 92
2.4. Стягивающие деревья (каркасы) 94
2.5. Отыскание фундаментального множества циклов в графе 98
2.6. Нахождение компонент двусвязности 101
2.7. Эйлеровы пути 106
2 8. Алгоритмы с возвратом 108
2.9. Задачи 114
3. Нахождение кратчайших путей в графе 119
3.1. Начальные понятия 119
3.2. Кратчайшие пути от фиксированной вершины 121
3.3. Случай неотрицательных весов — алгоритм Дейкстры 124
3.4. Пути в бесконтурном графе 127
3.5. Кратчайшие пути между всеми парами вершин, транзитивное замыкание отношения 130
3.6. Задачи 134
4. Потоки в сетях и родственные задачи 136
4.1. Максимальный поток в сети 136
4.2. Алгоритм построения максимального потока 141
4.3. Наибольшие паросочетания в двудольных графах 154
4.4. Системы различных представителей 163
4.5. Разложение на цепи 172
4.6. Задачи 178
5. Матроиды 183
5.1. Жадные алгоритмы решения оптимизационных задач 183
5.2. Матроиды и их основные свойства 185
5.3. Теорема Радо — Эдмондса 190
5.4. Матричные матроиды 193
5.5. Графовые матроиды 195
5.6. Матроиды трансверсалей 199
5.7. Задачи 202
Литература 205
Указатель 203