Поток

Поток (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] — выход, называется величиной или мощностью потока. Поток, величина которого наибольшая среди всех потоков по данной сети, называется наибольшим или максимальным потоком. Аналогично определяется минимальный поток. Для наибольших потоков справедлива теорема Форда—Фалкерсона:

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

Литература

• Берж К. Теория графов и ее применения. — М.: Изд-во иностр. лит., 1962.

• Кристофидес Н. Теория графов. Алгоритмический подход. — М.: Мир, 1978.

• Свами М., Тхуласираман К. Графы, сети и алгоритмы. — М.: Мир, 1984.