Flow

Flow --- поток.

Given a network [math]\displaystyle{ G = (V,A;s,t) }[/math] with the source [math]\displaystyle{ s }[/math] and the sink [math]\displaystyle{ t }[/math], let each arc [math]\displaystyle{ e \in A }[/math] have a nonnegative integer number [math]\displaystyle{ c(e) }[/math], the capacity of [math]\displaystyle{ e }[/math], associated with it. A (feasible) flow, of magnitude (or amount) [math]\displaystyle{ \Phi }[/math], from [math]\displaystyle{ s }[/math] to [math]\displaystyle{ t }[/math] in [math]\displaystyle{ G }[/math] is an integer-valued function [math]\displaystyle{ f }[/math] with the domain [math]\displaystyle{ A }[/math] that satisfies the linear equations and inequalities

[math]\displaystyle{ 0 \leq f(e) \leq c(e), }[/math] [math]\displaystyle{ \sum_{w \in V} f(w,v) = \sum_{w \in V} f(v,w), v \neq s,t. }[/math]

The value

[math]\displaystyle{ \Phi(f) = \sum_{w \in V} f(s,w) = \sum_{w \in V} f(w,t) }[/math]

is called the magnitude of [math]\displaystyle{ f }[/math]. The maximum flow problem is that of constructing a flow [math]\displaystyle{ f }[/math] that maximizes [math]\displaystyle{ \Phi }[/math].