Задачи о MAX потоке

Рассмотрим граф G=(X,A) с пропускными способностями дуг , источником S и стоком t. S,tX.Множество чисел ,определенных на дугах (, называется потоками в дугах, если выполняется условие:-и

(1) – уравнение сохранения потока : Поток, втекающий в вершину, равен потоку, вытекающему из вершины за исключением источника (s) и стока (t).Для S-S-сетевое вытекание и t- приток велиены,V соответственно.

(2) – ограниченны на пропускные способности для каждой дуги G.Задача: найти множество потоков по дугам, чтобы величина V=была максимальной.

Теорема Форда-Фацкерсона:

(о максимальном потоке и максимальном разрезе).

Величина максимального потока из s в t равна величине min разреза (), отделяющего s от t. Разрезотделен s от t , если Sи t .Величиной такого разреза называется сумма пропускных способностей всех дуг из g, начальные ве

Вершины которых лежат в , а конечные в ,т.е. ) Минимальный разрез ( )- это разрез с наименьшим таким значением.

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

 

Очевидно, что max поток из s в t не может быть больше, чем v ( ) т.е. всякая цель из s в t проходит хотябы через 1 дугу данного разреза. Поэтому достаточно установить существование потока с таким значением. Допустим , что поток задается м-мерным вектором . и определим разрез ( ) рекурсивным применением нижеуказанного шага б)

а ) Начать, пологая { s}.

б) Если и, кроме того, или

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

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

 

.

Случай (1) , t; В соответствии с шагом б) отношение tозначает следующее: существует такое « неориентирование « цель, ведущее из s в t, что для каждой дуги (), используется только в прямом направлении ( прямой дуги ), а для каждой дуги ( ), используется только в обратном направлении, т.е. от к )(

 

обратной дуги ), ( эта цепь называется аугументами augmen - увеличение ) (

 

цепью потока.

Пусть = min [] для прямой дуги ( ),

()

) для обратной дуги (

()

(и

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

Используя наш направленный поток, можно затем повторить шаги а) и б) и опредилив новый разрез() , повторить

Случай (2), t(т.е.t). В соответствии с шагом () и Следовательно и величин потока , а именно равна величине разреза (.

Т.к. в случае (1) поток все время увеличивается, по крайней мере, на 1, то при целочисленности всех gij max и поток направляется за конечное число шагов – как только возникает случай (2). Этот поток будет равен величине текущего разреза () , который будет равен минимальному разрезу. Теорема доказана.

Алгоритм начинает работу с произвольного допустимого потока ( можно взять и 0-й поток), затем стремится увеличить величину потока с помощью систематического поиска всех возможных аугментальных целей потока от s к t. Поиск аугментальной цели осуществляется с помощью расставленных пометок в вершинах графа. Поэтому указывают, вдоль каких дуг может быть увеличен поток и на сколько.

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