Тема: Алгоритм Диница

Приведите, пожалуйста, пример блокирующего потока, который не является максимальным.

2 Отредактировано NotImplemented (2012-05-07 04:52:25)

Re: Алгоритм Диница

Это, конечно же, несложно. Но в самой статье в целом изложение слишком схематично. Например, "Теперь заметим, что поскольку ребро (u, w) появилось в остаточной сети только после выполнения i-ой фазы, то отсюда следует". Откуда следует, что ребро появилось после i-ой фазы?

3

Re: Алгоритм Диница

NotImplemented пишет:

"Теперь заметим, что поскольку ребро (u, w) появилось в остаточной сети только после выполнения i-ой фазы, то отсюда следует". Откуда следует, что ребро появилось посли i-ой фазы?

Кажется, что иными словами всё это доказательство можно записать так.
Либо путь P содержит те же рёбра, что существовали и на предыдущей фазе, поэтому короче он стать не мог.
Либо путь P содержит какие-то новые рёбра, которые не существовали в остаточной сети на предыдущей фазе (однако учтём, что ребро могло появиться в остаточной сети только в результате пропускания потока вдоль этого ребра в обратном направлении). Рассмотрим первое "новое" ребро (u,w) из пути P; тогда, раз по нему пропустили поток на предыдущей фазе, то level_{i-1}[ u ] > level_{i-1}[ w ]; для вершины u мы можем использовать первую часть доказательства леммы, т.е. level_{i+1}[ u ] >= level_i[ u ]; наконец, в пути P расстояние до вершины w на единицу больше расстояния до u, поэтому level_{i+1}[ w ] > level_{i+1}[ u ]; собирая всё вместе, получаем level_{i+1}[ w ] > level_i[ w ]. Проделывая это же для всех остальных "новых" рёбер пути P, получим в итоге требуемое неравенство для вершины v.

На в самой статье в целом изложение слишком схематично.

Я позже вернусь к этой статье и попробую улучшить непонятные места. Будет хорошо, если вы отпишетесь, что ещё было описано в статье не слишком удачно.