Замечание

Если в графе G = (V, A, j) существуют два истока S^/₁ и S^/₂, тогда добавляем к множеству вершин графа фиктивную вершину S^/ и дуги (S^/, S^/₁) и (S^/, S^/₂); полагаем:

 

, .

 

Аналогично для двух стоков S^//₁ и S^//₂. Для преобразованного графа применим алгоритм Форда-Фалкерсона отыскания максимального потока в сети.

 

С понятием потока связано понятие разреза сети. Под разрезом сетипонимается множество дуг сети Р(А), обладающих следующим свойством: любой путь от истока к стоку пройдет ходя бы по одной дуге разреза. При удалении дуг разреза сеть становится несвязной, т.е. сеть как бы разрезается.

Величиной разреза С(Р) называется сумма пропускных способностей входящих в него дуг: .Естественно необходимо найти разрез минимальной величины.

В сети величина максимального потока равна величине минимального разреза, т.е.

.(4.11)