Page 1 of 1

Minimum cut

Posted: Sat Jun 09, 2007 9:11 pm
by blowguy
I know some algorithms how to find minimum cut in a graph, but is there an algorithm that gives the set of edges that form the min cut?

Posted: Mon Jun 11, 2007 12:26 pm
by Observer
Hi,

This question has been asked before here. Check this out:
http://online-judge.uva.es/board/viewtopic.php?t=2537

In short, by the famous Maxflow-mincut theorem, you can get a mincut (a partition of the original graph) from a maxflow. Please go through the proof of the theorem again.