Editing Flow network (section)

==Flows==

Flow functions model the net flow of units between pairs of nodes, and are useful when asking questions such as ''what is the maximum number of units that can be transferred from the source node s to the sink node t?'' The amount of flow between two nodes is used to represent the net amount of units being transferred from one node to the other.

The '''excess''' function {{math|''x''<sub>''f''</sub> : ''V'' → {{mathbb|R}}}} represents the net flow entering a given node {{mvar|u}} (i.e. the sum of the flows entering {{mvar|u}}) and is defined by<math display="block">x_f(u)=\sum_{w \in V} f(w,u) - \sum_{w \in V} f(u, w).</math>A node {{mvar|u}} is said to be '''active''' if {{math|''x''<sub>''f''</sub> (''u'') > 0}} (i.e. the node {{mvar|u}} consumes flow), '''deficient''' if {{math|''x''<sub>''f''</sub> (''u'') < 0}} (i.e. the node {{mvar|u}} produces flow), or '''conserving''' if {{math|''x''<sub>''f''</sub> (''u'') {{=}} 0}}. In flow networks, the source {{mvar|s}} is deficient, and the sink {{mvar|t}} is active.
Pseudo-flows, feasible flows, and pre-flows are all examples of flow functions.

:A '''pseudo-flow''' is a function {{math|''f''}}  of each edge in the network that satisfies the following two constraints for all nodes {{mvar|u}} and {{mvar|v}}:
:*''Skew symmetry constraint'': The flow on an arc from {{mvar|u}} to {{mvar|v}} is equivalent to the negation of the flow on the arc from {{mvar|v}} to {{mvar|u}}, that is: {{math|''f'' (''u'', ''v'') {{=}} −''f'' (''v'', ''u'')}}. The sign of the flow indicates the flow's direction.
:*''Capacity constraint'': An arc's flow cannot exceed its capacity, that is: {{math|''f'' (''u'', ''v'') ≤ ''c''(''u'', ''v'')}}.
:A '''pre-flow''' is a pseudo-flow that, for all {{math|''v'' ∈ ''V'' \{{mset|''s''}}}}, satisfies the additional constraint:
:*''Non-deficient flows'': The net flow ''entering'' the node {{mvar|v}} is non-negative, except for the source, which "produces" flow. That is: {{math|''x''<sub>''f''</sub> (''v'') ≥ 0}} for all {{math|''v'' ∈ ''V'' \{{mset|''s''}}}}.
:A '''feasible flow''', or just a '''flow''', is a pseudo-flow that, for all {{math|''v'' ∈ ''V'' \{{mset|''s'', ''t''}}}}, satisfies the additional constraint:
:*''Flow conservation constraint'': The total net flow entering a node {{mvar|v}} is zero for all nodes in the network except the source {{mvar|s}} and the sink {{mvar|t}}, that is: {{math|''x''<sub>''f''</sub> (''v'') {{=}} 0}} for all {{math|''v'' ∈ ''V'' \{{mset|''s'', ''t''}}}}. In other words, for all nodes in the network except the source {{mvar|s}} and the sink {{mvar|t}}, the total sum of the incoming flow of a node is equal to its outgoing flow (i.e. <math>\sum_{(u,v) \in E} f(u,v) = \sum_{(v,z) \in E} f(v,z) </math>, for each vertex {{math|''v'' ∈ ''V'' \{{mset|''s'', ''t''}}}}).
The '''value''' {{math|{{mabs|''f''}}}} of a feasible flow {{mvar|f}} for a network, is the net flow into the sink {{mvar|t}} of the flow network, that is: {{math|{{mabs|''f''}} {{=}} ''x''<sub>''f''</sub> (''t'')}}. Note, the flow value in a network is also equal to the total outgoing flow of source {{mvar|s}}, that is: {{math|{{mabs|''f''}} {{=}} &minus;''x''<sub>''f''</sub> (''s'')}}. Also, if we define {{math|''A''}} as a set of nodes in {{math|''G''}} such that {{math|''s'' ∈ ''A''}} and {{math|''t'' ∉ ''A''}}, the flow value is equal to the total net flow going out of A (i.e. {{math|{{mabs|''f''}} {{=}} ''f''<sup> out</sup>(''A'') &minus; ''f''<sup> in</sup>(''A'')}}).<ref name=":0" /> The flow value in a network is the total amount of flow from {{mvar|s}} to {{mvar|t}}.