Network flows (intro)
Graph theory · Mathematics
Study notes
Q: Source S to sink T: S→A cap 3, S→B cap 2, A→T cap 2, B→T cap 3, A→B cap 1. Max flow? Try: S→A→T: 2 (A→T caps it). S→B→T: 2 (S→B caps it). Reroute: S→A→B→T: A has 1 left (3-2), A→B cap 1, B→T has 1 left (3-2): +1. Total: 2+2+1 = 5. Min cut? {S} vs rest: 3+2 = 5 ✓ - max-flow min-cut!