Как найти минимальный разрез на графике с использованием алгоритма максимального потока?

Ответ 1

Из исходной вершины выполните поиск по глубине вдоль ребер в остаточной сети (то есть, не насыщенные края и задние края ребер, имеющих поток), и отметьте все вершины, которые могут быть достигнуты таким образом. Вырез состоит из всех ребер, которые идут от отмеченной до немаркированной вершины. Ясно, что эти края насыщены и, таким образом, не пересекаются. Как вы заметили, могут быть другие насыщенные ребра, которые не являются частью минимального разреза.

Ответ 2

Я не хочу быть придирчивым, но предлагаемое решение не совсем правильно, как было предложено.

Правильное решение. То, что вы на самом деле должны делать, это bfs/dfs на Residual-Network Gf (прочитать его на wikipedia) и маркировка вершин. И тогда вы можете выбрать те, у которых отмечены от вершины и немаркированные вершины.

Почему "следующие ненасыщенные ребра" недостаточно [/strong > : Учтите, что алгоритм потока насыщает ребра, как показано на рисунке. Я отметил вершины, которые я посещаю, с подходом "только после ненасыщенных ребер" с зеленым цветом. Ясно, что единственным правильным минимальным разрезом является край от E-F, в то время как предлагаемое решение также вернет A-D (и, возможно, даже D-E).

Обратите внимание, что вершина D будет посещаться dfs/bfs, если вместо этого мы рассмотрим Остаточную сеть, потому что было бы ребро от E до D, тем самым сделав ребро EF единственным с отмеченным из-вершины и немаркированным к вершине.

Ответ 3

Примечание. Алгоритм Фалька можно использовать для поиска минимального разреза с минимальными вершинами и с максимальными вершинами. Для последнего алгоритм должен быть обратным, т.е. поиск из вершины приемника вместо источника. См. Соответствующий вопрос: Сетевой поток: добавление нового края

Ответ 4

Один из способов понять, пусть определит разрез как два множества S и T, которые будут включать s и t соответственно.

Теперь добавьте все вершины в S, которые достижимы из s в остаточной сети и поместите оставшиеся ребра в T. Это будет один разрез.

Во-вторых, разрез можно сформировать, поместив все вершины из T, которые достижимы из t в остаточной сети и поместите оставшиеся вершины в S.

Взгляните на это видео, чтобы узнать, как найти вершины, доступные из s и t.

https://www.youtube.com/watch?v=FIJaXfUIXJA&index=4&list=PLe-ggMe31CTduQ68XQ-sVj32wYJIspTma

Ответ 5

После вычисления максимального потока мы можем искать ребра (u,v) такие, что в остаточном графе есть ребро в остаточном графе от v до u и f(v,u) = c(u,v) [это означает, что ребро насыщенный]

После кратковременного отображения таких ребер мы можем выбрать такие ребра (u,v), используя критерии отсутствия пути от u до погружения t в остаточном графе. Если это условие выполнено, то такие ребра образуют часть (S,T) cut

Время выполнения этого алгоритма может быть O(E) * O( V + E ) = O( E^2 )

Ответ 6

Я думаю, что это то, что говорят другие люди, но я нашел это неясным, так вот мое объяснение:

Из источника node сделайте заливку заливки графика, перемещаясь только по краям с остаточной емкостью, маркируя каждую посещенную вершину. Вы можете использовать DFS для этого. Напомним, что задние ребра из вершины имеют остаточную емкость - равную потоку вдоль переднего края (т.е. R (u, v) = оставшаяся емкость для ребра (u, v), r (v, u) = flow (u, v)).

Фактически это определяет S-часть разреза S-T графика.

Минимальным разрезом будет теперь набор ребер, чтобы одна вершина была отмечена от заливки заливки выше, а другая вершина не отмечена. Это будут ребра без остаточной емкости (иначе вы бы пересекли их в своей DFS) и вместе сформировали минимальный разрез.

После удаления этих ребер набор немаркированных вершин образует участок T разреза.

Ответ 7

Итак, чтобы дать точную процедуру, как получить сокращение minumum:

• Запустите алгоритм Форда-Фулкерсона, чтобы найти максимальный поток и получить остаточный граф ¹.
• Запустите BFS на остаточном графе, чтобы найти набор вершин, доступных из источника в остаточном графе. (учитывая, что вы не можете использовать ребра с 0 емкостью в остаточном графе) ВАЖНО: вы должны использовать обратные ребра в остаточном графе, чтобы найти правильный набор достижимых вершин!!! (см. этот алгоритм)
• Все ребра в исходном графе, которые находятся от достижимой вершины до недостижимой вершины, являются минимальными режущими кромками. Распечатайте все такие ребра.

¹ График, в котором емкость ребра определяется как его первоначальная емкость минус его поток (поток из сети максимального потока).