Липский В. Комбинаторика для программистов. - М., 1988. - 200 с.
Первая глава книги содержит изложение классических разделов комбинаторики (перестановки, разбиения множеств и чисел, биномиальные коэффициенты, производящие функции, и т.д.), а также многие — необязательно классические — алгоритмы генерирования упомянутых комбинаторных объектов. Во второй главе представлены основные методы, используемые при конструировании алгоритмов на графах, в особенности методы систематичного обхода графов. В двух следующих главах обсуждаются методы нахождения кратчайших путей в графах и задача отыскания максимального потока в сети. В последней главе рассматривается применение комбинаторного понятия матроида для решения некоторого класса оптимизационных задач. Книга предназначена для программистов, желающих расширить свои знания в области комбинаторных алгоритмов, а также пополнить свои практические знания теоретическими. От читателя требуются элементарные сведения из математики, а также знакомство с языком программирования Паскаль.
Оглавление
0.1 Предисловие редактора перевода......................................2
0.2 От автора..................................................................3
1 Введение в комбинаторику.................................5
1.1 Основные понятия........................................................5
1.2 Функции и размещения..................................................10
1.3 Перестановки: разложение на циклы, знак перестановки..........13
1.4 Генерирование перестановок............................................19
1.5 Подмножества множества, множества с повторениями................29
1.6 k-элементные подмножества, биномиальные коэффициенты ...............34
1.7 Генерирование k-элементных подмножеств ..........................39
1.8 Разбиения множества....................................................43
1.9 Числа Стирлинга второго и первого рода............................45
1.10 Генерирование разбиений множества..................................50
1.11 Разбиения чисел..........................................................54
1.12 Производящие функции................................................58
1.13 Принцип включения и исключения....................................66
1.14 Задачи ....................................................................70
2 Алгоритмы на графах 79
2.1 Машинное представление графов......................................79
2.2 Поиск в глубину в графе................................................83
2.3 Поиск в ширину в графе................................................86
2.4 Стягивающие деревья (каркасы) ......................................89
2.5 Отыскание фундаментального множества циклов в графе .... 92
2.6 Нахождение компонент двусвязности..................................95
2.7 Эйлеровы пути............................................................99
2.8 Алгоритмы с возвратом (back-tracking) ..............................102
2.9 Задачи ....................................................................108
3 Нахождение кратчайших путей в графе 111
3.1 Начальные понятия......................................................112
3.2 Кратчайшие пути от фиксированной вершины......................114
3.3 Случай неотрицательных весов — алгоритм Дейкстры ............116
3.4 Пути в бесконтурном орграфе..........................................120
3.5 Кратчайшие пути между всеми парами вершин, транз.замыкание ....................................123
3.6 Задачи ....................................................................127
4 Потоки в сетях и родственные задачи 129
4.1 Максимальный поток в сети............................................129
4.2 Алгоритм построения максимального потока........................134
4.3 Наибольшие паросочетания в двудольных графах..................147
4.4 Системы различных представителей..................................156
4.5 Разложение на цепи......................................................164
4.6 Задачи ....................................................................170
5 Матроиды 174
5.1 Жадный алгоритм решения оптимизационных задач..............174
5.2 Матроиды и их основные свойства....................................176
5.3 Теорема Рамо-Эдмондса................................................181
5.4 Матричные матроиды....................................................183
5.5 Графовые матроиды ....................................................186
5.6 Матроиды трансверсалей................................................189
5.7 Задачи ....................................................................192
