1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Min cut on a graph

  1. Sep 10, 2009 #1
    If I have this graph:
    http://rpi.edu/~doriad/graph.png [Broken]

    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?


    Last edited by a moderator: May 4, 2017
  2. jcsd
  3. Sep 15, 2009 #2
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook