Условие задачи
Найдите максимальный поток в заданной транспортной сети (s – начальная вершина, t – конечная), используя алгоритм Форда-Фалкерсона. Проверьте ответ по теореме Форда-Фалкерсона (найдите минимальный разрез графа сети).
Ответ
1. Начальный поток равен Valf=0
Путь из s в t, по которому поток может быть увеличен состоит из следующих дуг: sat.
Расставляем пометки вершин:
. Добавка к потоку: :