Max Flow / Minimum Cut - Расход после удаления алгоритма K ребер

Question

Меня попросили разработать алгоритм для следующей задачи:

Дано:

1. Поточная сеть G, края которой имеют максимальную пропускную способность 1
2. G максимальный поток | F |
3. Положительное целое число K

Удалить ровно K ребер, чтобы поток сети был минимизирован.

Мои мысли / алгоритм:

1. Если K больше или равно | F | удалить ВСЕ ребра, которые пересекают минимальный разрез G, и если K все еще больше нуля, удалите случайные ребра и новый максимальный поток равен нулю

2. Если K равно к | F | удалите ВСЕ кромки, пересекающие минимальный разрез G, и новый максимальный поток равен нулю

3. Если K меньше | F | удалить K ребер, которые пересекают минимальный разрез G, и новый максимальный поток равен | F | -K

Мне нужна некоторая проверка в качестве максимального потока / Min Cut для меня в новинку. Наконец, интуиция, лежащая в основе Max Flow / Min Cut, которую я получил, заключается в том, что Min (Source, Sink) cut работает как «узкое место» для максимального потока, который мы можем sh в сети. правильно?

Answer 1

Да, минимальный разрез является «узким местом» для потока, также |Min-Cut| = Max-flow. Если вам интересно, в Интернете есть масса доказательств (это известно как теорема о максимальном потоке и минимальном разрезе).

Для вашего алгоритма нет необходимости удалять случайные ребра на первом шаге, удаление одного ребра из min-cut уменьшает max-flow потоком, который проходит через это ребро (в данном случае 1, потому что все веса равны 1 согласно заявлению).

Таким образом, решение просто:

1. Найдите любые Min-Cut
2. Delete min(K, |Min-cut| ребер из графика)

Найти Min-Cut можно очень легко:

1. Построить остаток потоковый граф
2. Запустите на нем любой алгоритм максимального потока (Ford-Fulkerson, Bellman-Ford и др. c)
3. Теперь выполните BFS из исходного узла, только go через ребра, где значение потока меньше, чем пропускная способность
4. Теперь все ребра, которые go от посещенного узла к непосещаемому, образуют минимальный разрез