Книга польского специалиста по программированию знакомит читателей с
широким спектром комбинаторных и теоретико-графовых алгоритмов.
Описание постановка алгоритмов задачи дано на языке Паскаль
В настоящей книге представлены некоторые разделы комбинаторики, причем особое внимание уделено конструктивному алгоритмическому подходу - рядом с обсуждаемыми комбинаторными проблемами, как правило, приводятся алгоритмы их решения вместе с анализом их вычислительной сложности.
Эти алгоритмы представляют собой сжатые варианты программ, написанных на языке Паскаль. На выбор обсуждаемых проблем, в большой мере случайный, принимая во внимание ограниченный объем книги, а также обширность рассматриваемой области, оказали влияние как интересы автора, так и желание скорей дополнить, нежели продублировать две другие книги с родственной тематикой.
Первая, самая большая глава данной книги содержит изложение наиболее классических разделов комбинаторики (перестановки, разбиения множеств и чисел, биномиальные коэффициенты, производящие функции, и т.д.), а также
многие — необязательно классические — алгоритмы генерирования упомянутых комбинаторных объектов. Во второй главе представлены основные методы, используемые при конструировании алгоритмов на графах, в особенности методы систематичного обхода графов. Тематика, связанная с графами, затрагивается и в двух следующих главах: в одной из них обсуждаются метода нахождения кратчайших путей в графах, ребрам которых приписаны произвольные «длины», в другой — основное внимание сконцентрировано на задаче отыскания максимального потока в сети (т.е. в графе с определенными «пропускными способностями» ребер). В последней главе рассматривается применение комбинаторного понятия матроида для решения некоторого класса оптимизационных
задач.
Книга предназначена для программистов, желающих расширить свои знания в области комбинаторных алгоритмов, а также пополнить свои практические знания теоретическими. От читателя требуются элементарные сведения из
математики, а также знакомство с языком программирования Паскаль.
и некоторый опыт программирования на языке высокого уровня.
Author(s): Липский В
Publisher: Мир
Year: 1988
Language: Russian
Pages: 212
City: Москва
Предисловие редактора перевода 5
От автора 7
1. Введение в комбинаторику 9
1.1. Основные понятия 9
1.2. Функции и размещения 14
1.3. Перестановки: разложение на циклы, знак перестановки 17
1.4. Генерирование перестановок 24
1.5. Подмножества множества, множества с повторениями, генерирование подмножеств множества 34
1.6. A-элементные подмножества, биномиальные коэффициенты 39
1.7. Генерирование A-элементных подмножеств 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. Эйлеровы пути . . . 1 0 6
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
Указатель 208
