Разработка и анализ алгоритма для циркуляций
Как выясняется, задача поиска действительной циркуляции с уровнями потребле- ния {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
- § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
- § 2.ФУНКЦИИ МЕТОДОЛОГИИ В РАЗРАБОТКЕ МЕТОДИК АНАЛИЗА СОЦИАЛЬНЫХ ФАКТОВ
- Общие признаки нарушения циркуляции энергии в канале
- Тексты для анализа
- Тексты для анализа
- Тексты для анализа
- Тексты для анализа
- Тексты для анализа
- Тексты для анализа
- Тексты для анализа
- Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
- Таблица контент-критериев для анализа показаний
- АЛГОРИТМ
- АЛГОРИТМ УДАЧИ
- Алгоритм исцеления:
- Алгоритм избавления от боли
- 2. Специфика и алгоритмы работы с источниками.
- Алгоритм обработки результатов.