Разработка алгоритма

Граф, определяющий задачу паросочетаний, не направлен, тогда как потоковые сети являются направленными; тем не менее алгоритм задачи нахождения максималь- ного потока легко адаптируется для нахождения максимального паросочетания.

Начиная с графа G в экземпляре задачи о двудольном паросочетании, мы по- строим потоковую сеть G' так, как показано на рис. 7.9. Сначала все ребра из G будут направлены из X в Y. Затем мы добавим узел 5 и ребро (5, х) из s в каждый узел X. Далее добавляется узел t и ребро (у, t) из каждого узла из Y в t. Наконец, каждому ребру в G' назначается пропускная способность 1.

Рис. 7.9. a — двудольный граф; b — соответствующая потоковая сеть, в которой все пропускные способности ребер равны 1


После этого вычисляется максимальный поток s-t в этой сети G'. Как выясня- ется, величина этого максимального потока равна размеру максимального паросо- четания в G. Кроме того, из анализа становится видно, как использовать сам поток для получения паросочетания.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Разработка алгоритма:

  1. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  2. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  3. АЛГОРИТМ
  4. АЛГОРИТМ УДАЧИ
  5. Алгоритм исцеления:
  6. Алгоритм избавления от боли
  7. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  8. Алгоритм обработки результатов.
  9. 2. Специфика и алгоритмы работы с источниками.
  10. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.