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

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

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

56
задан dingalapadum 23 March 2016 в 12:40
поделиться