Min Cut on Graph: BGL Users Answer David's Question

  • Context: Undergrad 
  • Thread starter Thread starter daviddoria
  • Start date Start date
  • Tags Tags
    Cut Graph
Click For Summary
SUMMARY

The discussion centers on finding the minimum cut in a graph using the Boost Graph Library (BGL). The user, David, questions whether the minimum cut is 11, as he identified two potential cuts: one separating the source (Node 0) from the rest and another separating the sink (Node 3). However, BGL returns a minimum cut weight of 7, prompting inquiries into the discrepancy. The conversation highlights the importance of correctly identifying source and sink nodes in calculating minimum cuts.

PREREQUISITES
  • Understanding of graph theory concepts, particularly minimum cuts.
  • Familiarity with the Boost Graph Library (BGL) version 1.76 or later.
  • Knowledge of source and sink nodes in flow networks.
  • Basic skills in analyzing graph capacities and edge weights.
NEXT STEPS
  • Explore the Boost Graph Library documentation for minimum cut algorithms.
  • Learn about the Edmonds-Karp algorithm for maximum flow and its relation to minimum cuts.
  • Investigate how to visualize graph structures and capacities using graph plotting tools.
  • Study the implications of having multiple minimum cuts in flow networks.
USEFUL FOR

This discussion is beneficial for computer scientists, software developers, and researchers working with graph algorithms, particularly those utilizing the Boost Graph Library for network flow analysis.

daviddoria
Messages
96
Reaction score
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
 
Last edited by a moderator:
Mathematics news on Phys.org
Anyone?
 

Similar threads

Max Flow / Min Cut (undirected graph)
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Spectral Bisection of Simplest Graph Clearly Incorrect
  • · Replies 5 ·
Replies
5
Views
2K
High School Infrared Detectors & The 2nd Law of Thermodynamics
  • · Replies 152 ·
6
Replies
152
Views
11K
Graduate Trying to understand spin networks, or at least SU(2)
  • · Replies 14 ·
Replies
14
Views
7K
Surface roughness in 2D sinusoidal corrugation
  • · Replies 1 ·
Replies
1
Views
5K
Is Alan Turing given too much credit when it comes to computers?
  • · Replies 29 ·
Replies
29
Views
6K
Programs How good is this applied math program?
  • · Replies 13 ·
Replies
13
Views
4K
Mathematica This Week's Finds in Mathematical Physics (Week 267)
  • · Replies 1 ·
Replies
1
Views
4K