![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Пусть задан граф G =(V, E), каждой дуге (x, y)Î E приписано два числа f (x, y) и c (x, y) – число единиц потока, проходящих по дуге (x, y), и пропускная способность дуги (x, y) соответственно. Пусть в графе G также выделено две вершины s Î V – источник и t Î V – сток. Если при этом выполняются следующие условия:
1) "(x, y)Î E; 0£ f (x, y)£ c (x, y) (7.1)
2) " x Î V, x ¹ s, x ¹ t; å f (x, y)-å f (y, x) = 0 (7.2)
y Î V y Î V
3) å f (s, y) - å f (y, s) = v (7.3)
y Î V y Î V
4) å f (y, t) - å f (t, y) = v (7.4)
y Î V y Î V
то говорят, что в графе G задан поток величины v (из источника в сток передается v единиц потока).
Первое условие для каждой дуги (x, y) ограничивает число единиц потока, проходящих по дуге (x, y), пропускной способностью этой дуги.
Второе условие запрещает утечки потока в промежуточных вершинах (в вершинах, отличных от источника и стока), то есть для каждой промежуточной вершины число приходящих единиц потока в эту вершину должно быть равно числу единиц потока, выходящих из неё.
Третье и четвертое условие задает баланс единиц потока, выходящих из источника и приходящих в сток: сколько единиц потока вышло из источника, столько же единиц потока должно прийти в сток.
Пример графа с заданным потоком величины 7 представлен на рис.7.1.
![]() |
Дата публикования: 2015-01-04; Прочитано: 528 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!