algorithm - What is the difference between maximal flow and maximum flow? -

what difference between maximal flow , maximum flow. reading these terms while working on ford fulkerson algorithms , quite confusing. tried on internet, couldn't reasonable answer. believe maximum flow quite clear means maximum amount of flow can transferred source sink in network, maximal flow.

please answer in layman terms if possible.

thanks.

short answer:

think top of mountains, each of them maximal solution, there not place nearby higher them, top of everest mountain has maximum height , therefore maximum solution.

longer answer:

let me explain in geometric terms: think plane (e.g. large peace of paper). each point on plane possible solution problem. height of each point quality of solution corresponding point. in optimization want find optimal solution, i.e. highest point on plane. 1 idea find optimal solution start possible solution in plane , improve little little: each time move point 1 near higher. called local search algorithm. process stops when reach point higher points near it. such point called local optimum. corresponding solution called maximal cannot increase quality of solution moving solution near it. however, maximal solution doesn't need optimal solution, optimal in comparison neighbors.

there common conditions if satisfied not have local optimals on plane not globally optimals. in such situations can use local search algorithms find optimal solution. 1 such condition if plane of solutions convex, intuitively every 2 points have points on line connection them in solution space , quality of each of them can determined relative distance of point 2 endpoints , quality of 2 endpoints. optimization on convex spaces studied in convex optimization.

now, lets go max flow problem. fix graph input. think of each flow satisfies capacity , preservation of flow requirements point. call these valid flows. want find maximum flow. 2 points near each other if can obtain 1 increasing or decreasing flow through path source sink.

we can start flow flow on edges 0 (this valid flow). @ each step find path source sink in updated remaining capacity graph (the weight of each edge amount of capacity not being used) somehow (e.g. using bfs) , increase flow adding this. gives local search algorithm. problem space of solutions not convex , may end flow cannot increase more not maximum flow.

what can do? 1 idea change space of solutions convex one. intuition think star on plane. points inside star not make convex space can turn convex space including more points in our solution space , turning pentagon.

this consider existing flow on original edges of graph new edges (called residual edges) flow on them corresponds decreasing existing flow on original edges. makes space convex , our local search algorithm not stuck on solutions locally optimal not globally optimal.