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

What is the difference between maximal flow and maximum flow?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
theflowmaximumwhatdifferencebetweenandmaximal

Problem

What is the difference between maximal flow and maximum flow. I am reading these terms while working on Ford Fulkerson algorithms and they are quite confusing. I tried on internet, but couldn't get a reasonable answer. I believe maximum flow is quite clear as it means maximum amount of flow that can be transferred from source to sink in a network, but what exactly is maximal flow.

Please answer in layman terms if possible.

Thanks.

Solution

As saadtaame mentions, maximum usually means global maximum, whereas maximal means local maximum. For example, a maximal independent set in a graph is one to which no vertex can be added (making it a dominating set), while a maximum independent set is one with largest cardinality among all independent set.

My guess is that a maximal flow is one in which every source-to-sink path has a saturated edge (i.e., the flow equals the capacity). Such a flow cannot be improved by pushing more flow through some source-to-sink path.

It so happens that such a flow is also maximum. To see this, consider the residual network, formed by the unsaturated edges. Let $C$ be the connected component containing the source. Since the flow is maximal, $C$ does not contain the sink, and so it forms a source-sink cut in the graph. The value of every flow in the graph is bounded by the capacity of edges crossing the cut. Yet by definition, this is also the value of the flow under consideration, completing the proof.

Context

StackExchange Computer Science Q#23763, answer score: 5

Revisions (0)

No revisions yet.