Понятие сети

Сеть –это конечный граф без циклов и петель, ориентированный в одном общем направлении от вершины J, являющийся входом ( истоком ) графа, к вершине S, являющейся выходом ( стоком ) графа ( рис. 23 ).

Рис. 23

Максимальноеколичество вещества, которое может пропустить за единицу времени ребро ( i, j ) называется его пропускной способностью.

В общем случае . Если вершины k и l на сети не соединены, то .

На рис. 23 пропускные способности ребер указаны в скобках: первое число – это пропускная способность в направлении от вершины i к вершине j, второе – в противоположном направлении.

Пропускные способности ребер сети можно задать квадратной матрицей n – го порядка ( n – число вершин сети ). Поскольку , то главная диагональ матрицы состоит из нулей. Для сети на рис. 23 матрица R пропускных способностей имеет вид

Количество вещества, проходящего через ребро ( i, j ) в единицу времени, называется потоком по ребру( i, j ). При этом , а = 0.

Совокупность потоков по всем ребрам ( i, j ) сети называют потоком по сетиили просто потоком.

Поток по каждому ребру не превышает его пропускную способность, т.е. ( i, j = 1 - n).

Количество вещества, притекающее в вершину, равно количеству вещества, вытекающего из нее.

Из свойства потоков по ребрам сети следует, что общее количество вещества, исходящего из истока J, совпадает с общим количеством вещества, поступающего в сток S, т.е.

( * )

Линейную функцию ( * ) называют мощностью потока на сети.

Имеет место следующая ЗЛП о максимально потоке: найти совокупность ребер по сети для которых мах при условии

Для решения задачи сеть разбивают на два непересекающихся подмножества таким образом, чтобы истокJ попал в подмножество А, а сток S – в подмножество В. В этом случае говорят, что на сети произведен разрез, отделяющий исток J от стока S.

Совокупность ребер ( i, j ) начальные вершины которых попали во множество А, конечные – во множество В, называется разрезом сети и обозначается А / В.

Например, на рис.23 показан разрез А / В, при котором вершины сети оказались разбитыми на подмножества А={1, 2} и В={3, 4, 5}, а ребрами, образующими разрез, стали ( 1, 3 ), ( 2, 3 ), ( 2, 4 ) и ( 2, 5 ).

Если на сети задач некоторый поток , то ребро (i, j) называют насыщенным при и ненасыщенным при . Так, на рис.23 ребро ( 1, 2 ) насыщенное, как и ребро ( 4, 5 ), ( 3, 5 ), а все остальные ребра насыщенные.

Величина

Представляющая собой сумму пропускных способностей всех ребер разрыва, называется пропускной способностью разреза.

Например, для разреза на рис. 23 R( A / B ) = 4+3+5+6=18.

Величина

представляющая собой сумму потоков по всем ребрам разреза, называется потоком через разрез.

Например, для разреза на рис.23

Х( А / B ) = 3 + 0 + 1 + 1 = 5.

Теорема Форда – Фалкерсона.На любой сети максимальная величина потока из истока J в сток S равна минимальной пропускной способности разреза, отделяющего J oт S.