daviddoria
- 96
- 0
If I have this graph:
http://rpi.edu/~doriad/graph.png
Node 0 is the source and Node 3 is the sink. Is the min cut 11 (the minimum sum of capacities of edges cut to partition the graph into two parts)? There are two min cuts, correct? One that separates 0 from everything else, and the other which separates 3 from everything else.
If you didn't have a source and sink - could you still find the min cut on the graph? (i.e. just looking at the capacities of all of the edges)?
I am trying to do this with Boost Graph Library but it keeps telling me the min cut weight is 7. Anyone know why this would be? Are there any BGL users here?
Thanks!
David
http://rpi.edu/~doriad/graph.png
Node 0 is the source and Node 3 is the sink. Is the min cut 11 (the minimum sum of capacities of edges cut to partition the graph into two parts)? There are two min cuts, correct? One that separates 0 from everything else, and the other which separates 3 from everything else.
If you didn't have a source and sink - could you still find the min cut on the graph? (i.e. just looking at the capacities of all of the edges)?
I am trying to do this with Boost Graph Library but it keeps telling me the min cut weight is 7. Anyone know why this would be? Are there any BGL users here?
Thanks!
David
Last edited by a moderator: