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

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

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

2) для любой промежуточной вершины v выполняется равенство

т.е. сумма потоков по дугам, заходящими в v, равна сумме потоков по дугам, исходящими из v.

Пусть j - допустимый поток в транспортной сети D.

Потоком в транспортной сети Т называется неотрицательная вещественная функция, определенная на множестве дуг, удовлетворяющая условиям:

ограниченности: поток по любой дуге сети не превосходит пропускной способности этой дуги;

сохранения: суммарный поток, заходящий в любую вершину сети (кроме истока и стока) равен суммарному потоку, выходящему из этой вершины.

Определение. Дуга x Î X называется насыщенной, если поток по ней равен ее пропускной способности, т.е. если j(x) = c(x). Поток j называется полным, если любой путь в D из v₁ в v_n содержит, по крайней мере, одну насыщенную дугу.

Определение. Поток j называется максимальным, если его величина принимает максимальное значение по сравнению с другими допустимыми потоками в транспортной сети D.

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

(Как упоминалось выше, поток в сети - это функция, определенная на множестве дуг. Величиной потока называется сумма значений этой функции по всем выходным дугам сети (выходные дуги сети - это дуги, инцидентные стоку). Понятия потока и величины потока в сети часто путают, однако между ними существует различие: поток - это функция, а величина потока - число. Советуем это запомнить.)

Алгоритм построения полного потока в транспортной сети D:

Шаг 1. Полагаем "x Î X j(x) = 0 (т.е. начинаем с нулевого потока). Кроме того, полагаем D`=D.

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

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

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

Пример.

Построить полный поток в транспортной сети, изображенной на рисунке 43.

 

 

 

 

Решение.

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

1. h ₁ = v₁v₂v₄v₆, a₁ = min{7, 3, 7} = 3 (рис. 45).

2. h ₂ = v₁v₂v₃v₄v₆, a₂ = min{7-3, 2, 2, 7-3} = 2 (рис. 46).

3. h ₃ = v₁v₃v₅v₆, a₃ = min{8, 2, 9} = 2 (рис. 47).

4. h ₄ = v₁v₂v₅v₆, a₄ = min{7-5, 6, 9-2} = 2 (рис. 48).

Заметим, что в полученной транспортной сети не существует пути из источника в сток, по которому возможно пройти. Следовательно, построенный поток в транспортной сети является полным и j = 3+2+2+2=9.

 

Разрезом сети называется множество, которому принадлежит исток, и не принадлежит сток. Т.е. разрез - это минимальное (в смысле отношения включения) множество дуг, удаление которых “ разрывает” все пути, соединяющие исток и сток.

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

Отыскание минимального разреза - одна из основных задач анализа транспортных сетей.

В силу конечности графа минимальный разрез может быть найден перебором всех разрезов, но этот путь, конечно, неприемлем для достаточно больших графов. Оказывается, что минимальный разрез можно отыскать при помощи максимального потока сети на основании теоремы Форда-Фалкерсона