Построения полного потока в сети

Потоки в сетях

Полный поток в транспортной сети

Теория транспортных сетей возникла при решении задач, связанных с организацией перевозки грузов. Тем не менее понятие потока на транспортной сети, алгоритм нахождения потока наибольшей величины и критерий существования потока, насыщающего выходные дуги сети, оказались полезными для многих других прикладных и теоретических вопросов комбинаторного характера.

Введем основные понятия данной теории.

Транспортной сетью называется орграф D = (V, X) с множеством вершин V = {v₁, …, v_n}, для которого выполняются условия:

1) существует одна и только одна вершина v₁, называемая источником, такая, что Г^-1 (v₁) = Æ (т.е. ни одна дуга не заходит в v₁),

2) существует одна и только одна вершина v_n, называемая стоком, такая, что Г(v_n) = Æ (т.е. из v_n не исходит ни одной дуги),

3) каждой дуге xÎ X поставлено в соответствие целое число c (x) ³ 0, называемое пропускной способностью дуги.

Функция j(x), определенная на множестве X дуг транспортной сети D и принимающая целочисленные значения, называется допустимым потоком (или просто потоком) в транспортной сети D, если

1) для любой дуги xÎ X величина j(x), называемая потоком по дуге x, удовлетворяет условию 0 £ j(x) £ c(x),

2) для любой промежуточной вершины v сумма потоков по дугам, заходящим в v, равна сумме потоков по дугам, исходящим из v.

Величиной потока j в транспортной сети D называется величина, равная сумме потоков по всем дугам, заходящим в сток, или, что то же самое сумме потоков по всем дугам, исходящим из источника.

Дуга xÎ X называется насыщенной, если поток по ней равен ее пропускной способности. Поток j называется полным, если любой путь в сети из источника в сток содержит, по крайней мере, одну насыщенную дугу.

А л г о р и т м

построения полного потока в сети

Данные: транспортная сеть D, заданная матрицей пропускных способностей дуг.

Результат: полный поток в сети.

1. Полагаем для любой дуги xÎ Х j(x) = 0 (начинаем с нулевого потока).

2. Полагаем D* = D.

1. Удаляем из орграфа D* все дуги, являющиеся насыщенными при потоке j в транспортной сети D. Полученный орграф снова обозначим через D*.

2. Ищем в D* простую цепь m из v₁ в v_n. Если такой цепи нет, то j - искомый полный поток в транспортной сети D. В противном случае переходим к шагу 5.

3. Увеличиваем поток j(x) по каждой дуге x из m на одинаковую величину a> 0 такую, что, по крайней мере, одна дуга из m окажется насыщенной, а потоки по всем остальным дугам из m не превышают их пропускных способностей. При этом величина потока j также увеличится на a, а сам поток j в транспортной сети D остается допустимым. После этого перейдем к шагу 3.