Наибольший поток: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
Строка 1: Строка 1:
'''Наибольший поток''' (''[[Maximum flow]]'') -
'''Наибольший поток''' (''[[Maximum flow]]'')
[[поток]], величина которого наибольшая среди всех потоков по данной
[[поток]], величина которого наибольшая среди всех потоков по данной
сети. По [[теорема Форда-Фалкерсона|теореме Форда-Фалкерсона]] она равна пропускной способности
сети. По [[теорема Форда и Фалкерсона|теореме Форда-Фалкерсона]] она равна пропускной способности
минимального [[разрез|разреза]].
минимального [[разрез|разреза]].
==Литература==
==Литература==
[Берж],  
* Берж К. Теория графов и ее применения. — М.: Изд-во иностр. лит., 1962.


[Кристофидес],  
* Кристофидес Н. Теория графов. Алгоритмический подход. — М.: Мир, 1978.
 
[Липский]
* Липский В. Комбинаторика для программистов. —  М.: Мир, 1988.

Текущая версия от 11:37, 13 мая 2011

Наибольший поток (Maximum flow) — поток, величина которого наибольшая среди всех потоков по данной сети. По теореме Форда-Фалкерсона она равна пропускной способности минимального разреза.

Литература

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