28. Теорема Форда и Фолкерсона (о максимальном потоке и минимальном разрезе)
К списку вопросов
Во всякой сети величина любого максимального потока равна пропускной способности любого минимального разреза.
Данная теорема позволяет для простых сетей проверять на максимальность найденный поток.
Примечание: этот алгоритм излагается для сетей с целочисленными пропускными способностями.
Обобщение его на сети с рациональными пропускными способностями не представляет затруднений.
Допустим, задана сеть пропускных способностей Nfu (D;fu).
Нахождение максимального потока через эту сеть осуществляется за 3 шага (хотя один из этих шагов как правило необходимо возвращаться многократно)
Шаг 1: подберём поток fi, обладающий ненулевой величиной (если такой существует), причем, чем больше величина выбранного на этом шаге потока, тем проще будут последующие шаги. Строим сеть потоков N? (D;?).
Шаг 2: Исходя из Nfu и Nfi строим новую сеть пропускных способностей Nfu' , путем изменения направления потока ? на противоположное;
более точно любая дуга а, для которой ?(а)=0 остается в Nfu' со своей первоначальной пропускной способностью.
fu' (a)= fi (a), а любая дуга а, для которой fi (a) не равно 0 заменяется дугой с пропускной способностью fu ' (a)= fu (a)- fi (a) и противоположно напраавленной дугой с пропускной способностью fi (a).
Шаг 3: Если в сети Nfu' можно найти ненулевой поток из V в W, то он алгебраически суммируется с первоначальным потоком ? и т.о. получается новый поток ? большой величины. Повторяя всю эту процедуру многократно, в конце концов приходим к сети N fi (n), не содержащей ненулевых потоков. Тогда соответствующий поток fi (n) и будет искомым максимальным потоком через данную сеть.
К списку вопросов
