Maximum flow problem
Definition

First we establish some notation:

Definition. The capacity of an edge is the maximum amount of flow that can pass through an edge. Formally it is a map c: E → R +. {\displaystyle c:E\to \mathbb {R} ^{+}.}

Definition. A flow is a map f: E → R {\displaystyle f:E\to \mathbb {R} } that satisfies the following:

Remark. Flows are skew symmetric: f u v = − f v u {\displaystyle f_{uv}=-f_{vu}} for all (u, v) ∈ E. {\displaystyle (u,v)\in E.}

Definition. The value of flow is the amount of flow passing from the source to the sink. Formally for a flow f: E → R + {\displaystyle f:E\to \mathbb {R} ^{+}} it is given by:

Definition. The maximum flow problem is to route as much flow as possible from the source to the sink, in other words find the flow f max {\displaystyle f_{\textrm {max}}} with maximum value.

Note that several maximum flows may exist, and if arbitrary real (or even arbitrary rational) values of flow are permitted (instead of just integers), there is either exactly one maximum flow, or infinitely many, since there are infinitely many linear combinations of the base maximum flows. In other words, if we send x {\displaystyle x} units of flow on edge u {\displaystyle u} in one maximum flow, and y > x {\displaystyle y>x} units of flow on u {\displaystyle u} in another maximum flow, then for each Δ ∈ {\displaystyle \Delta \in } we can send x + Δ {\displaystyle x+\Delta } units on u {\displaystyle u} and route the flow on remaining edges accordingly, to obtain another maximum flow. If flow values can be any real or rational numbers, then there are infinitely many such Δ {\displaystyle \Delta } values for each pair x, y {\displaystyle x,y}.
punctuation:no_comma, detectable_content:postscript, length_constraints:number_paragraphs[3]