Определение сети, потока и разреза

Граф, некоторые вершины которого выделены, называется сетью. Выделенные вершины называются полюсами сети. Например, дерево с корнем можно рассматривать как однополюсную сеть.

Вершины, отличные от полюсов, называются внутренними вершинами сети. Ребро, инцидентное хотя бы одному полюсу, называется полюсным ребром. Остальные ребра называются внутренними.

-полюсником называется сеть с полюсами, разбитыми на два класса: входных и выходных полюсов. (1, 1)-полюсник называется также двухполюсной сетью.

Далее будут рассматриваться только двухполюсные сети, которые будем называть просто сетями. Будем называть также цепью (без указания концов) элементарную цепь между полюсами сети. В противном случае будем указывать концы цепи и называть ее цепочкой.

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

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

Для каждой вершины сети обозначим через множество всех дуг, входящих в , а через – выходящих из . Для источника и стока имеем .

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

1) , ; (1)

2) , (, , ). (2)

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

На рис. 1 приведен пример сети , в которой каждой дуге приписана двойка .

8, 8 7, 6

2, 2 2, 0

5, 5

Рис. 1. Пример транспортной сети

Если сложить уравнения сохранения для всех вершин, то останутся только члены, соответствующие дугам и :

.

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

.

Поток в сети, имеющий наибольшую величину, называется максимальным.

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

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

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

.

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