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