4194
правки
Поток: различия между версиями
Материал из WEGA
нет описания правки
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. | |||
