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?

    Thanks!

    David
     
    Last edited by a moderator: May 4, 2017
  2. jcsd
  3. Sep 15, 2009 #2
    Anyone?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Min cut on a graph
  1. Dedekind Cut (Replies: 1)

Loading...