Липский В. Комбинаторика для программистов

Перевод с польск. В.А. Евстигнеева, О.А. Логиновой. — Под ред. А.П. Ершова. — М.: Мир, 1988. — 200 с.В настоящей книге представлены некоторые разделы комбинаторики, причем особое внимание уделено конструктивному алгоритмическому подходу - рядом с обсуждаемыми комбинаторными проблемами, как правило, приводятся алгоритмы их решения вместе с анализом их вычислительной сложности. Эти алгоритмы представляют собой сжатые варианты программ, написанных на языке Паскаль. Первая, самая большая глава данной книги содержит изложение наиболее классических разделов комбинаторики (перестановки, разбиение множеств и чисел, биномиальные коэффициенты, производящие функции, и т.д.), а также многие - необязательно классические - алгоритмы генерирования упомянутых комбинаторных объектов. Во второй главе представлены основные методы, используемые при конструировании алгоритмов на графах, в особенности методы систематического обхода графов. Тематика, связанная с графами, затрагивается и в двух следующих главах: в одной из них обсуждаются метода нахождения кратчайших путей в графах, ребрам которых приписаны произвольные "длины", в другой - основное внимание сконцентрировано на задаче отыскания максимального потока в сети (т.е. в графе с определенными "пропускными способностями" ребер). В последней главе рассматривается применение комбинаторного понятия матроида для решения некоторого класса оптимизационных задач.Предисловие редактора перевода.
От автора.
Введение в комбинаторику.
Основные понятия.
Функции и размещения.
Перестановки: разложение на циклы, знак перестановки.
Генерирование перестановок.
Подмножества множества, множества с повторениями.
k-элементные подмножества, биномиальные коэффициенты.
Генерирование k-элементных подмножеств.
Разбиения множества.
Числа Стирлинга второго и первого рода.
Генерирование разбиений множества.
Разбиения чисел.
Производящие функции.
Принцип включения и исключения.
Задачи.
Алгоритмы на графах.
Машинное представление графов.
Поиск в глубину в графе.
Поиск в ширину в графе.
Стягивающие деревья (каркасы).
Отыскание фундаментального множества циклов в графе.
Нахождение компонент двусвязности.
Эйлеровы пути.
Алгоритмы с возвратом (back-tracking).
Задачи.
Нахождение кратчайших путей в графе.
Начальные понятия.
Кратчайшие пути от фиксированной вершины.
Случай неотрицательных весов — алгоритм Дейкстры.
Пути в бесконтурном орграфе.
Кратчайшие пути между всеми парами вершин, транз. замыкание.
Задачи.
Потоки в сетях и родственные задачи.
Максимальный поток в сети.
Алгоритм построения максимального потока.
Найбольшие паросочетания в двудольных графах.
Системы различных представителей.
Разложение на цепи.
Задачи.
Матроиды.
Жадный алгоритм решения оптимизационных задач.
Матроиды и их основные свойства.
Теорема Рамо-Эдмондса.
Матричные матроиды.
Графовые матроиды.
Матроиды трансверсалей.
Задачи.