Вопросы по пути увеличения (метод Форда-Фалкерсона)

Сейчас я изучаю метод Форда-Фалкерсона.

В некоторых статьях говорится, что если f — максимальный поток, то увеличивающего пути нет! Но если увеличивающего пути нет, откуда вы знаете, что f — максимальный поток?

  • Откуда вы знаете, что способ нахождения увеличивающего пути правильный?
  • Почему в остаточной сети, если мы не можем связаться с t из s, нет способа увеличить поток? Откуда ты это знаешь?

optimization algorithm mathematical-optimization max-flow ford-fulkerson
person hygoni    schedule 24.12.2019    source источник
comment
Я думаю, у вас есть небольшое непонимание того, что такое увеличивающие пути и где они вписываются в этот алгоритм. Они представляют собой промежуточное представление, включающее подмножество конечного потока. Вы рекурсивно находите новый aug. пути и добавляйте их, постепенно увеличивая вашу емкость до максимума. Как только нет способа увеличить его, это потому, что вы загружены, поэтому у вас есть максимальный поток, и нет увеличивающих путей, то есть нет способа достичь t из s. Последний вопрос можно доказать от противного. Если бы был способ добраться до t из s, то был бы aug. путь и, таким образом, способ достижения t.   -  person sinanspd    schedule 24.12.2019

Ответы (1)


arrow_upward
0
arrow_downward

Это теорема максимального потока о минимальном разрезе, ср. например Теорема 26.6 в CLRS. Суть в следующем: пусть S будет набором вершин, доступных из источника в остаточной сети, и пусть T = V \ < em>S. Тогда, если увеличивающих путей нет, (S, T) — разрез, и оказывается, что значение потока — это пропускная способность этого разреза. Поскольку значения расхода никогда не могут превышать пропускную способность, из этого следует, что расход максимален.

person fuglede    schedule 27.12.2019