Поток: различия между версиями
Перейти к навигации
Перейти к поиску
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Поток''' (''[[Flow]]'') | '''Поток''' (''[[Flow]]'') — | ||
целочисленная функция <math>f(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> | ||
2) <math>\sum \limits_{x \in V}f(x,v) = \sum \limits_{y \in V}f(v,y), \; v | :2) <math>\sum \limits_{x \in V}f(x,v) = \sum \limits_{y \in V}f(v,y), \; v | ||
\neq s, \; v \neq t</math> | \neq s, \; v \neq t.</math> | ||
Здесь <math>r(e)</math> называется нижней пропускной способностью дуги <math>e</math> | Здесь <math>\,r(e)</math> называется нижней пропускной способностью дуги <math>\,e,</math> а | ||
<math>c(e)</math> | <math>\,c(e)</math> — верхней пропускной способностью. Число | ||
<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>\,s</math> — [[вход]] сети, а <math>\,t</math> — [[выход]], | ||
называется величиной или мощностью потока. Поток, величина которого | называется величиной или мощностью потока. Поток, величина которого | ||
наибольшая среди всех потоков по данной сети, называется наибольшим | наибольшая среди всех потоков по данной сети, называется наибольшим | ||
или максимальным потоком. Аналогично определяется минимальный поток. | или максимальным потоком. Аналогично определяется минимальный поток. | ||
Для наибольших потоков справедлива теорема | Для наибольших потоков справедлива теорема Форда—Фалкерсона: | ||
:''Величина наибольшего потока равна [[пропускная способность разреза|пропускной способности минимального разреза]]''. | |||
''Величина наибольшего потока равна пропускной способности минимального разреза''. | |||
==Литература== | ==Литература== | ||
* Берж К. Теория графов и ее применения. — М.: Изд-во иностр. лит., 1962. | |||
* Кристофидес Н. Теория графов. Алгоритмический подход. — М.: Мир, 1978. | |||
* Свами М., Тхуласираман К. Графы, сети и алгоритмы. — М.: Мир, 1984. | |||
Текущая версия от 12:48, 22 июня 2011
Поток (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.