39. Задача о максимальном потоке и минимальном разрезе. Алгоритм Форда-Фалкерсона.

Задан вершинный орграф G=(N,U). Взвешены дуги. Дуге (I,j) приписано неотрицательно число ci≥0, которое называется пропускной способностью дуги. Граф, лежащий в основе орграфа G-связный.

Выделены 2 вершины s и t. S-источник, t-сток. Такие орграфы-сети.

Потоком по сети G называется множество чисел xij таких, что:

1.0≤xij≤cij

2.Закон сохранения потока в вершине: ∀k≠s,t выполняется, что суммарный поток втекающей вершины равен суммарному потоку вытекающему из неё.

3.Закон сохранения потока в сети:поток, втекающий в сеть через вершину s=потоку вытекающему из сети через вершину t.

Задача состоит в том, что необходимо максимилизировать величину потока из сети при ограничении 1,3.

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

Задача о мини разрезе. Пусть У⊆Nи пусть SЭУ и t∉У.

Разрезом сети G(Y,¬Y) назыв множ таких рёбер (i,j) таких, что {iЄY, jЄ¬Y} или наоборот: {iЄ¬Y, jЄY}

Пропускной способностью разреза назыв величина с (У,¬У)=∑сij

(i,j)Є(Y,¬Y)

Задача о мин разрезе формулируется след образом: с(У,¬У) минилизировать -> min(Y,¬Y). Мин ищется по всевозможным разрезам, выделяющие источник по стокам.

Алгоритм Форда-Фолкерсона.

I этап. Выбираем некоторый начальный поток. В качестве такого потока можно взять xij=0.Вершина S получает метку(S,∞). Это значит, что мы пытаемся засунуть в сеть бесконечный по величине макс поток. Вершина S при этом считается помеченной, но не просмотренной. Все остальные вершины не помечены.

II этап. Выбираем произвольную помеченную и не просмотренную вершину и пытаемся пометить из неё все смежные с ней вершины. Предположим, выбранная вершина k и пытаемся пометить смежну к ней вершину i. Возможны 2 случая:

1.в исходном графе имеется дуга (k,i)

2.в исходном графе имеется дуга (i,k)

Рассмотрим первый случай. Имеем 2 случая:

1.Если cki>xki, то по дуге (k,i) ток можно увеличить на величину ε^+(i)=min{cki-xki,ε(k)}

2.Если сki=xki, то дуга в этом случае дуга назыв насыщенной вершину i пометить из вершины k нельзя и поток по этой дуге увеличить нельзя. Рассмотрим II случай. Здесь также 2 случая:

1.xik>0, то поток по дуге (i,k) можно уменьшить на величину ε^(-)(i)=min(xik,ε(k)). При этом, вообще говоря, поток по сети увеличивается.

2.Если xik=0, то вершину i из вершины k пометить нельзя. Независимо от того, удалось ли пометить все смежные с k вершины, вершина к считается помеченной и просмотренной. Процедура расстановки пометки продолжается до тех пор, пока не будет помечена вершина Е. Если вершину Е удаётся пометить, то переходим на след этап. В противном случае текущий поток является макс и при этом определяется мин разрез.

III этап. Начиная из вершины t, по меткам определяем путь из s в t. Пусть вершина t имеет метку M(t)=(in,ε^+(t)), вершина M(in)=(in-1,…), M(in-1)=(in-2,…) и тем самым будет определён полупуть (S=i1,i2,…,in,t), дуговые потоки для этого полупути изменяем на величину ε(t). В случае ориентации дуги из s в t, воток по дуге увеличиваем на величина ε(t), в случае обратного-уменьшаем на величину ε(t). После этого все метки, за исключением метки вершины s, вытираются, все вершины, кроме вершины s считаются непомеченными, а вершина s помеченной и не просмотренной. Возвращаемся на II этап.