М, Мир., 1988 г.
Первая глава данной книги содержит изложение наиболее классических разделов комбинаторики (перестановки, разбиения множеств и чисел, биномиальные коэффициенты, производящие функции, и т.д.), а также многие — необязательно классические — алгоритмы генерирования упомянутых комбинаторных объектов. Во второй главе представлены основные методы, используемые при конструировании алгоритмов на графах, в особенности методы систематического обхода графов. Тематика, связанная с графами, затрагивается и в двух следующих главах: в одной из них обсуждаются метода нахождения кратчайших путей в графах, ребрам которых приписали произвольные «длины», в другой — основное внимание сконцентрировано на задаче отыскания максимального потока в сети (т.е., в графе с определенными «пропускными способностями» ребер). В последней главе рассматривается применение комбинаторного понятия матроида для решения некоторого класса оптимизационных задач.
Первая глава данной книги содержит изложение наиболее классических разделов комбинаторики (перестановки, разбиения множеств и чисел, биномиальные коэффициенты, производящие функции, и т.д.), а также многие — необязательно классические — алгоритмы генерирования упомянутых комбинаторных объектов. Во второй главе представлены основные методы, используемые при конструировании алгоритмов на графах, в особенности методы систематического обхода графов. Тематика, связанная с графами, затрагивается и в двух следующих главах: в одной из них обсуждаются метода нахождения кратчайших путей в графах, ребрам которых приписали произвольные «длины», в другой — основное внимание сконцентрировано на задаче отыскания максимального потока в сети (т.е., в графе с определенными «пропускными способностями» ребер). В последней главе рассматривается применение комбинаторного понятия матроида для решения некоторого класса оптимизационных задач.