Graph Theory37 sections · 1633 units
Open in Course

Integer Flow Theorem

Integral capacities yield i...

If all capacities are integers, then there exists a maximum flow where all flow values are integers. Edmonds-Karp guarantees this. Why?

Each augmentation increases flow by an integer (the bottleneck is the minimum of integer capacities). You start at 00, so the final flow is an integer. This is useful in problems where flow represents discrete items, like people or packages. You do not need to worry about fractional flows.