Файл: Курсач ебаный.docx

Если j - поток через сеть N=(G,a), то через G_j будем обозначать суграф графа G, содержащий дуги, по которым проходит ненулевой поток (и только такие дуги).

Лемма 1. Для любого потока j через сеть N=(G,a) существует поток j через ту же сеть такой, что ½j½=½y½ и G_y - бесконтурный подграф графа G_j.

Доказательство. Предположим, что граф G_j содержит контур С, проходящий по дугам е₁,е₂,…,е_l. Среди чисел j (e₁), j(e₂), …, j (e_l) выберем наименьшее, пусть это будет число m. Рассмотрим функцию θ:E®NÈ{0}, определяемую следующим образом:

Легко проверить, что θ – поток через сеть N, ½j½= ½θ½ и G_θ – подграф графа G_j. Граф G_θ уже не содержит контура С. Повторяя эту процедуру необходимое число раз, в итоге получаем необходимый поток y.

Лемма доказана.

Лемма 2. Пусть j - ненулевой поток через сеть N с источником а и стоком b. Тогда существует простой (a,b) – путь, проходящий по дугам с ненулевым потоком.

Доказательство. В силу леммы 1 можно считать, что граф G_j = (V,E_j) не содержит контуров. Пусть V_a – множество вершин графа G_j, достижимых из вершины а. Поскольку граф G_j не содержит контуров, то множество V_a содержит хотя бы одну вершину х, которая является стоком в графе G_j. Ясно, что х¹а. Если х¹b, то в графе G существуют дуги с ненулевым потоком, заходящие в х, и не существует дуг с ненулевым потоком, выходящих из х. Это противоречит определению потока. Следовательно, bÎV_a, т.е. в графе G_jвершина b достижима из а. Это означает, что в сети N существует простой (a,b) – путь, проходящий по дугам с ненулевым потоком.

Лемма доказана.

Лемма 3. Величина любого потока через сеть не превосходит пропускной способности любого разреза этой сети.

Доказательство. Пусть j - поток через сеть N=(G,a), S – разрез этой сети. Напомним, что величину потока мы обозначаем через ½j½ а пропускную способность разреза – через a(S).

Предположим вначале, что функция j принимает целочисленные значения. Исходя из сети N и потока j, построим орграф G’ с кратными дугами. Множество вершин графа G’ совпадает с множеством вершин исходного графа G. Если е – (x,y)–дуга графа G и j(е)>0, то в графе G’ изображаем j (е) дуг, исходящих из х и заходящих в y. Если же j(е) = 0 или в G нет дуги из х в y, то в G’ тоже нет дуги из х в y. На рис. 6.20 изображен граф G’, построенный для сети N и потока (в скобках), представленных на рис. 6.19.

Из леммы 2 следует, что в графе G’ найдется множество Р из ½j½ простых (a,b)-путей, никакие два из которых не содержат общей дуги. Обозначим через S’ множество дуг графа G’, которые получились из дуг разреза S. Ясно, что S’ - разрез графа G’ и что количество дуг в S’ меньше или равно a(S). Каждый из путей множества Р содержит хотя бы одну дугу из S’, причем два различных пути не могут содержать одну и ту же дугу из S’. Это означает, что число путей в Р не превосходит число дуг в S’, т.е. ½j½=½Р½£½S’½£a(S).

Рассмотрим теперь случай, когда функция j принимает рациональные значения. Пусть m – наибольшее общее кратное всех знаменателей значений функции j. Тогда функция m·j будет потоком в сети (G; m·a). Ясно, что множество S будет разрезом и в новой сети с пропускной способностью, равной m·a(S). В предыдущем абзаце было доказано, что ½m·j½£ m·a(S). Отсюда следует неравенство ½j½£a(S).

Общий случай, т.е. когда допускаются любые значения пропускных способностей и потоков, сводится к рассмотренному выше с помощью следующего утверждения. Для любой сети N=(G,a) с потоком j и разрезом S и любого числа e >0 существует рациональный поток j₀ через ту же сеть, такой что - e <½j½–½j₀½<e и ½j₀½£ a(S).

Лемма доказана.

Для дальнейшего введем ряд обозначений. Пусть N=(G,a) – сеть, имеющая источник а и сток b, D – множество вершин сети, такое, что aÎD, bÏD. Тогда множество ребер

{(u,v) ÎE½uÎD, vÏD}

обозначим через S_D. Легко проверяется, что множество S_D является разрезом сети. Этот разрез будем называть D–разрезом. Если X и Y – непустые множества вершин сети, а j- поток через сеть, то

j (X,Y)=S{ j(u,v)½uÎX, vÎY}.

Например, для сети, изображенной на рис. 6.19, если D={a,x,y}, X={a,x}, Y={x,y,b}, то S_D={(a,z), (x,z), (y,b)}, j (X,Y)= j (a,x)+ j (a,y)+ j (x,y)=1+2+0=3.

Лемма 4. Пусть N=(G,a) – сеть, имеющая источник a и сток b, j - поток через эту сеть, D – множество вершин сети, содержащее a и не содержащее b. Тогда

½j½=j(D,) - j(D,).

Доказательство. По определению потока для x¹a и x¹b имеем равенство

j (x,V) - j (V,x)=0,

а по определению величины потока – равенство

j (a,V) - j (V,a)=½j½.

Из этих равенств следует, что

½j½= (j (x,V) - j (V,x)) = j (D,V) - j (V,D).

Далее, поскольку j(X₁ÈX₂,Y)=j(X₁,Y)+j(X₂,Y) для X₁ÇX₂=Æ и j (X,Y₁ÈY₂)= j(X,Y) + j(X,Y₂) для Y₁ÇY₂=Æ, то j(D,V) - j(V,D) = j(D,DÈ) - j(DÈ,D)=j(D,D)+j(D,) - j(D,D) - j(,D)=j(D,) - j(,D).

Лемма доказана.

Теорема Форда-Фалкерсона. В любой сети величина максимального потока равна пропускной способности минимального разреза.

Доказательство. Пусть j - максимальный поток в сети N=(G,a). В силу леммы 3 достаточно доказать существование разреза S такого, что a(S)=½j½.

Можно считать, что G_j - бесконтурный граф (см. лемму 1).

Дугу e назовем насыщенной, если j(e)=a(e). Обозначим буквой D множество вершин сети, содержащее сток a и все вершины u, для которых существует последовательность

a=x₀, x₁,…, x_k-1, x_k=u,

такая, что дуга (x_i, x_i+1) ненасыщенна или через дугу (x_i+1, x_i) проходит ненулевой поток. Например, для сети, изображенной на рис. 6.21. D={a,y,z}. Отметим, что zÎD, хотя дуги (y,z) в сети нет.

Докажем, что bÏD. Предположим, что это не так, т.е. bÎD. Тогда существует последовательность вершин

a=y₀,y₁,…,y_l-1,y_l=b                             (*)

указанного выше вида (т.е. либо дуга (y_i,y_i+1) ненасыщенна, либо через дугу (y_i+1,y_i) проходит ненулевой поток). Пусть e - положительное число, которое меньше разности a(e) - j(e) для любой ненасыщенной дуги e и меньше любого ненулевого потока через дуги сети.

Изменим значение потока j на дугах цепи следующим образом. Если дуга (y_i,y_i+1) ненасыщенна, то положим j'( y_i+1,y_i+1) = j(y_i,y_i+1)+e. Если же эта дуга насыщена, то пустьj'(y_i+1,y_i) = j(y_i+1,y_i)-e. Для остальных дуг e значение потока оставим прежним: j ′(e) = j (e).

Нетрудно убедиться, что j′ - поток через сеть N. Действительно, ограничение j′(e) £ a(e) выполняется для любой дуги e по построению j′. Если через вершину v не проходит цепь (*), то суммарный поток через v равен нулю, поскольку это справедливо для j. Пусть v=y_i для некоторого iÎ{1,…,l-1}. Возможны четыре случая определяемые насыщенностью или ненасыщенностью дуг (y_i-1,y_i) и (y_i,y_i+1). (Нам будет удобно отсутствующую дугу считать насыщенной) Рассмотрим только один из них: дуга (y_i-1,y_i) ненасыщенна, а дуга (y_i,y_i+1) насыщена. Обозначим буквой А множество вершин, из которых выходят дуги, заходящие в y_i, буквой B множество вершин сети, в которые заходят дуги, выходящие из y_i. Тогда

j(x,y_i) = j(y_i,z),                               (**)

поскольку j - поток. При переходе от j к j′ слагаемые в правой части не изменятся, а в левой изменятся два слагаемых: j(y_i-1,y_i) заменятся на j(y_i-1,y_i) + e, а j(y_i+1,y_i) - наj(y_i+1,y_i) - e, но вся сумма останется прежней. Следовательно, равенство (**) сохранится и при переходе от j к j′. Мы доказали, что j′ - поток через сеть N. Но его величина равна ½j½+ e, что противоречит максимальности потока j. Таким образом, bÏD.

Если uÎD и существует дуга, заходящая в u из вершины v, с ненулевым потоком, то vÎD. Это означает, что j(,D)=0. Рассмотрим разрез S_D. Тогда из леммы 4 следует, что½j½=a(S_D), поскольку a(S_D)= j(D, ).

Теорема доказана.

Рис. 6.21

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