Algorithms-1 06

Flow networks, maximum flow problem

Input

Output

Two definitions are equivalent, that is, there exists a flow by the first definition of value iff there exists a flow by the second definition of value

Flow between subsets definition

Flow value via flow between subsets lemma

Cut definition

Flow in an cut lemma

Capacity of a cut definition

Upper bound on a flow in an cut lemma

Upper bound of a maximum flow lemma

Saturated edge definition

Residual network definition

Augmenting path definition

Max-Flow Min-Cut theorem

Ford-Fulkerson algorithm

If all capacities are integers, in each iteration of the while loop, the flow is increased by at least This means that there are at most iterations where is the maximum flow In each iteration, we can find a path using BFS/DFS in Note that for rational numbers, it is possible to multiply (and then divide) by a largest common denominator to obtain integer capacities once again. For irrational numbers however, the algorithm is not guaranteed to converge to a maximum flow or even terminate.