Потоки на сетях. Постановка задачи о максимальном потоке

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

Для наглядности будем представлять, что по дугам из истока I в сток S направляется некоторое вещество (груз, ресурс, информация и т.п.)

Определение 12.8. Максимальное количество r_ij вещества, которое может пропустить за единицу времени дуга, идущая из вершины x_i в x_j называется его пропускной способностью. В общем случае r_ij ≠ r_ji .

Определение 12.9. Количество x_ij вещества, проходящего через дугу из вершины x_i в x_j в единицу времени, называется потоком по дуге.

Предполагается, что если из вершины x_i в x_j направляется поток величиной x_ij , то величина потока из x_j в x_i равна –x_ij , то есть x_ji = –x_ij. (12.1)

Принимается также, что x_ii=0. (12.2)

Определение 12.10. Совокупность X={x_ij} потоков по всем дугам сети называется потоком по сети или просто потоком.

Поток по любой дуге не превышает его пропускную способность:

x_ij ≤ r_ij . (12.3)

Если x_ij<r_ij , то дугу между вершинами x_i и x_j называют ненасыщенной.

Общее количество вещества, вытекающего из истока I, совпадает с общим количеством вещества, поступающего в сток S, то есть мощность потока (12.4),

где j – конечные вершины дуг, исходящих из I; i – начальные вершины дуг, входящих в S.

Задача о максимальном потоке формулируется следующим образом: найти совокупность X^*={x^*_ij} потоков x^*_ij по всем дугам сети, которая удовлетворяет условиям (12.1) – (12.3) и максимизирует линейную функцию (12.4).

К задаче о максимальном потоке сводятся задачи: доставка груза; отыскание минимальной по стоимости плана выполнения комплекса работ при заданной его продолжительности; задачи, связанные с наиболее экономным строительством энергетических сетей и т.д.