[Solved]: Maximum number of augmenting paths in a network flow

Problem Detail: 

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?

Asked By : 372

Answered By : 372

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11288