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

| cite | improve this answer | |
$\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.

| cite | improve this answer | |
$\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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

The cut you are after is from sB through BA through At.

The sB arrow comes from the left to the right. This direction determines the rest of the calculations. Count it as 2.

But the BA arrow comes from the right to the left. This is discarded, and counted as zero.

The At arrow comes from left to the right. It is counted as 2.

Thus the total, and the maximum flow, is 4. As you state, correctly. 

I am still searching for an  example where the minimum cut is not equal to (i.e. it is inevitably greater than) the maximum flow. The problem is that for complex examples, finding the minimum cut is not trivial. Theory says that there is always a minimum cut, and it is always equal to the maximum flow. 

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Why is the cut you mentioned minimum? $\endgroup$ – xskxzr Apr 7 at 1:33

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.