|
Оглавление
Предисловие редактора перевода................ 5 От автора.........................7 1. Введение в комбинаторику................. 9 1.1. Основные понятия................... 9 1.2. Функции и размещения.................. 14 1.3. Перестановки: разложение на циклы, знак перестановки..... 17 1.4. Генерирование перестановок................ 24 1.5. Подмножества множества, множества с повторениями, генерирование подмножеств множества................ 34 1.6. 6-элементные подмножества, биномиальные коэффициенты.... 39 1.7. Генерирование й-элементных подмножеств........... 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
|