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

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

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

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

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

Транспортной сетью называется орграф 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 называется полным, если любой путь в сети из источника в сток содержит, по крайней мере, одну насыщенную дугу.