Теорема Форда-Фалкерсона о максимальном потоке

Теорема (Форда-Фалкерсона) о максимальном потоке: всякая транспортная сеть имеет максимальный поток и его величина Mf = cmin.

Доказательство: Построим полный поток сети S по теореме 1. Тогда всякий направленный путь в S от s к t насыщен (имеет насыщенную дугу). По теореме 2 (см. потоки в транспортных сетях) построим поток, для которого всякая ненаправленная цепь от s к t, имеющая обратные дуги не допускает увеличение потока. По теореме 3 построенный поток максимален и его величина Mf = cmin.


Комментарии запрещены.





Статистика

Рейтинг@Mail.ru