Задача максимального потока

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

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

Это означает, что мощность потока от узла 1 к узлу 2 равна 6, а мощность потока от узла 2 к узлу 1 равна 0, т.е. поток отсутствует.

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

Искомую величину максимального потока положим равной нулю.

Итерация 1. Выбираем путь 1-3-6.

P_f = min {6, 2} = 2. Следовательно, мощности потоков на пути 1-3-6 в направлении потока (а именно, значения 6 и 2) уменьшаем на величину P_f =2, а мощности потоков в обратном направлении на пути 1-3-6 (0 и 0) увеличим на P_f = 2. Общий поток станет равным 2 тыс. автомашин в час.

Итерация 2. Выбираем путь 1-4-6.

P_f = min {3, 3} = 3. Следовательно, мощности потоков на пути 1-4-6 в направлении общего потока (3 и 3) уменьшаем на величину P_f =3, а мощности потоков в обратном направлении на данном пути (0 и 0) увеличим на P_f = 3. Общий поток станет равным 2 + 3 = 5 тыс. автомашин в час.

Вовторяем эти действия до тех пор пока не закончатся все возможные варианты добраться их узла №1 в №6.

Больше не существует путей из узла 1 в узел 6 с мощностью превышающей ноль на всем пути (P_f =0), следовательно, 9 тыс. автомашин в час – это нулевой поток.

Определим теперь величину и направление потока на каждой дуге, чтобы достичь максимального потока в 9 тыс. автомобилей. Поток проходит по дуге с величиной, равной разнице между первоначальной и конечной мощностями потока. Так, первоначальная мощность дуги 1-2 равна 2, а конечная – 0, следовательно в направлении от узла 1 к узлу 2 поток имеет мощность
2 – 0 = 2. Сравнивая конечные и начальные мощности потока всех дуг сети, мы получаем конечную модель потоков.

По дороге 5-6 должно проезжать 4 тыс. автомашин в час, чтобы обеспечить максимальный поток.