Теорема о максимальном расходе и минимальном разрезе

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

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

Определения и утверждения [ править ]

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

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

Пусть $N = (V, E)$ - ориентированный граф , где V обозначает множество вершин, а E - множество ребер. Пусть $s \in V$ и $t \in V$ - источник и сток $N$ соответственно.

Емкость ребра отображение обозначается $гр$ $уф$ или $с$ $($ $U$ $,$ $V$ $)$ , где $U$ $,$ $V$ $\in$ $V$ . Он представляет собой максимальный поток, который может пройти через край. ${\ displaystyle c: E \ to \ mathbb {R} ^ {+}}$

Потоки [ править ]

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

Емкость Constraint : Для каждого ребра , ${\ displaystyle (u, v) \ in E}$ ${\ displaystyle f_ {uv} \ leq c_ {uv}.}$
Сохранение потоков : для каждой вершины, кроме и (т.е. источника и стока , соответственно), выполняется следующее равенство: ${\ displaystyle v}$ ${\ displaystyle s}$ ${\ displaystyle t}$
$\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},

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

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

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

Сокращения [ править ]

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

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

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

Емкости из м разреза является общим весом его ребер,

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$

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

Проблема с минимальным срезом. Минимизируйте

c (S, T)

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

S

и

T

так, чтобы емкость ST-разреза была минимальной.

Основная теорема [ править ]

Основная теорема связывает максимальный поток через сеть с минимальным разрезом сети.

Теорема о максимальном потоке и минимальном разрезе. Максимальное значение первого потока равно минимальной производительности по всем проходам.

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

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

	Максимальный расход (Primal)	Мин-вырез (двойной)
переменные	$f_{uv}$ $\forall (u,v)\in E$ [переменная для каждого края]	$d_{uv}$ $\forall (u,v)\in E$ [переменная для каждого края] $z_{v}$ $\forall v\in V\setminus \{s,t\}$ [переменная для нетерминального узла]
цель	максимизировать $\sum \nolimits _{v:(s,v)\in E}f_{sv}$ [максимальный общий поток из источника]	свести к минимуму $\sum \nolimits _{(u,v)\in E}c_{uv}d_{uv}$ [минимальная общая вместимость кромок в разрезе]
ограничения	при условии ${\begin{aligned}f_{uv}&\leq c_{uv}&&\forall (u,v)\in E\\\sum _{u}f_{uv}-\sum _{w}f_{vw}&=0&&v\in V\setminus \{s,t\}\end{aligned}}$ [ограничение для каждого ребра и ограничение для нетерминального узла]	при условии ${\begin{aligned}d_{uv}-z_{u}+z_{v}&\geq 0&&\forall (u,v)\in E,u\neq s,v\neq t\\d_{sv}+z_{v}&\geq 1&&\forall (s,v)\in E\\d_{ut}-z_{u}&\geq 0&&\forall (u,t)\in E\\\end{aligned}}$ [ограничение на край]
знаковые ограничения	${\begin{aligned}f_{uv}&\geq 0&&\forall (u,v)\in E\\\end{aligned}}$	${\begin{aligned}d_{uv}&\geq 0&&\forall (u,v)\in E\\z_{v}&\in \mathbb {R} &&\forall v\in V\setminus \{s,t\}\end{aligned}}$

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

d_{uv}={\begin{cases}1,&{\text{if }}u\in S{\text{ and }}v\in T{\text{ (the edge }}uv{\text{ is in the cut) }}\\0,&{\text{otherwise}}\end{cases}}

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

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

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

Ограничения (эквивалентные ) гарантируют, что для нетерминальных узлов u, v , если u находится в S, а v находится в T , то ребро ( u , v ) засчитывается в cut ( ). $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 *, такое как что оптимальные значения, образованные двумя решениями, равны.

Пример [ править ]

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

На рисунке справа изображена сеть, имеющая значение расхода 7. Цифровая аннотация на каждой стрелке в форме x / y указывает расход ( x ) и пропускную способность ( y ). Всего семь потоков, исходящих из источника (4 + 3 = 7), как и потоков в сток (3 + 4 = 7).

Вершины, отмеченные белым цветом, и вершины, отмеченные серым, образуют подмножества $S$ и $T$ st разреза, множество разрезов которого содержит штриховые ребра. Поскольку пропускная способность первого прохода равна 7, что равняется значению потока, теорема о максимальном потоке и минимальном отрезке указывает, что значение потока и пропускная способность первого прохода оптимальны в этой сети.

Обратите внимание, что поток через каждую из пунктирных кромок идет на полную мощность: это «узкое место» системы. Напротив, в правой части сети есть резервные мощности. В частности, поток от узла один к узлу два не обязательно должен быть равен 1. Если бы не было потока между узлами один и два, то входы в приемник изменились бы на 4/4 и 3/5; общий поток все равно будет семь (4 + 3 = 7). С другой стороны, если поток от узла один к узлу два удвоится до 2, то входы в приемник изменится на 2/4 и 5/5; общий поток снова останется на уровне семи (2 + 5 = 7).

Заявление [ править ]

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

Задачу максимального потока можно сформулировать как максимизацию электрического тока через сеть, состоящую из нелинейных резистивных элементов. ^[4] В такой постановке предел тока $I$ $в$ между входными клеммами электрической сети в качестве входного напряжения $V$ $в$ подходах , равно весу набор среза минимального веса. $\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$ и $т$ , и мы должны найти максимальное количество края непересекающихся го путей в $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 cut представляет проекты и машины в $P$ и $Q$ соответственно. По теореме о максимальном потоке и минимальном отсечении можно решить задачу как задачу о максимальном потоке .

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

	Проект $r (p i)$	Машина $c (q j)$
1	100	200	Для проекта 1 требуются машины 1 и 2.
2	200	100	Для проекта 2 требуется машина 2.
3	150	50	Для проекта 3 требуется машина 3.

Минимальная мощность одного прохода - 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$ , а приемник (пурпурный узел) соединен всеми пикселями с емкостью $б I$ . Два ребра ( $i, j$ ) и ( $j, i$ ) с емкостью $p ij$ добавляются между двумя соседними пикселями. Й вырез множество , то представляет пиксели , назначенные на первый план в $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$

Требовать. $value (f) = c (A, A c)$ , где емкость первого разреза определяется

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

.

Теперь мы знаем, для любого подмножества вершин, $A$ . Следовательно, для $значения ($ $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}$

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

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

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

См. Также [ править ]

Гипотеза GNRS
Линейное программирование
Максимальный расход
Минимальный срез
Поточная сеть
Алгоритм Эдмондса – Карпа
Алгоритм Форда – Фулкерсона
Приближенная теорема о максимальном расходе и минимальном сокращении
Теорема Менгера

Ссылки [ править ]

^ Данциг, Великобритания; Фулкерсон, Д.Р. (9 сентября 1964 г.). «О теореме сетей о максимальном потоке и минимальном разрезе» (PDF) . Корпорация RAND : 13 . Проверено 10 января 2018 .
^ Тревизан, Лука. «Лекция 15 из CS261: Оптимизация» (PDF) .
^ Келлер, Оргад. «LP min-cut max-flow презентация» .
^ Цедербаума, I. (август 1962). «Об оптимальной работе сетей связи». Журнал Института Франклина . 274 : 130–141.
^ LR Ford Jr. & DR Fulkerson (1962) Потоки в сетях , страница 1, Princeton University Press MR 0159700
^ LR Ford Jr. и DR Fulkerson (1956) "Максимальный поток через сеть", Canadian Journal of Mathematics 8: 399-404}}
↑ П. Элиас, А. Файнштейн и К. Э. Шеннон (1956) «Заметка о максимальном потоке через сеть», IRE. Труды по теории информации, 2 (4): 117–119.
^ Джордж Данциг и Д. Р. Фулкерсон (1956) "О теореме сетей о максимальном потоке и минимальном разрезе", в линейных неравенствах , Ann. Математика. Исследования, нет. 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.

[1] Данциг, Великобритания; Фулкерсон, Д.Р. (9 сентября 1964 г.). «О теореме сетей о максимальном потоке и минимальном разрезе» (PDF) . Корпорация RAND : 13 . Проверено 10 января 2018 .

[2] Тревизан, Лука. «Лекция 15 из CS261: Оптимизация» (PDF) .

[3] Келлер, Оргад. «LP min-cut max-flow презентация» .

[4] Цедербаума, I. (август 1962). «Об оптимальной работе сетей связи». Журнал Института Франклина . 274 : 130–141.

[5] LR Ford Jr. & DR Fulkerson (1962) Потоки в сетях , страница 1, Princeton University Press MR 0159700

[6] LR Ford Jr. и DR Fulkerson (1956) "Максимальный поток через сеть", Canadian Journal of Mathematics 8: 399-404}}

[7] П. Элиас, А. Файнштейн и К. Э. Шеннон (1956) «Заметка о максимальном потоке через сеть», IRE. Труды по теории информации, 2 (4): 117–119.

[8] Джордж Данциг и Д. Р. Фулкерсон (1956) "О теореме сетей о максимальном потоке и минимальном разрезе", в линейных неравенствах , Ann. Математика. Исследования, нет. 38, Принстон, Нью-Джерси

[9] LR Ford & DR Fulkerson (1957) "Простой алгоритм для нахождения максимальных сетевых потоков и приложение к проблеме Хичкока", Canadian Journal of Mathematics 9: 210–18

[1]