Поток

Материал из WikiGrapp
Версия от 18:09, 22 декабря 2009; Glk (обсуждение | вклад) (Создана новая страница размером '''Поток''' (''Flow'') - целочисленная функция <math>f(e)</math>, определенная на множеств...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

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

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

Литература

[Берж],

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

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