Расширения задачи о максимальном потоке - Нахождение потока в сети

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

Двудольные паросочетания — первое естественное практическое применение задачи в этом направлении; в следующих разделах рассматриваются и другие применения. На первых порах мы сохраним представление о потоке как об абстрактном “трафике” и будем искать более общие условия, которым этот трафик может подчиняться. Как выясняется, эти более общие условия могут принести пользу в будущем.

В частности, особое внимание будет уделено двум обобщениям задачи о максимальном потоке. Вы увидите, что оба случая приводятся к базовой задаче о максимальном потоке.

Задача: циркуляция с потреблением

Одна из упрощающих особенностей исходной формулировки задачи о максимальном потоке заключалась в том, что графе содержал только один источник s и один сток t. Теперь предположим, что в графе присутствует множество S источников, генерирующих поток, и множество T стоков, поглощающих поток. Как и прежде, каждое ребро обладает целочисленной пропускной способностью.

С несколькими источниками и стоками не совсем понятно, как решить, какому из источников или стоков следует отдать предпочтение в задаче максимизации. Вместо того чтобы максимизировать величину потока, мы рассмотрим ситуацию, в которой источники имеют фиксированную величину поставки, а стоки — фиксированную величину потребления, а наша цель заключается в передаче потока от узлов со свободной поставкой к узлам с заданным потреблением. Представьте, например, что сеть представление систему дорог или железнодорожных линий, которая используется для поставки товаров с фабрик (поставка) в торговые точки (потребление). В такой постановке задачи нас будет интересовать не максимизация конкретной величины, а удовлетворение всего спроса с использованием доступной поставки.

Следовательно, мы имеем потоковую сеть G = (V, E) с пропускными способностями ребер. С каждым узлом v ∈ V связывается уровень потребления d_v. Если d_v > 0, значит, узел v потребляет d_vединиц потока; узел выполняет функции стока и желает получать на d_v единиц больше потока, чем отправлять далее. Если d_v < 0, значит v имеет уровень потребления -d_v; он является источником, и хочет отправлять на -d_v единиц потока больше, чем получает. Если d_v = 0, то узел v не является ни источником, ни стоком. Будем считать, что все пропускные способности и уровни потребления являются целыми числами.

Обозначим S множество всех узлов с отрицательным потреблением, и T — множество всех узлов с положительным потреблением. Хотя узел v в S хочет передавать больше потока, чем получает, он может иметь поток по входящим ребрам; он будет компенсироваться потоком из v по выходящим ребрам. Сказанное относится (в противоположном направлении) и к множеству T.

Рис. 7.13. a — экземпляр задачи о циркуляции с решением: в узлах указаны уровни потребления; на ребрах — пропускные способности и величины потока, а в прямоугольниках — величины потока; b — результат преобразования этого экземпляра в эквивалентный экземпляр задачи о максимальном потоке

В этой ситуации циркуляцией с потреблением {d_v} называется функция f, которая связывает с каждым ребром неотрицательное вещественное число и удовлетворяет следующим двум условиям:

♦ (i) (Ограничения пропускной способности) Для всех e ∈ E выполняется условие 0 ≤ f(e) ≤ c_e.

♦ (ii) (Ограничения сохранения потока) Для каждого узла v ∈ V выполняется условие v, fⁱⁿ(v) - f^out(v) = d_v.

Сейчас вместо задачи максимизации нас интересует задача существования: требуется узнать, существует ли действительная циркуляция (то есть циркуляция, удовлетворяющая условиям (i) и (ii)).

Для примера рассмотрим экземпляр задачи на рис. 7.13, а. На этой схеме два узла являются источниками (уровни потребления -3 и -3); два узла являются стоками, с уровнями потребления 2 и 4. Величины потока на схеме образуют действительную циркуляцию, так как все уровни потребления удовлетворяются в соответствии с пропускными способностями.

Если рассмотреть произвольный экземпляр задачи о циркуляции, существует простое условие, которое должно выполняться для существования действительной циркуляции: суммарная поставка должна быть равна суммарному потреблению.

(7.49) Если существует действительная циркуляция с потреблением {d}, то

Доказательство. Допустим, действительная циркуляция f существует. Тогда В последнем выражении величина f(e) для каждого ребра е = (u, v) подсчитывается дважды: в f^out(u) и в fⁱⁿ(v). Эти два слагаемых компенсируются; а поскольку это происходит для всех величин f(e), общая сумма равна 0. ■

Из (7.49) известно, что

Обозначим эту величину D.

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

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

Рис. 7.14. Сведение задачи о циркуляции к задаче о максимальном потоке

Преобразование очень похоже на то, которое использовалось в задаче о двудольном паросочетании: каждый узел в S связывается с “суперисточником” s*, а каждый узел в T — с “суперстоком” t. А конкретнее, граф G' строится на основе G добавлением в него новых узлов s* и t*. Для каждого узла v ∈ T — то есть для каждого узла v с d_v > 0 — добавляется ребро (v, t*) с пропускной способностью d_v. Для каждого узла u ∈ S — то есть для каждого узла с d_u < 0 — добавляется ребро (s*, u) с пропускной способностью - d_u. Остальная структура G переносится в G' без изменений.

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

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

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

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

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

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

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

Задача: циркуляция с потреблением и нижние границы

Наконец, немного обобщим приведенную задачу. Во многих ситуациях требуется не только обеспечить потребление в разных узлах, но и заставить поток использовать некоторые ребра. Для этого можно установить для ребер нижние границы наряду с обычными верхними границами, определяемыми пропускными способностями ребер.

Рассмотрим потоковую сеть G = (V, Е) с пропускной способностью с_е и нижней границейl_e для каждого ребра е. Будем считать, что 0 ≤ l_e ≤ с_е для всех е. Как и прежде, каждому узлу v также назначен уровень потребление d_v, который может быть как положительным, так и отрицательным. Предполагается, что все уровни потребления, пропускные способности и нижние границы являются целыми числами.

Основные величины имеют тот же смысл, что и прежде, а нижняя граница l_e означает, что величина потока через е должна быть не меньше l_e. Таким образом, циркуляция в потоковой сети должна удовлетворять следующим двум условиям.

(i) (Ограничения пропускной способности.) Для всех е ∈ Е выполняется условие l_e ≤ f(е) ≤ с_e.

(ii) (Ограничения уровня потребления.) Для всех v ∈ V выполняется условие fⁱⁿ(v) – f^out(v) = d_v.

Как и прежде, требуется решить, существует ли действительная циркуляция — то есть циркуляция, удовлетворяющая этим требованиям.

Разработка и анализ алгоритма с нижними границами

Наша стратегия заключается в сведении этой задачи к задаче нахождения циркуляции с уровнями потребления, но без нижних границ. (Как вы уже видели, последняя задача может быть сведена к стандартной задаче о максимальном потоке.) Идея заключается в следующем: мы знаем, что по каждому ребру е необходимо передавать как минимум l_e единиц потока. Предположим, исходная циркуляция f₀ определяется просто как f₀(e) = l_e. f₀ удовлетворяет всем ограничениям пропускной способности (для нижних и верхних границ), но, вероятно, не удовлетворяет всем ограничениям потребления. В частности,

Обозначим эту величину L_v. Если L_v = d_v, то ограничение потребления для v выполняется, а если нет — нужно наложить поверх f₀ циркуляцию f₁, которая исправит “дисбаланс” в v. Следовательно, потребуется f₁ⁱⁿ(v) – f₁^out(v) = d_v – L_v. И какой пропускной способностью мы для этого располагаем? По каждому ребру уже передаются l_e, единиц потока, поэтому для использования доступны еще с_e — l_e единиц.

Эти соображения заложены в основу следующего построения. Пусть граф G' состоит из тех же узлов и ребер с пропускными способностями и уровнями потребления, но без нижних границ. Пропускная способность ребра е будет равна с_e — l_e. Уровень потребления узла v будет равен d_v — L_v.

Например, возьмем экземпляр графа на рис. 7.15(a). Перед вами тот же экземпляр, который был показан на рис. 7.13, но на этот раз одному из ребер назначена нижняя граница 2. В части bэта нижняя граница устраняется, что приводит к снижению верхней границы для ребра и изменению потребления на двух концах ребра. В процессе становится ясно, что действительной циркуляции не существует, так как после применения этой конструкции появляется узел с уровнем потребления -5 и только 4 единицами пропускной способности на выходящих ребрах.

Утверждается, что наша общая конструкция создает эквивалентный экземпляр задачи с уровнями потребности, но без нижних границ; к этой задаче можно применить общий алгоритм.

Рис. 7.15. a — экземпляр задачи о циркуляции с нижними границами: числа в узлах — уровни потребности, числа у ребер — пропускные способности. Одному из ребер назначается нижняя граница 2; b — результат преобразования этого элемента в эквивалентный экземпляр задачи о циркуляции без нижних границ

(7.52) Действительная циркуляция в G существует в том и только в том случае, если существует действительная циркуляция в G'. Если все уровни потребления, пропускные способности и нижние границы в G являются целыми числами и существует действительная циркуляция, то эта действительная циркуляция является целочисленной.

Доказательство. Сначала предположим, что в G' существует циркуляция f'. Определим циркуляцию f в G по формуле f(e) = f'(e) + l_e. В этом случае f удовлетворяет ограничениям пропускной способности в G, и

поэтому также выполняются ограничения потребления в G.

И наоборот, предположим, что в G существует циркуляция f и определим в G' циркуляцию f' по формуле f'(e) = f(e) — l_e. В этом случае f' удовлетворяет ограничениям пропускной способности в G' и

поэтому также выполняются ограничения потребления в G'.