Почему жадный алгоритм без обратных рёбер не находит максимальный поток? Контрпример
Не понимаю, зачем нужны обратные рёбра в потоке. Казалось бы: ищем любой путь от истока к стоку, пускаем по нему максимум, повторяем. Почему так нельзя? Можно конкретный маленький контрпример, где это даёт не оптимум?
2 ответа
Классический контрпример на 4 вершинах. Вершины $s, a, b, t$. Рёбра (все пропускной способности 1, кроме среднего):
s -> a : 1
s -> b : 1
a -> t : 1
b -> t : 1
a -> b : 1 (это «диагональ»)
Максимальный поток здесь равен 2: пускаем $s\to a\to t$ и $s\to b\to t$.
Но жадность может сначала выбрать «неудачный» путь $s \to a \to b \to t$ (величина 1). После этого рёбра $s\to a$, $a\to b$, $b\to t$ насыщены. Остаётся только $s\to b$ и $a\to t$, но между ними нет пути ($b$ ведёт только в $t$ через насыщенное ребро, а в $a$ зайти неоткуда). Жадность останавливается на потоке 1 — это не оптимум.
Обратные рёбра спасают: после пуска $s\to a\to b\to t$ в остаточной сети есть обратное ребро $b\to a$ (пропускная 1). Теперь находится путь $s \to b \to a \to t$, использующий это обратное ребро. Пуск по нему «откатывает» поток на $a\to b$ и перенаправляет его правильно. Итог — поток 2. Обратное ребро формально означает «я передумал гнать поток через эту диагональ».
Именно поэтому корректные алгоритмы (Форд-Фалкерсон и потомки) всегда работают в остаточной сети, а не в исходной.
Полезная интуиция: обратное ребро — это не «физический» канал, а право отмены уже принятого решения. Без возможности откатить раннюю ошибку жадный выбор пути может загнать в локальный оптимум. Теорема Форда-Фалкерсона гарантирует: если в остаточной сети нет ни одного увеличивающего пути, то поток максимален (и тогда же находится минимальный разрез). Без обратных рёбер вы проверяете отсутствие путей в неправильном графе, поэтому и получаете неправильный ответ.