Поток

Поток (Flow) - целочисленная функция [math]\displaystyle{ f(e) }[/math], определенная на множестве [math]\displaystyle{ E }[/math] дуг транспортной сети и удовлетворяющая следующим условиям:

1) [math]\displaystyle{ 0\leq r(e) \leq f(e) \leq c(e), \; e \in E }[/math];

2) [math]\displaystyle{ \sum \limits_{x \in V}f(x,v) = \sum \limits_{y \in V}f(v,y), \; v \neq s, \; v \neq t }[/math].

Здесь [math]\displaystyle{ r(e) }[/math] называется нижней пропускной способностью дуги [math]\displaystyle{ e }[/math], а [math]\displaystyle{ c(e) }[/math] --- верхней пропускной способностью. Число

[math]\displaystyle{ \Phi_{f} = \sum_{x \in V}f(s,x) = \sum_{y \in V}f(y,t), }[/math]

где [math]\displaystyle{ s }[/math] --- вход сети, а [math]\displaystyle{ t }[/math] --- выход, называется величиной или мощностью потока. Поток, величина которого наибольшая среди всех потоков по данной сети, называется наибольшим или максимальным потоком. Аналогично определяется минимальный поток. Для наибольших потоков справедлива теорема Форда---Фалкерсона:

Величина наибольшего потока равна пропускной способности минимального разреза.

Литература

[Берж],

[Кристофидес],

[Свами-Тхуласираман]