In a flow network, what theorem states that if all edge capacities are integers, there exists a maximum flow where all flow values are integers?
Show answer
Integrality Theorem
The Integrality Theorem is crucial for combinatorial problems. It guarantees that for any flow network with integer capacities, there exists a maximum flow where the flow across every edge is an integer.
Also asked as:
- Which theorem guarantees the existence of a maximum flow consisting entirely of integers if every edge capacity in the network is an integer?