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

Концепция теории оптимизации

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

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

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

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

Сеть

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

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

Потоки

Поток через сеть представляет собой отображение, обозначаемое или , с учетом следующих двух ограничений: ${\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}$

Порезы

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

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

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

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

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

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

Проблема с минимальным вырезом. Минимизируйте c ( S , T ) , то есть определите S и T так, чтобы пропускная способность st разреза была минимальной.

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

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

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

Пример

Максимальный поток в сети. Каждое ребро помечено f/c , где f — поток через ребро, а c — пропускная способность ребра. Значение расхода равно 5. Имеется несколько минимальных срезов s - t с производительностью 5; один из них S = { s , p } и T = { o , q , r , t }.

На рисунке справа показан поток в сети. Числовая аннотация на каждой стрелке в форме 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:

${\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_{v}={\begin{cases}1,&{\text{if }}v\in S\\0,&{\text{otherwise}}\end{cases}}}$

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

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

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

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

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

Приложение

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

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

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

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

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

${\displaystyle \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 — набор закупленных машин, тогда проблему можно сформулировать следующим образом:

${\displaystyle \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 , эту задачу максимизации можно вместо этого сформулировать как задачу минимизации, т. е.

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

Вышеупомянутую проблему минимизации затем можно сформулировать как задачу минимального сечения путем построения сети, где источник подключен к проектам с мощностью r ( pi ₎ , а приемник подключен к машинам с мощностью c ( q _j ). . Ребро ( pi , qj ) с бесконечной производительностью добавляется, _{если для проекта} pi _{требуется} машина qj . Первый набор разрезов представляет проекты и машины в P и Q соответственно. По теореме о максимальном потоке и минимальном сокращении проблему можно решить как задачу о максимальном потоке .

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

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

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

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

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

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

Пусть P — набор пикселей, назначенных переднему плану, а 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}.}$

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

История

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

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

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

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

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

1. A : набор вершин, достижимых из s в G _f
2. A ^c : набор оставшихся вершин, т. е. V − A

Требовать. value(  f  ) = c ( A , Ac ⁾ , где пропускная способность st разреза определяется выражением

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

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

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

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

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

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

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

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

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

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

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

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

1. Данциг, Великобритания; Фулкерсон, Д.Р. (9 сентября 1964 г.). «О теореме сетей о максимальном потоке и минимальном разрезе» (PDF) . RAND Corporation : 13. Архивировано из оригинала (PDF) 5 мая 2018 года.
2. Тревизан, Лука. «Лекция 15 из CS261: Оптимизация» (PDF) .
3. Келлер, Оргад. «Презентация LP min-cut max-flow».
4. Седербаум, И. (август 1962 г.). «Об оптимальной эксплуатации сетей связи». Журнал Института Франклина . 274 : 130–141.
5. Л.Р. Форд-младший и Д.Р. Фулкерсон (1962) Потоки в сетях , стр. 1, Princeton University Press MR 0159700
6. Л.Р. Форд-младший и Д.Р. Фулкерсон (1956) «Максимальный поток через сеть», Canadian Journal of Mathematics 8: 399-404
7. П. Элиас, А. Файнштейн и К. Э. Шеннон (1956) «Заметка о максимальном потоке через сеть», IRE. Труды по теории информации, 2 (4): 117–119.
8. Джордж Данциг и Д. Р. Фулкерсон (1956) «О теореме сетей о максимальном потоке MinCut», в «Линейные неравенства» , Ann. Математика. Исследования, нет. 38, Принстон, Нью-Джерси
9. Л. Р. Форд и Д. Р. Фулкерсон (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. Введение в ЛП-Дуальность». Алгоритмы аппроксимации . Спрингер. стр. 93–100. ISBN 3-540-65367-8.