Увеличьте поток, изменив только один край после Ford-Fulkerson

Question

Предположим, что я запустил алгоритм Форда-Фулкерсона на графике G = (V,E), и в результате получился максимальный поток f_max, который связан с минимальным сечением Xmin. Я заинтересован в максимально возможном увеличении потока за счет увеличения пропускной способности любого ребра на графике. Как я могу определить этот край?

Одна из стратегий может быть следующей: с учетом начальной вершины s и конечной вершины t рассмотрите все пути от s до t и проверьте ребро с меньшей пропускной способностью. Например, если у меня есть ребро с 1/1, это вершина, которую я должен увеличить емкость.

Существует ли общий алгоритм решения этой проблемы?

Answer 1

Как только вы нашли максимальный поток на графике, увеличение пропускной способности ребра (u, v) увеличит максимальный поток только в том случае, если на остаточном графике есть путь с положительной пропускной способностью от s до u и от v до t. Если это не так, то после остаточного графика не будет расширенного пути на остаточном графике, поэтому максимальный поток останется максимальным.

Из ребер (u, v), обладающих этим свойством, максимальный объем дополнительного потока, который вы можете переместить от s до t после увеличения пропускной способности (u, v), будет ограничен. Если вы можете протолкнуть любой поток через этот край, вам придется найти путь от s до u и путь от v до t. При этом на каждом из двух путей всегда будет край узкого места, и поток не может увеличиться более чем на это. Соответственно, один из вариантов решения проблемы заключается в следующем:

• Найти путь с максимальным узким местом от s до каждого другого узла, достижимого из s в остаточном графе.
• Найдите путь максимального узкого места от каждого узла, который может достигать t к t в остаточном графе.
• Для каждого ребра (u, v), пересекающего путь, максимальный объем дополнительного потока, который можно протолкнуть через край, задается минимумом пути максимального узкого места от s до u и пути максимального узкого места от v до t,

Другими словами, если вы можете вычислить пути максимального узкого места в графе, вы можете найти ребро, которое должно быть увеличено за время O(B(m, n) + m), где B (m, n) - это стоимость вычисление путей максимального узкого места в графе.

К счастью, это хорошо изученная проблема, и ее можно решить с помощью варианта алгоритма Дейкстры, где вместо хранения путей с минимальными затратами к каждому узлу вы сохраняете пути с максимальным узким местом для каждого узла. Быстрый поиск в Google должен найти дополнительную информацию по этому вопросу. Используя кучу Фибоначчи, вы можете реализовать этот поиск за время O(m + n log n), и, следовательно, общее время выполнения для определения ребра, емкость которого должна быть увеличена, также должно быть O (m + n log n).

Надеюсь это поможет!