patternMinor
Maximum number of augmenting paths in a network flow
Viewed 0 times
augmentingnumbermaximumflowpathsnetwork
Problem
Let's say we a have flow network with $m$ edges and integer capacities.
Prove that there exists a sequence of at most $m$ augmenting paths that yield the maximum flow.
A good way to start thinking about this is to imagine that we know the maximum flow already. How can we figure the sequence of $m$ paths?
Prove that there exists a sequence of at most $m$ augmenting paths that yield the maximum flow.
A good way to start thinking about this is to imagine that we know the maximum flow already. How can we figure the sequence of $m$ paths?
Solution
I got it myself... The idea is to set the flows of all edges to 0 one by one. It will take M iterations to do so. Once all edges are set to zero it becomes clear that the highest number of augmenting paths can not exceed the number of edges that are 0.And since there are M such edges the maximum number of possible paths is M as well.
Context
StackExchange Computer Science Q#11288, answer score: 2
Revisions (0)
No revisions yet.