Поток

Материал из WikiGrapp
Перейти к:навигация, поиск

Поток (Flow) — целочисленная функция \,f(e), определенная на множестве \,E дуг транспортной сети и удовлетворяющая следующим условиям:

1) 0\leq r(e) \leq f(e) \leq c(e), \; e \in E;
2) \sum \limits_{x \in V}f(x,v) = \sum \limits_{y \in V}f(v,y), \; v
\neq s, \;  v \neq t.

Здесь \,r(e) называется нижней пропускной способностью дуги \,e, а \,c(e) — верхней пропускной способностью. Число

\Phi_{f} = \sum_{x \in V}f(s,x) = \sum_{y \in V}f(y,t),

где \,sвход сети, а \,tвыход, называется величиной или мощностью потока. Поток, величина которого наибольшая среди всех потоков по данной сети, называется наибольшим или максимальным потоком. Аналогично определяется минимальный поток. Для наибольших потоков справедлива теорема Форда—Фалкерсона:

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

Литература

  • Берж К. Теория графов и ее применения. — М.: Изд-во иностр. лит., 1962.
  • Кристофидес Н. Теория графов. Алгоритмический подход. — М.: Мир, 1978.
  • Свами М., Тхуласираман К. Графы, сети и алгоритмы. — М.: Мир, 1984.