snippetModerate
How to find a minimum cut of a network flow?
Viewed 0 times
flowhowcutminimumfindnetwork
Problem
I am currently reading the lecture slides from Princeton regarding network flows but I cannot understand how they manage to find out minimum cuts from a directed graph.
Could someone explain how to find the minimum cut of this graph? I THINK the minimum capacity is 4.
Could someone explain how to find the minimum cut of this graph? I THINK the minimum capacity is 4.
Solution
The minimum cut is a partition of the nodes into two groups.
Once you find the max flow, the minimum cut can be found by creating the residual graph, and when traversing this residual network from the source to all reachable nodes, these nodes define one part of the partition. Call this partition $A$. The rest of the nodes (the unreachable ones) can be called $B$. The size of the minimum cut is the sum of the weights of the edges in the original network which flow from a node in $A$ to a node in $B$.
Once you find the max flow, the minimum cut can be found by creating the residual graph, and when traversing this residual network from the source to all reachable nodes, these nodes define one part of the partition. Call this partition $A$. The rest of the nodes (the unreachable ones) can be called $B$. The size of the minimum cut is the sum of the weights of the edges in the original network which flow from a node in $A$ to a node in $B$.
Context
StackExchange Computer Science Q#33834, answer score: 12
Revisions (0)
No revisions yet.