Условия существования потока

Пусть задан граф 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.