Network Flow Examples

Graph Theory · Axiom Academy

Computing maximum flow, minimum cut, and flow-based algorithms Consider the flow network below with source s and sink t . Edge labels show capacities. We'll compute the maximum flow using Ford-Fulkerson, find a minimum cut, verify max-flow min-cut theorem, and convert a matching problem to flow. The minimum cut is S= s,a,b,d , T= c,t , with crossing edges a→c (cap 6, saturated) and d→t (cap 10, saturated). Their capacities sum to 6 + 10 = 16, exactly equal to the maximum flow. Bipartite Matching Problem: Given sets L= L1,L2,L3 and R= R1,R2,R3 with edges: L1-R1, L1-R2, L2-R2, L2-R3, L3-R1 Flow Network Construction: 1. Add source s connected to all vertices in L (capacity 1 each) 2. Direct all bipartite edges from L to R (capacity 1 each) 3. Add sink t connected from all vertices in R (capacity 1 each) 4. Maximum flow value = maximum matching size Excellent work! You've worked through network flow problems. Here's what we learned: Ford-Fulkerson Method: Repeatedly find augmenting paths in the residual graph and push flow along them until no augmenting path exists. The final flow value is the maximum flow. Residual Graph: For each edge with capacity c and flow f, the residual graph has a forward edge with capacity c-f (unused capacity) and a backward edge with capacity f (allowing flow reversal).

This is the written version of the interactive lesson above. See the full Graph Theory course.