В информатике и теории оптимизации теорема о максимальном потоке и минимальном разрезе утверждает, что в проточной сети максимальный объем потока, проходящего от источника к стоку, равен общему весу ребер в минимальном разрезе , т. е. наименьший общий вес ребер, удаление которых приведет к отключению источника от стока.
Это частный случай теоремы двойственности для линейных программ , который можно использовать для вывода теоремы Менгера и теоремы Кенига-Эгервари . [1]
Теорема приравнивает две величины: максимальный поток через сеть и минимальную пропускную способность сечения сети. Чтобы сформулировать теорему, каждое из этих понятий необходимо сначала определить.
Сеть состоит из
Поток через сеть представляет собой отображение, обозначаемое или , с учетом следующих двух ограничений:
Поток можно представить как физический поток жидкости через сеть, следуя направлению каждого края. Тогда ограничение пропускной способности гласит, что объем, проходящий через каждое ребро в единицу времени, меньше или равен максимальной пропускной способности ребра, а ограничение сохранения гласит, что объем, поступающий в каждую вершину, равен объему, вытекающему из каждой вершины. кроме исходных и стоковых вершин.
Величина потока определяется формулой
где, как указано выше, это источник и приемник сети. В аналогии с жидкостью он представляет собой количество жидкости, поступающей в сеть у источника. Из-за аксиомы сохранения потоков это то же самое, что и количество потока, покидающего сеть в стоке.
Задача о максимальном потоке требует максимального потока в данной сети.
Проблема максимального потока. Максимизировать, то есть маршрутизировать как можно больший поток отк.
Другая половина теоремы о максимальном потоке и минимальном разрезе относится к другому аспекту сети: набору разрезов. St разрез C = ( S , T ) — это разбиение V такое, что s ∈ S и t ∈ T. То есть разрез s — t — это разделение вершин сети на две части, с источником в одной части и стоком в другой. Множество разреза C — это набор ребер , которые соединяют исходную часть разреза с стоковой частью:
Таким образом, если все ребра в разрезе C удалены, положительный поток невозможен, поскольку в результирующем графе нет пути от источника к стоку.
Пропускная способность поперечного разреза равна сумме пропускных способностей ребер в его наборе разрезов.
где если и , иначе.
Обычно в графе много разрезов, но найти разрезы с меньшими весами зачастую труднее.
В описанной выше ситуации можно доказать, что значение любого потока через сеть меньше или равно пропускной способности любого 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:
Цель минимизации суммирует пропускную способность по всем ребрам, содержащимся в разрезе.
Ограничения гарантируют, что переменные действительно представляют собой допустимый разрез: [3]
Обратите внимание: поскольку это задача минимизации, нам не нужно гарантировать, что ребро не находится в разрезе — нам нужно только гарантировать, что каждое ребро, которое должно быть в разрезе, суммируется в целевой функции.
Равенство в теореме о максимальном потоке и минимальном сокращении следует из сильной теоремы двойственности в линейном программировании , которая утверждает, что если основная программа имеет оптимальное решение x *, то двойственная программа также имеет оптимальное решение y *, такое что оптимальные значения, образованные двумя решениями, равны.
Задачу максимального потока можно сформулировать как максимизацию электрического тока через сеть, состоящую из нелинейных резистивных элементов. [4] В этой формулировке предел тока I между входными клеммами электрической сети, когда входное напряжение V приближается к , равен весу набора отсечек минимального веса.
В дополнение к пропускной способности ребра, рассмотрим пропускную способность в каждой вершине, то есть отображение, обозначаемое c ( v ) , такое, что поток f должен удовлетворять не только ограничению пропускной способности и сохранению потоков, но также пропускной способности вершины. ограничение
Другими словами, количество потока , проходящего через вершину, не может превышать ее пропускную способность. Определите разрез 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 — набор закупленных машин, тогда проблему можно сформулировать следующим образом:
Поскольку первое слагаемое не зависит от выбора P и Q , эту задачу максимизации можно вместо этого сформулировать как задачу минимизации, т. е.
Вышеупомянутую проблему минимизации затем можно сформулировать как задачу минимального сечения путем построения сети, в которой источник подключен к проектам с мощностью r ( pi ) , а приемник подключен к машинам с мощностью c ( q j ) . . Ребро ( pi , qj ) с бесконечной производительностью добавляется, если для проекта pi требуется машина qj . Первый набор разрезов представляет проекты и машины в P и Q соответственно. По теореме о максимальном потоке и минимальном сокращении проблему можно решить как задачу о максимальном потоке .
На рисунке справа представлена сетевая формулировка следующей задачи выбора проекта:
Минимальная мощность одного разреза — 250, а сумма дохода каждого проекта — 450; следовательно, максимальная прибыль g равна 450 - 250 = 200 при выборе проектов p 2 и p 3 .
Идея здесь состоит в том, чтобы «пропустить» прибыль каждого проекта через «трубы» его машин. Если мы не можем заполнить трубу с помощью машины, прибыль машины будет меньше, чем ее стоимость, и алгоритм минимального сокращения сочтет, что дешевле сократить прибыль проекта, а не стоимость машины.
В задаче сегментации изображения имеется n пикселей. Каждому пикселю i может быть присвоено значение переднего плана f i или значение фона b i . Существует штраф pij , если пиксели i, j соседние и имеют разные назначения. Проблема состоит в том, чтобы назначить пиксели переднему или заднему плану так, чтобы сумма их значений за вычетом штрафов была максимальной.
Пусть P — набор пикселей, назначенных переднему плану, а Q — набор точек, назначенных фону, тогда проблему можно сформулировать следующим образом:
Вместо этого эту задачу максимизации можно сформулировать как задачу минимизации, т. е.
Вышеупомянутую задачу минимизации можно сформулировать как задачу минимального сечения путем построения сети, в которой источник (оранжевый узел) соединен со всеми пикселями с емкостью f 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 по алгоритму Форда–Фалкерсона . В остаточном графе ( Gf ) , полученном для G (после окончательного назначения потока алгоритмом Форда–Фалкерсона ), определите два подмножества вершин следующим образом:
Требовать. value( f ) = c ( A , Ac ) , где пропускная способность st разреза определяется выражением
Теперь мы знаем, что для любого подмножества вершин A . Следовательно, для value( f ) = c ( A , Ac ) нам нужно:
Для доказательства вышеизложенного утверждения рассмотрим два случая:
Оба приведенных утверждения доказывают, что пропускная способность полученного вышеописанным способом разреза равна потоку, полученному в сети. Кроме того, поток был получен с помощью алгоритма Форда-Фалкерсона , поэтому он также является максимальным потоком сети.
Кроме того, поскольку любой поток в сети всегда меньше или равен пропускной способности каждого возможного разреза в сети, описанный выше разрез также является минимальным разрезом , который обеспечивает максимальный поток .
Следствием этого доказательства является то, что максимальный поток через любой набор ребер разреза графа равен минимальной пропускной способности всех предыдущих разрезов.