Может ли кто-нибудь дать мне представление об алгоритме поиска минимального разреза на графике (V, E, c, s, t, f), где f [v] [w] max поток и c [v] [w] - емкость?Алгоритм для поиска минимального разреза при максимальном потоке
Запустите BFS или DFS из исходного узла. Края, на которых вы не можете идти вправо, находятся на минимальном разрезе. При пересечении краев вы должны проверить, c[v][w] > f[v][w]. Узлы, которые вы могли бы достать, лежат на левой стороне минимального разреза, а другие узлы находятся справа.
Вы можете проверить более подробную информацию [здесь] (http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cts=1331121392192&ved=0CC4QFjAA&url=http%3A%2F%2Fciteseerx.ist. psu.edu% 2Fviewdoc% 2Fdownload% 3Bjsessionid% 3D6F1324E4CAF290676E3605F39901D1A4% 3Fdoi% 3D10.1.1.85.7307% 26rep% 3Drep1% 26type% 3Dpdf & е = tkxXT7v-EsrJrAeZwLXzCw & USG = AFQjCNHlUpzr2bHRgY9ecDnxpKDyRgp9Pw & Sig2 = 6P1qlsU54JAjBmMVScfd7Q) –
http://ezekiel.vancouver.wsu.edu/~ cs223/lectures/graphs/maxflow/maxflow.pdf – wcochran
ПРИМЕЧАНИЕ. Если вы не хотите самостоятельно реализовывать алгоритм. И я бы рекомендовал вам не делать этого, если вы просто не хотите учиться, а затем используйте библиотеку JGraphT. Проблема решена отлично - MaxFlow и MinCut все доставлены вам с помощью элегантного API. – 99Sono
Google? Там есть масса вещей, с чем вы столкнулись? –
Возможный дубликат [Как найти минимальный разрез на графике с использованием алгоритма максимального потока?] (Http://stackoverflow.com/questions/4482986/how-can-i-find-the-minimum-cut-on -a-graph-using-a-maximum-flow-algorithm) –
Это реальный вопрос. Те, кто его закрыл, не понимают теорему о минимальном потоке максимума потока. – wcochran