Graph Theory37 sections · 1633 units
Open in Course

Example - Finding Min Cut

(Small network)

Consider ss connected to aa (capacity 1010) and bb (capacity 55). Both aa and bb connect to tt with capacity 88 each.

You send 88 through sats \to a \to t (limited by ata \to t) and 55 through sbts \to b \to t (limited by sbs \to b). Max flow is 1313. The min cut is {sb,at}\{s \to b,\, a \to t\} with total capacity 5+8=135 + 8 = 13, separating {s,a}\{s, a\} from {b,t}\{b, t\}.

Notice that max flow equals the min cut capacity. This confirms the max-flow min-cut theorem on a concrete example.