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

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
Строка 13: Строка 13:
<math>\Phi_{f} = \sum_{x \in V}f(s,x) = \sum_{y \in V}f(y,t),</math>
<math>\Phi_{f} = \sum_{x \in V}f(s,x) = \sum_{y \in V}f(y,t),</math>


где <math>s</math> --- вход сети, а <math>t</math> --- выход,
где <math>s</math> --- [[вход]] сети, а <math>t</math> --- [[выход]],
называется величиной или мощностью потока. Поток, величина которого
называется величиной или мощностью потока. Поток, величина которого
наибольшая среди всех потоков по данной сети, называется наибольшим
наибольшая среди всех потоков по данной сети, называется наибольшим

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

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

Литература

[Берж],

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

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