Алгоритм нахождения максимального потока

Дана сеть (G,a), a – источник, b – сток сети, a:E®N.

 

Шаг 1. Если не существует пути из источника в сток, то положить j=0 и перейти к шагу 4, иначе выбрать непустое множество T непересекающихся по дугам путей из a в b. Если e₁,e₂,…,e_k – путь из T, т.е. последовательность дуг, то положить j(e₁)= j(e₂)=…= j(e_k)=min{a(e₁),…,a(e_k)}. Для дуг e, через которые не проходят пути из T, положить j(e)=0. В результате получаем ненулевой поток j через сеть (G,a).

 

Шаг 2. Исходя из сети (G,a) и потока j построить сеть (G^/,a^/) следующим образом. Граф G^’ будет иметь те же вершины, что и граф G. Если e – дуга графа G и a(e) – j(e)¹0, то e – дуга графа G^/ и a^/(e)=a(e) – j(e). Если e – дуга графа G и j(e)¹0, то вводим дугу обратной ориентации, нежели e, и полагаем a^/( ) = j(e). В случае, когда возникают кратные дуги e₁ и e₂, то вводим вместо них одну дугу e и полагаем a^/(e)=a^/(e₁) + a^/(e₂).

 

Шаг 3. Если в сети (G^/,a^/) не существует пути из a в b, то перейти к шагу 4, иначе в сети (G’,a’) построить ненулевой поток j’ так, как это предписано шагом 1. Для сети (G,a) положить j=j+j’ и перейти к шагу 2.

 

Шаг 4. Выдать j. Конец работы алгоритма.

 

На примере сети, изображенной на рис 6.22, проиллюстрируем работу алгоритма. В качестве множества T на первом шаге алгоритма выбрано множество из двух путей: a,v₁,v₄,b и a,v₂,v₅,b.

Рис 6.22 Рис. 6.23

 

На рис. 6.23 представлена сеть (G^/,a^/) полученная после выполнения шага 2 из сети на рис. 6.22 с указанным (в скобках) потоком j^/. В качестве множества T для построения потока j^/ взято множество, состоящее из одного пути: a,v₃,v₅,v₂,v₆,b. Поток j+j^/ для сети (G,a) изображен на рис. 6.24. Этим завершен один проход алгоритма. Обратим внимание на то, что для e=(v₂,v₅) (j+j^/)(e)=j(e)-j^/( )=1.

 

Рис. 6.24 Рис. 6.25

 

Сеть построенная на шаге 2 второго прохода алгоритма, уже не имеет (a,b) – путей (см.рис. 6.25). Следовательно, на рис. 6.24 изображен максимальный поток.