Разработка и анализ алгоритма для циркуляций


Как выясняется, задача поиска действительной циркуляции с уровнями потребле- ния {dv} сводится к задаче нахождения максимального потока s-t в другой сети, как показано на рис.
7.14.

Преобразование очень похоже на то, которое использовалось в задаче о дву- дольном паросочетании: каждый узел в S связывается с «суперисточником» s*, а каждый узел в T — с «суперстоком» t. А конкретнее, граф G' строится на осно- ве G добавлением в него новых узлов s* и t*. Для каждого узла v 0 — добавляется ребро (v,t*) с пропускной способностью dv. Для каждого узла и S — то есть для каждого узла с du < 0 — добавляется ребро

(s*, u) с пропускной способностью -du. Остальная структура G переносится в G' без изменений.

В графе G' мы будем искать максимальный поток s*-t*. На интуитивном уровне это преобразование можно рассматривать как добавление узла s* «поставляющего» всем источникам их дополнительный поток, и узла t* «сливающего» лишний поток из стоков. Так, в части (b) рис. 7.13 показан результат применения этого преобра- зования к экземпляру из части (a).

Обратите внимание: в G' не может быть потока s*-t* с величиной больше D, поскольку разрез (A, B) c A = {s*| имеет пропускную способность D. Далее, если в G существует действительная циркуляция f с уровнями потребления {dv}, то отправляя величину потока -dv по каждому ребру (s*, v) и величину потока dv по каждому ребру (v,t*), мы получим в G' поток s*-t* с величиной D, который является максимальным. И наоборот, предположим, что в G' существует (максимальный) поток s*-t* с величиной D. При этом каждое ребро, выходящее из s* и каждое ре- бро, входящее в f, полностью насыщено потоком. Таким образом, при удалении

этих ребер мы получим циркуляцию в G с /в(v) — /™(v) = f/п для каждого узла v.

Кроме того, если в G' существует поток с величиной D, то этот поток содержит целочисленные значения.

Итак, мы доказали следующее:

(7.50) Действительная циркуляция с уровнями потребления {dv} в G суще- ствует в том и только в том случае, если максимальный поток s*-t* в G' имеет величину D. Если все пропускные способности и уровни потребления в G заданы целыми числами и существует действительная циркуляция, то эта действительная циркуляция является целочисленной.

В конце раздела 7.5 теорема о максимальном потоке и минимальном разрезе использовалась для получения характеристики (7.40) двудольных графов, не име- ющих идеального паросочетания. Аналогичную характеристику можно определить и для графов, не имеющих действительной циркуляции. В этой характеристике используется понятие разреза, адаптированное для текущей ситуации. В контексте задачи циркуляции с потреблением разрезом (A, B) называется разбиение множе- ства узлов V на два подмножества без каких-либо ограничений относительно того, на какой стороне разбиения окажутся источники и стоки. Мы приводим характе- ристику без доказательства.

(7.51) Граф G имеет действительную циркуляцию с уровнями потребления {dv} в том и только том случае, если для всех разрезов (A, B)

Важно заметить, что в нашей сети существует только один «тип» потока. Хотя поток поступает из нескольких источников и поглощается несколькими стоками, мы не можем установить ограничения относительно того, какой источник будет поставлять поток тому или иному стоку; это решает алгоритм. В более сложной задаче многопродуктового потока сток t. должен получать поток, поставляемый источником s. для всех i. Эта тема более подробно рассматривается в главе 11.

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

Еще по теме Разработка и анализ алгоритма для циркуляций:

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