Теорема о максимальном потоке и минимальном разрезе

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

Это частный случай теоремы двойственности для линейных программ , который можно использовать для вывода теоремы Менгера и теоремы Кёнига–Эгервари . ^[1]

Определения и утверждения

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

Сеть

Сеть состоит из

конечный ориентированный граф $N = (V, E)$ , где V обозначает конечное множество вершин, а $E \subseteq V \times V$ — множество направленных ребер;
источник $s$ $\in$ $V$ и сток $t$ $\in$ $V$ ;
функция пропускной способности , которая представляет собой отображение, обозначаемое как $c$ $uv$ или $c$ $($ $u$ $,$ $v$ $)$ для $($ $u$ $,$ $v$ $) \in$ $E$ . Она представляет собой максимальный объем потока, который может пройти через ребро. $c:E\to \mathbb {R} ^{+}$

Потоки

Поток через сеть — это отображение, обозначаемое как или , при соблюдении следующих двух ограничений: $f:E\to \mathbb {R} ^{+}$ $f_{uv}$ $f(u,v)$

Ограничение пропускной способности : для каждого ребра , $(u,v)\in E$ $f_{uv}\leq c_{uv}.$
Сохранение потоков : для каждой вершины, кроме и (т.е. источника и стока соответственно), выполняется следующее равенство: $v$ $с$ $т$
$\sum \nolimits _{\{u:(u,v)\in E\}}f_{uv}=\sum \nolimits _{\{w:(v,w)\in E\}}f_{vw}.$

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

Значение потока определяется как

|f|=\sum \nolimits _{\{v:(s,v)\in E\}}f_{sv}=\sum \nolimits _{\{v:(v,t)\in E\}}f_{vt},

где, как указано выше, является источником, а является стоком сети. В аналогии с жидкостью это представляет собой количество жидкости, поступающей в сеть в источнике. Из-за аксиомы сохранения для потоков это то же самое, что и количество потока, покидающего сеть в стоке. $с$ $т$

Задача о максимальном потоке требует наибольшего потока в заданной сети.

Задача о максимальном потоке. Максимизировать, то есть направить как можно больший поток изв. $|е|$ $с$ $т$

Порезы

Другая половина теоремы о максимальном потоке и минимальном разрезе относится к другому аспекту сети: набору разрезов. Разрез st $C = (S, T)$ — это разбиение $V$ такое, что $s \in S$ и $t \in T$ . То есть разрез s - t — это разделение вершин сети на две части, с источником в одной части и стоком в другой. Набор разрезов разреза $C$ — это набор ребер, которые соединяют исходную часть разреза с стоком: $X_{C}$

X_{C}:=\{(u,v)\in E\ :\ u\in S,v\in T\}=(S\times T)\cap E.

Таким образом, если удалить все ребра в разрезе $C$ , то положительный поток невозможен, поскольку в полученном графе нет пути от источника к стоку.

Пропускная способность разреза st равна сумме пропускных способностей ребер в его разрезе,

c(S,T)=\sum \nolimits _{(u,v)\in X_{C}}c_{uv}=\sum \nolimits _{(i,j)\in E}c_{ij}d_{ij},

где если и , в противном случае. $d_{ij}=1$ $i\in S$ $j\in T$ $0$

Обычно в графе много разрезов, но разрезы с меньшим весом зачастую сложнее найти.

Задача о минимальном разрезе st. Минимизировать

c (S, T)

, то есть определить

S

T

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

Основная теорема

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

Теорема о максимальном потоке и минимальном разрезе. Максимальное значение потока st равно минимальной пропускной способности по всем разрезам st.

Пример

На рисунке справа показан поток в сети. Цифровая аннотация на каждой стрелке в форме f / c указывает поток ( f ) и пропускную способность ( c ) стрелки. Потоки, исходящие из источника, в сумме составляют пять (2+3=5), как и потоки в сток (2+3=5), что устанавливает, что значение потока равно 5.

Один разрез s - t со значением 5 задается как S = { s , p } и T = { o , q , r , t }. Пропускные способности ребер, пересекающих этот разрез, равны 3 и 2, что дает пропускную способность разреза 3+2=5. (Стрелка от o к p не рассматривается, так как она указывает от T обратно к S .)

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

Обратите внимание, что поток через каждую из двух стрелок, соединяющих S и T, идет на полную мощность; так происходит всегда: минимальное сечение представляет собой «узкое место» системы.

Формулировка линейной программы

Задачу максимального потока и задачу минимального разреза можно сформулировать как две прямо-двойственные линейные задачи программирования . ^[2]

LP с максимальным потоком прост. Двойственный LP получается с помощью алгоритма, описанного в двойственной линейной программе : переменные и ограничения знака двойственного соответствуют ограничениям основного, а ограничения двойственного соответствуют переменным и ограничениям знака основного. Полученный LP требует некоторых пояснений. Интерпретация переменных в LP с минимальным разрезом такова:

d_{uv}={\begin{cases}1,&{\text{if }}u\in S{\text{ and }}v\in T{\text{ (край }}uv{\text{ находится в разрезе) }}\\0,&{\text{internally}}\end{cases}}

z_{v}={\begin{cases}1,&{\text{if}}v\in S\\0,&{\text{inotherwise}}\end{cases}}

Цель минимизации суммирует пропускную способность по всем ребрам, содержащимся в разрезе.

Ограничения гарантируют, что переменные действительно представляют собой законное сокращение: ^[3]

Ограничения (эквивалентные ) гарантируют, что для неконцевых узлов u,v , если u находится в S и v находится в T , то ребро ( u , v ) учитывается в разрезе ( ). $d_{uv}-z_{u}+z_{v}\geq 0$ $d_{uv}\geq z_{u}-z_{v}$ $d_{uv}\geq 1$
Ограничения (эквивалентные ) гарантируют, что если v принадлежит T , то ребро (s,v) учитывается в разрезе (так как s по определению принадлежит S ). $d_{sv}+z_{v}\geq 1$ $d_{sv}\geq 1-z_{v}$
Ограничения (эквивалентные ) гарантируют, что если u принадлежит S , то ребро (u,t) учитывается в разрезе (так как t по определению принадлежит T ). $d_{ut}-z_{u}\geq 0$ $d_{ut}\geq z_{u}$

Обратите внимание, что поскольку это задача минимизации, нам не нужно гарантировать, что ребро не находится в разрезе — нам нужно только гарантировать, что каждое ребро, которое должно находиться в разрезе, суммируется в целевой функции.

Равенство в теореме о максимальном потоке и минимальном разрезе следует из теоремы о сильной двойственности в линейном программировании , которая гласит, что если первичная программа имеет оптимальное решение x *, то двойственная программа также имеет оптимальное решение y *, такое, что оптимальные значения, образованные двумя решениями, равны.

Приложение

Теорема Седербаума о максимальном потоке

Задача максимального потока может быть сформулирована как максимизация электрического тока через сеть, состоящую из нелинейных резистивных элементов. ^[4] В этой формулировке предел тока $I$ $in$ между входными клеммами электрической сети, когда входное напряжение $V$ $in$ приближается к , равен весу набора разрезов минимального веса. $\infty$

\lim _{V_{\text{in}}\to \infty }(I_{in})=\min _{X_{C}}\sum _{(u,v)\in X_{C}}c_{uv}

Обобщенная теорема о максимальном потоке и минимальном разрезе

В дополнение к пропускной способности ребра, предположим, что в каждой вершине имеется пропускная способность, то есть отображение, обозначенное как $c$ $($ $v$ $)$ , такое, что поток $f$ должен удовлетворять не только ограничению пропускной способности и сохранению потоков, но также ограничению пропускной способности вершины $c:V\to \mathbb {R} ^{+}$

\forall v\in V\setminus \{s,t\}:\qquad \sum \nolimits _{\{u\in V\mid (u,v)\in E\}}f_{uv}\leq c(v).

Другими словами, объем потока, проходящего через вершину, не может превышать ее пропускную способность. Определим разрез st как множество вершин и ребер, таких, что для любого пути от s до t , путь содержит член разреза. В этом случае пропускная способность разреза равна сумме пропускной способности каждого ребра и вершины в нем.

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

Теорема Менгера

В задаче о неориентированных рёберно-непересекающихся путях нам дан неориентированный граф $G = (V, E)$ и две вершины $s$ и $t$ , и нам нужно найти максимальное количество рёберно-непересекающихся путей st в $G.$

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

Проблема выбора проекта

В задаче выбора проекта есть $n$ проектов и $m$ машин. Каждый проект $p i$ приносит доход $r (p i)$ , а каждая машина $q j$ стоит $c (q j)$ на покупку. Мы хотим выбрать подмножество проекта и купить подмножество машин, чтобы максимизировать общую прибыль (доход выбранных проектов за вычетом стоимости купленных машин). Мы должны соблюдать следующее ограничение: каждый проект определяет набор машин, которые должны быть куплены, если проект выбран. (Каждая машина, после покупки, может использоваться любым выбранным проектом.)

Чтобы решить задачу, пусть $P$ будет набором невыбранных проектов , а $Q$ — набором закупленных машин, тогда задачу можно сформулировать следующим образом:

\max\{g\}=\sum _{i}r(p_{i})-\sum _{p_{i}\in P}r(p_{i})-\sum _{q_{j}\in Q}c(q_{j}).

Поскольку первый член не зависит от выбора $P$ и $Q$ , эту задачу максимизации можно сформулировать как задачу минимизации, то есть:

\min\{g'\}=\sum _{p_{i}\in P}r(p_{i})+\sum _{q_{j}\in Q}c(q_{j}).

Вышеуказанная задача минимизации может быть сформулирована как задача минимального разреза путем построения сети, где источник соединен с проектами с емкостью $r (p i)$ , а сток соединен с машинами с емкостью $c (q j)$ . Ребро $(p i, q j)$ с бесконечной емкостью добавляется, если проект $p i$ требует машину $q j$ . Набор разрезов st представляет проекты и машины в $P$ и $Q$ соответственно. По теореме о максимальном потоке минимального разреза можно решить задачу как задачу максимального потока .

На рисунке справа представлена сетевая формулировка следующей задачи выбора проекта:

Минимальная мощность разреза st составляет 250, а сумма доходов каждого проекта составляет 450; следовательно, максимальная прибыль g составляет 450 − 250 = 200, при выборе проектов $p 2$ и $p 3$ .

Идея здесь заключается в том, чтобы «пропустить» прибыль каждого проекта через «трубы» его машин. Если мы не можем заполнить трубу из машины, то доход машины меньше ее стоимости, и алгоритм минимального разреза найдет более дешевым сократить границу прибыли проекта вместо границы стоимости машины.

Проблема сегментации изображения

В задаче сегментации изображения есть $n$ пикселей. Каждому пикселю $i$ можно присвоить значение переднего плана $f i$ или значение фона $b i$ . Существует штраф $p ij ,$ если пиксели $i, j$ являются смежными и имеют разные назначения. Задача состоит в том, чтобы присвоить пикселям передний план или фон таким образом, чтобы сумма их значений за вычетом штрафов была максимальной.

Пусть $P$ — набор пикселей, назначенных переднему плану, а $Q$ — набор точек, назначенных фону, тогда задачу можно сформулировать следующим образом:

\max\{g\}=\sum _{i\in P}f_{i}+\sum _{i\in Q}b_{i}-\sum _{i\in P,j\in Q\lor j\in P,i\in Q}p_{ij}.

Эту задачу максимизации можно сформулировать как задачу минимизации, то есть:

\min\{g'\}=\sum _{i\in P,j\in Q\lor j\in P,i\in Q}p_{ij}.

Вышеуказанная задача минимизации может быть сформулирована как задача минимального разреза путем построения сети, где источник (оранжевый узел) соединен со всеми пикселями с емкостью $f i$ , а сток (фиолетовый узел) соединен со всеми пикселями с емкостью $b i$ . Два ребра ( $i, j$ ) и ( $j, i$ ) с емкостью $p ij$ добавляются между двумя соседними пикселями. Затем st cut-set представляет пиксели, назначенные переднему плану в $P ,$ и пиксели, назначенные фону в $Q$ .

История

Отчет об открытии теоремы был дан Фордом и Фулкерсоном в 1962 году: ^[5]

«Определение максимального стационарного потока из одной точки в другую в сети, подверженной ограничениям пропускной способности дуг... было предложено авторам весной 1955 года Т. Э. Харрисом, который совместно с генералом Ф. С. Россом (в отставке) сформулировал упрощенную модель железнодорожного транспортного потока и обозначил эту конкретную проблему как центральную, предложенную моделью. Вскоре после этого был выдвинут и установлен главный результат — теорема 5.1, которую мы называем теоремой о максимальном потоке и минимальном разрезе. ^[6] С тех пор появилось множество доказательств». ^[7]^[8]^[9]

Доказательство

Пусть $G = (V, E)$ — сеть (направленный граф), где $s$ и $t$ являются источником и стоком $G$ соответственно.

Рассмотрим поток $f,$ вычисленный для $G$ с помощью алгоритма Форда–Фалкерсона . В остаточном графе $($ $G$ $f$ $),$ полученном для $G$ (после окончательного назначения потока с помощью алгоритма Форда–Фалкерсона ), определим два подмножества вершин следующим образом:

$A$ : множество вершин, достижимых из $s$ в $G f$
$A c$ : множество оставшихся вершин, т.е. $V - A$

Claim. $value(f) = c (A, A c)$ , где пропускная способность разреза st определяется как

c(S,T)=\sum \nolimits _{(u,v)\in S\times T}c_{uv}

Теперь мы знаем, что для любого подмножества вершин $A.$ Следовательно, для $value($ $f$ $) =$ $c$ $($ $A$ $,$ $A$ $c$ $)$ нам нужно: $value(f)=f_{out}(A)-f_{in}(A)$

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

Для доказательства вышеизложенного утверждения рассмотрим два случая:

В $G$ существует исходящее ребро, такое, что оно не насыщено, т. е. $f$ $($ $x$ $,$ $y$ $) <$ $c$ $xy$ . Это означает, что существует прямое ребро из $x$ в $y$ в $G$ $f$ , поэтому существует путь из $s$ в $y$ в $G$ $f$ , что является противоречием. Следовательно, любое исходящее ребро $($ $x$ $,$ $y$ $)$ полностью насыщено. $(x,y),x\in A,y\in A^{c}$

В $G$ существует входящее ребро, такое, что оно несет некоторый ненулевой поток, т. е. $f$ $($ $y$ $,$ $x$ $) > 0$ . Это подразумевает, что существует обратное ребро из $x$ в $y$ в $G$ $f$ , поэтому существует путь из $s$ в $y$ в $G$ $f$ , что снова является противоречием. Следовательно, любое входящее ребро $($ $y$ $,$ $x$ $)$ должно иметь нулевой поток. $(y,x),x\in A,y\in A^{c}$

Оба приведенных выше утверждения доказывают, что пропускная способность разреза, полученного описанным выше способом, равна потоку, полученному в сети. Кроме того, поток был получен с помощью алгоритма Форда-Фалкерсона , поэтому он также является максимальным потоком сети.

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

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

Смотрите также

Ссылки

^ Данциг, ГБ; Фулкерсон, Д.Р. (9 сентября 1964 г.). «О теореме о максимальном потоке и минимальном разрезе сетей» (PDF) . RAND Corporation : 13. Архивировано из оригинала (PDF) 5 мая 2018 г.
^ Тревизан, Лука. «Лекция 15 из CS261: Оптимизация» (PDF) .
^ Келлер, Оргад. «Презентация LP min-cut max-flow».
^ Cederbaum, I. (август 1962 г.). «Об оптимальной работе сетей связи». Журнал Института Франклина . 274 (2): 130–141. doi :10.1016/0016-0032(62)90401-5.
^ Л.Р. Форд-младший и Д.Р. Фулкерсон (1962) Потоки в сетях , стр. 1, Princeton University Press MR 0159700
^ LR Ford Jr. и DR Fulkerson (1956) «Максимальный поток через сеть», Canadian Journal of Mathematics 8: 399–404
^ P. Elias, A. Feinstein и CE Shannon (1956) "Заметка о максимальном потоке через сеть", IRE. Труды по теории информации, 2(4): 117–119
↑ Джордж Данциг и Д.Р. Фулкерсон (1956) «О теореме о максимальном потоке и минимальном разрезе сетей», в книге « Линейные неравенства » , Ann. Math. Studies, № 38, Принстон, Нью-Джерси
^ LR Ford & DR Fulkerson (1957) «Простой алгоритм для нахождения максимальных сетевых потоков и его применение к проблеме Хичкока», Canadian Journal of Mathematics 9: 210–18

Юджин Лоулер (2001). "4.5. Комбинаторные следствия теоремы о максимальном потоке и минимальном разрезе, 4.6. Интерпретация теоремы о максимальном потоке и минимальном разрезе с помощью линейного программирования". Комбинаторная оптимизация: сети и матроиды . Довер. стр. 117–120. ISBN 0-486-41453-1.
Христос Х. Пападимитриу , Кеннет Стейглиц (1998). "6.1 Теорема о максимальном потоке и минимальном разрезе". Комбинаторная оптимизация: алгоритмы и сложность . Довер. стр. 120–128. ISBN 0-486-40258-4.
Виджай В. Вазирани (2004). "12. Введение в LP-двойственность". Аппроксимационные алгоритмы . Springer. стр. 93–100. ISBN 3-540-65367-8.