Поток в транспортной сети - Нахождение максимального потока в графе

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

*для любой дуги величина, называемая потоком по дуге, удовлетворяет условию ;

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

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

Для любого допустимого потока в транспортной сети D выполняется равенство:

По определению допустимого потока имеем:

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

Аналогично для каждой дуги, величина входит в левую часть равенства (2) лишь один раз и при этом со знаком минус. С другой стороны, для каждой дуги величина входит в левую часть равенства (2) один раз со знаком плюс (при ) и один раз со знаком минус (при ), что в сумме дает нулевой вклад в левую часть равенства (2). Учитывая сказанное, заключаем, что из равенства (2) следует справедливость равенства (1).

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

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

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

Очевидно, что максимальный поток обязательно является полным (т. к. в противном случае в D существует некоторая простая цепь из V1 в Vn, не содержащая насыщенных дуг, а следовательно, можно увеличить на единицу потоки по всем дугам из и тем самым увеличить на единицу, что противоречит условию максимальности потока). Обратная же, вообще говоря, неверно. Существуют полные потоки, не являющиеся максимальными. Тем на менее полный поток можно рассматривать как некоторое приближение к максимальному потоку.

Похожие статьи




Поток в транспортной сети - Нахождение максимального потока в графе

Предыдущая | Следующая