Орграф приращений, Теорема Форда-Фалкерсона - Нахождение максимального потока в графе

Введем для заданной транспортной сети D и допустимого потока в этой сети орграф приращений, имеющий те же вершины, что и сеть D. Каждой дуге транспортной сети D в орграфе приращений соответствует две дуги: и - дуга, противоположная по направлению дуге. Припишем дугам орграфа приращений длину:

Т. е. орграф является нагруженным. При этом очевидно, что длина любого пути из в в орграфе равна либо 0, либо бесконечности.

Теорема Форда-Фалкерсона

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

Пусть. Тогда выполняется равенство

(1)

Если, так как в противном случае, используя имеем, а следовательно, в силу существует путь нулевой длины из в, что противоречит условию. Но тогда из (1) получаем

Следствие 1. Используя теорему Форда-Фалкерсона получаем, что величина максимального потока в транспортной сети равна пропускной способности минимального разреза.

Следствие 2. Пусть - допустимый поток в транспортной сети D. Тогда, если длина минимального пути из v1 в vn в орграфе приращений равна бесконечности, то - максимальный поток.

Похожие статьи




Орграф приращений, Теорема Форда-Фалкерсона - Нахождение максимального потока в графе

Предыдущая | Следующая