4
$\begingroup$

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.

enter image description here

Could someone explain how to find the minimum cut of this graph? I THINK the minimum capacity is 4.

$\endgroup$
  • $\begingroup$ For an example of this size, enumerate all cuts. $\endgroup$ – Raphael Dec 4 '14 at 14:23
  • $\begingroup$ Are you sure you meant "minimum" capacity or "maximum" capacity? $\endgroup$ – SOFe Mar 22 '19 at 5:01
3
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

For this specific graph, yes, the minimum cut does have capacity $4$: if you only delete one edge, there's still a path from $s$ to $t$, so you need to delete at least two edges. Deleting the edges $sB$ and $At$ disconnects $s$ from $t$ and those edges have total capacity $4$; any other pair of edges has higher capacity, so $4$ is the minimum.

$\endgroup$
0
$\begingroup$

minimum cut gives the maximum capacity, not the minimum capacity in above network, on deleting sB and At, you get the max-flow as 4 the min-flow can be 0 in any network without circulation, for which you dont need to determine the min-cut.

To find min-cut, you remove edges with minimum weight such that there is no flow possible from s to t. The sum of weights of these removed edges would give you the max-flow

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.