Теорема о максимальном расходе и минимальном разрезе - Max-flow min-cut theorem

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

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

Определения и заявление

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

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

Позволять N = (V, E) быть ориентированный граф, куда V обозначает множество вершин, а E это множество ребер. Позволять s ∈ V и т ∈ V быть источником и приемником N, соответственно.

В емкость ребра - это отображение ${\displaystyle c:E\to \mathbb {R} ^{+}}$ обозначается c_УФ или же c(ты, v) куда ты,v ∈ V. Он представляет собой максимальный поток, который может пройти через край.

Потоки

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

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

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

В ценить потока определяется

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

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

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

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

Порезы

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

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

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

В емкость из s-t вырезать - общий вес его ребер,

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

куда ${\displaystyle d_{ij}=1}$ если ${\displaystyle i\in S}$ и ${\displaystyle j\in T}$, ${\displaystyle 0}$ иначе.

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

Проблема с минимальным разрезом s-t. Свести к минимуму c(S, Т), то есть определить S и Т так что емкость S-T разрез минимально.

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

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

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

Постановка линейной программы

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

	Максимальный расход (Primal)	Мин-вырез (двойной)
переменные	${\displaystyle f_{uv}}$ ${\displaystyle \forall (u,v)\in E}$ [переменная для каждого края]	${\displaystyle d_{uv}}$ ${\displaystyle \forall (u,v)\in E}$ [переменная для каждого края] ${\displaystyle z_{v}}$ ${\displaystyle \forall v\in V\setminus \{s,t\}}$ [переменная для нетерминального узла]
цель	максимизировать ${\displaystyle \sum \nolimits _{v:(s,v)\in E}f_{sv}}$ [максимальный общий поток из источника]	свести к минимуму ${\displaystyle \sum \nolimits _{(u,v)\in E}c_{uv}d_{uv}}$ [мин. общая вместимость кромок в резе]
ограничения	при условии ${\displaystyle {\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}}}$ [ограничение на ребро и ограничение на нетерминальный узел]	при условии ${\displaystyle {\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}}}$ [ограничение на край]
знаковые ограничения	${\displaystyle {\begin{aligned}f_{uv}&\geq 0&&\forall (u,v)\in E\\\end{aligned}}}$	${\displaystyle {\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:

${\displaystyle 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}}}$

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

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

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

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

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

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

Пример

Сеть со значением потока, равным пропускной способности отрезка s-t

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

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

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

Заявление

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

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

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

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

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

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

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

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

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

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

Смотрите также: Теорема Менгера

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

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

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

Смотрите также: Задача максимального расхода

Сетевая постановка задачи выбора проекта с оптимальным решением

В задаче выбора проекта есть п проекты и м машины. Каждый проект п_я приносит доход р(п_я) и каждая машина q_j расходы c(q_j) покупать. Для каждого проекта требуется несколько машин, и каждая машина может использоваться несколькими проектами. Проблема состоит в том, чтобы определить, какие проекты и машины следует выбрать и купить соответственно, чтобы получить максимальную прибыль.

Позволять п быть набором проектов нет выбран и Q быть набором купленных машин, то проблема может быть сформулирована как,

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

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

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

Вышеупомянутая задача минимизации затем может быть сформулирована как задача минимального сокращения путем построения сети, в которой источник подключен к проектам с мощностью р(п_я), а мойка подключается машинами емкостью c(q_j). Край (п_я, q_j) с бесконечный мощность добавляется, если проект п_я требуется машина q_j. Набор s-t cut-set представляет проекты и машины в п и Q соответственно. По теореме о максимальном потоке и минимальном разрезе можно решить проблему как проблема максимального расхода.

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

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

Минимальная мощность разреза s-t составляет 250, а сумма дохода по каждому проекту составляет 450; поэтому максимальная прибыль грамм 450 - 250 = 200, выбрав проекты п₂ и п₃.

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

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

Смотрите также: Задача максимального расхода

Каждый черный узел обозначает пиксель.

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

Позволять п быть набором пикселей, назначенных переднему плану и Q - набор точек, отнесенных к фону, то задача может быть сформулирована как,

${\displaystyle \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}.}$

Вместо этого эту задачу максимизации можно сформулировать как задачу минимизации, т. Е.

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

Вышеупомянутая задача минимизации может быть сформулирована как задача минимального среза путем построения сети, в которой источник (оранжевый узел) подключен ко всем пикселям с емкостью ж_я, а сток (пурпурный узел) соединен всеми пикселями с емкостью б_я. Два ребра (я, j) и (j, я) с п_ij емкость добавляется между двумя соседними пикселями. Затем набор s-t cut-set представляет пиксели, назначенные на передний план в п и пиксели, назначенные фону в Q.

История

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

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

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

Позволять грамм = (V, E) сеть (ориентированный граф) с s и т быть источником и приемником грамм соответственно.

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

1. А: множество вершин, достижимых из s в грамм_ж
2. А^c: множество оставшихся вершин, т.е. В - А

Требовать. ценить(ж ) = c(А, А^c), где емкость из s-t вырезать определяется

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

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

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

Чтобы доказать это утверждение, рассмотрим два случая:

• В грамм, существует исходящий край ${\displaystyle (x,y),x\in A,y\in A^{c}}$ такой, что он не насыщен, т.е.  ж (Икс, у) < c_ху. Это означает, что существует передний край из Икс к у в грамм_ж, следовательно, существует путь из s к у в грамм_ж, что противоречит. Следовательно, любое исходящее ребро (Икс, у) полностью насыщен.

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

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

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

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

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

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

Рекомендации

1. Dantzig, G.B .; Фулкерсон, Д. (9 сентября 1964 г.). "О теореме о максимальном потоке и минимальном разрезе сетей" (PDF). Корпорация РЭНД: 13. Получено 10 января 2018.
2. Тревизан, Лука. «Лекция 15 из CS261: Оптимизация» (PDF).
3. Келлер, Оргад. «Представление LP min-cut max-flow».
4. Седербаум, И. (август 1962 г.). «Об оптимальной работе сетей связи». Журнал Института Франклина. 274: 130–141.
5. Л. Р. Форд-младший & Д. Р. Фулкерсон (1962) Потоки в сетях, Страница 1, Princeton University Press МИСТЕР0159700
6. Л. Р. Форд-младший и Д. Р. Фулкерсон (1956) "Максимальный поток через сеть", Канадский математический журнал 8: 399-404}}
7. П. Элиас, А. Файнштейн и К. Э. Шеннон (1956) «Заметка о максимальном потоке через сеть», IRE. Труды по теории информации, 2 (4): 117–119.
8. Джордж Данциг и Д. Р. Фулкерсон (1956) "О теореме сетей о максимальном потоке и минимальном разрезе", в Линейные неравенства, Анна. Математика. Исследования, нет. 38, Принстон, Нью-Джерси
9. Л. Р. Форд и Д. Р. Фулкерсон (1957) "Простой алгоритм для поиска максимальных сетевых потоков и приложение к проблеме Хичкока", Канадский математический журнал 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.