Поток: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Поток''' (''Flow'') - целочисленная функция <math>f(e)</math>, определенная на множеств...) |
(нет различий)
|
Версия от 18:09, 22 декабря 2009
Поток (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] --- выход, называется величиной или мощностью потока. Поток, величина которого наибольшая среди всех потоков по данной сети, называется наибольшим или максимальным потоком. Аналогично определяется минимальный поток. Для наибольших потоков справедлива теорема Форда---Фалкерсона:
Величина наибольшего потока равна пропускной способности минимального разреза.
Литература
[Берж],
[Кристофидес],
[Свами-Тхуласираман]