загрузка...

АЛГОРИТМЫ - Разработка и применение - 2016 год

Глава 7. Нахождение потока в сети

7.7. Расширения задачи о максимальном потоке

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

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

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

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

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

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

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

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

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

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

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

♦ (ii) (Ограничения сохранения потока) Для каждого узла v ∈ V выполняется условие v, fin(v) - fout(v) = dv.

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

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

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

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

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

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

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

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

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

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

Преобразование очень похоже на то, которое использовалось в задаче о двудольном паросочетании: каждый узел в S связывается с «суперисточником» s*, а каждый узел в T — с «суперстоком» t. А конкретнее, граф G' строится на основе G добавлением в него новых узлов s* и t*. Для каждого узла v T — то есть для каждого узла v с dv > 0 — добавляется ребро (v, t*) с пропускной способностью dv. Для каждого узла u 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* и каждое ребро, входящее в t*, полностью насыщено потоком. Таким образом, при удалении этих ребер мы получим циркуляцию в G с fin(v) — fout(v) = d, для каждого узла 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)

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

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

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

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

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

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

(ii) (Ограничения уровня потребления.) Для всех v ∈ V выполняется условие fin(v) – fout(v) = dv.

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

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

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

Обозначим эту величину Lv. Если Lv = dv, то ограничение потребления для v выполняется, а если нет — нужно наложить поверх f0 циркуляцию f1, которая исправит «дисбаланс» в v. Следовательно, потребуется f1in(v) – f1out(v) = dv – Lv. И какой пропускной способностью мы для этого располагаем? По каждому ребру уже передаются le, единиц потока, поэтому для использования доступны еще сele единиц.

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

Например, возьмем экземпляр графа на рис. 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) + le. В этом случае f удовлетворяет ограничениям пропускной способности в G, и

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

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

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





загрузка...

загрузка...