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

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
(не показана 1 промежуточная версия этого же участника)
Строка 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>


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>t</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.