Editing Maximum flow problem (section)

==Definition==
[[File:Simpe_flow_network.svg|thumb|upright=0.8|A flow network, with source ''s'' and sink ''t''. The numbers next to the edges are the capacities.]]

First we establish some notation:
* Let <math>N = (V, E)</math> be a flow network with <math>s, t \in V</math> being the source and the sink of <math>N</math> respectively. 
* If <math>g</math> is a function on the edges of <math>N</math> then its value on <math>(u,v) \in E</math> is denoted by <math>g_{uv}</math> or <math>g(u,v).</math>

'''Definition.''' The '''capacity''' of an edge is the maximum amount of flow that can pass through an edge. Formally it is a map <math>c: E \to \R^+.</math>

'''Definition.''' A '''flow''' is a map <math>f : E \to \R</math> that satisfies the following:
*''Capacity constraint''. The flow of an edge cannot exceed its capacity, in other words: <math>f_{uv} \leq c_{uv}</math> for all <math>(u, v) \in E.</math>
* ''Conservation of flows.'' The sum of the flows entering a node must equal the sum of the flows exiting that node, except for the source and the sink. Or:
::<math>\forall v \in V \setminus \{s, t\}: \quad \sum_{u:(u, v) \in E, f_{uv}>0} f_{uv} = \sum_{u:(v, u) \in E, f_{vu}>0} f_{vu}.</math>

''Remark''. Flows are skew symmetric: <math>f_{uv} = -f_{vu}</math> for all <math>(u, v) \in E.</math>

'''Definition.''' The '''value of flow''' is the amount of flow passing from the source to the sink. Formally for a flow <math>f : E \to \R^+</math> it is given by:
:<math>|f| = \sum_{v:\ (s,v) \in E} f_{sv} = \sum_{u:\ (u,t) \in E} f_{ut}.</math>

'''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 <math>f_\textrm{max}</math> 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 <math>x</math> units of flow on edge <math>u</math> in one maximum flow, and <math>y > x</math> units of flow on <math>u</math> in another maximum flow, then for each <math>\Delta \in [0, y-x]</math> we can send <math>x+\Delta</math> units on <math>u</math> 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 <math>\Delta</math> values for each pair <math>x, y</math>.