HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Maximum number of augmenting paths in a network flow

Submitted by: @import:stackexchange-cs··
0
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?

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.