Поток: различия между версиями

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Поток''' (''Flow'') - целочисленная функция <math>f(e)</math>, определенная на множеств...)
 
Нет описания правки
Строка 1: Строка 1:
'''Поток''' (''Flow'') -  
'''Поток''' (''[[Flow]]'') -  
целочисленная функция <math>f(e)</math>, определенная на множестве <math>E</math> дуг
целочисленная функция <math>f(e)</math>, определенная на множестве <math>E</math> [[дуга|дуг]]
'' транспортной сети'' и удовлетворяющая следующим условиям:
'' [[транспортная сеть|транспортной сети]]'' и удовлетворяющая следующим условиям:


1) <math>0\leq r(e) \leq f(e) \leq c(e), \; e \in E</math>;
1) <math>0\leq r(e) \leq f(e) \leq c(e), \; e \in E</math>;

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

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

Литература

[Берж],

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

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