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

  • Thread starter daviddoria
  • Start date
  • Tags
    Cut Graph
In summary, the conversation discusses the concept of a min cut in a graph, specifically looking at the example provided in the link. It is noted that Node 0 is the source and Node 3 is the sink, and the question is raised if the minimum cut is 11. It is also mentioned that there are two min cuts - one separating Node 0 from everything else, and the other separating Node 3 from everything else. The possibility of finding the min cut without a source and sink is also brought up. The conversation concludes with a mention of using the Boost Graph Library to find the min cut, but encountering an issue with the min cut weight being 7.
  • #1
daviddoria
97
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
  • #2
Anyone?
 

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

1. What is a Min Cut on Graph?

A Min Cut on Graph refers to the minimum number of edges that must be removed from a graph in order to disconnect it into two distinct components. It is an important concept in graph theory and has applications in various fields such as network optimization and image segmentation.

2. How is Min Cut on Graph calculated?

The calculation of Min Cut on Graph depends on the specific algorithm being used. One common approach is the Ford-Fulkerson algorithm, which utilizes the concept of flow networks to find the minimum cut. Other algorithms include the Stoer-Wagner algorithm and the Karger algorithm.

3. What is the significance of Min Cut on Graph?

The significance of Min Cut on Graph lies in its practical applications. It can be used to identify the most critical connections in a network, as well as to find the optimal way to divide a graph into smaller components. It also has theoretical importance in the study of graph theory and its applications in various fields.

4. Can Min Cut on Graph be applied to any type of graph?

Yes, Min Cut on Graph can be applied to any type of graph, including directed and undirected graphs, weighted and unweighted graphs, and even multigraphs. However, the specific algorithm used may vary depending on the type of graph and the problem being solved.

5. How can BGL be used to answer David's question about Min Cut on Graph?

BGL (Boost Graph Library) is a popular open-source C++ library for working with graphs. It provides a wide range of algorithms and data structures specifically designed for graph problems. Using BGL, one can easily implement algorithms for finding Min Cut on Graph and other related problems. In David's case, BGL can be used to efficiently find the minimum cut on a given graph and provide an answer to his question.

Similar threads

I Spectral Bisection of Simplest Graph Clearly Incorrect
    • General Math
Replies
5
Views
1K
Max Flow / Min Cut (undirected graph)
    • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
Comp Sci Using Single Source Shortest Path Algorithm to find the longest path
    • Engineering and Comp Sci Homework Help
Replies
4
Views
1K
How Many Edges and Keys in Specific Binomial Min-Heaps?
    • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
Network optimization / Min cost flow problem
    • Precalculus Mathematics Homework Help
Replies
8
Views
4K
Using dual solution and max flow algorithm to find min cost flow
    • Calculus and Beyond Homework Help
Replies
1
Views
2K
Modelling Diesel Cycle in Excel.
    • Engineering and Comp Sci Homework Help
Replies
4
Views
5K
Writing a Paper in Word 2019: Questions & Answers
    • General Discussion
Replies
3
Views
1K
Challenge Math Challenge - October 2021
    • Math Proof Training and Practice
2
Replies
61
Views
7K
B Infrared Detectors & The 2nd Law of Thermodynamics
    • Thermodynamics
5
Replies
152
Views
5K

Hot Threads

Recent Insights

Back
Top