Как я могу найти минимальное сокращение на графике, используя алгоритм максимального потока?

Question

Мне нужно найти минимальный разрез на графике.Я читал о потоковых сетях, но все, что я могу найти, - это алгоритмы максимального потока, такие как Ford-Fulkerson, push-relbel и т. Д. Учитывая теорему о максимальном минимальном расходе, можно ли использовать один из этих алгоритмов дляминимальный разрез на графике с использованием алгоритма максимального потока?Как?

Лучшая информация, которую я нашел до сих пор, заключается в том, что если я найду «насыщенные» ребра, то есть ребра, где поток равен емкости, эти ребра соответствуют минимальному разрезу.Это правда?Это не звучит на 100% правильно для меня.Это правда, что все ребра на минимальном срезе будут насыщенными, но я полагаю, что также могут быть насыщенные ребра, которые находятся за пределами минимального «пути» среза.

Answer 1

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

Answer 2

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

Правильное решение : На самом деле вы должны делать bfs / dfs на Residual-Network Gf ( прочитайте его в википедии ) и отметьте вершины.И затем вы можете выбрать те, которые отмечены как из-вершины и не помечены как-вершины.

Почему «следование ненасыщенным ребрам» недостаточно : учтите, что алгоритм потока насыщает ребра, как показанона картинке.Я обозначил вершины, которые я посещаю, подходом «просто следуя ненасыщенным краям» зеленым цветом.Ясно, что единственный правильный min-cut - это ребро от EF, в то время как предлагаемое решение также вернуло бы AD (и, возможно, даже DE).

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

Answer 3

Итак, чтобы дать точную процедуру получения минимального среза:

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

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

Answer 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

Answer 5

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

Answer 6

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

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

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

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

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

Answer 7

После того, как максимальный поток рассчитан, мы можем искать ребра (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 )