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.
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.
Boils down to knowing the difference between maximal and maximum. maximal is relative whereas maximum is absolute. I guess, maximal flow means maximum flow in a sub-network but I'm not sure.
