![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Задача максимального потока
Рассматривается сеть с одним узлом входа (источник) и одним узлом выхода (сток). Какова максимальная величина потока (количество машин, сообщений, жидкости и т.д.), который может войти в сетевую систему и выйти из нее в заданный период времени? Предполагается, что поток, вытекающий из узла, равен потоку, втекающему в узел. Под пропускной способностью (или мощностью) дуги понимается верхнее (максимальное) ограничение на поток в этой дуге. Условное изображение в сети для данного случая, например, может выглядеть так Это означает, что мощность потока от узла 1 к узлу 2 равна 6, а мощность потока от узла 2 к узлу 1 равна 0, т.е. поток отсутствует. Пример. Система автодорог «Север-Юг», проходящих через Псковскую область, может обеспечить пропускные способности, показанные на следующей схеме (тыс. автомашин в час).
Искомую величину максимального потока положим равной нулю. Итерация 1. Выбираем путь 1-3-6. Pf = min {6, 2} = 2. Следовательно, мощности потоков на пути 1-3-6 в направлении потока (а именно, значения 6 и 2) уменьшаем на величину Pf =2, а мощности потоков в обратном направлении на пути 1-3-6 (0 и 0) увеличим на Pf = 2. Общий поток станет равным 2 тыс. автомашин в час. Итерация 2. Выбираем путь 1-4-6. Pf = min {3, 3} = 3. Следовательно, мощности потоков на пути 1-4-6 в направлении общего потока (3 и 3) уменьшаем на величину Pf =3, а мощности потоков в обратном направлении на данном пути (0 и 0) увеличим на Pf = 3. Общий поток станет равным 2 + 3 = 5 тыс. автомашин в час. Вовторяем эти действия до тех пор пока не закончатся все возможные варианты добраться их узла №1 в №6. Больше не существует путей из узла 1 в узел 6 с мощностью превышающей ноль на всем пути (Pf =0), следовательно, 9 тыс. автомашин в час – это нулевой поток. Определим теперь величину и направление потока на каждой дуге, чтобы достичь максимального потока в 9 тыс. автомобилей. Поток проходит по дуге с величиной, равной разнице между первоначальной и конечной мощностями потока. Так, первоначальная мощность дуги 1-2 равна 2, а конечная – 0, следовательно в направлении от узла 1 к узлу 2 поток имеет мощность По дороге 5-6 должно проезжать 4 тыс. автомашин в час, чтобы обеспечить максимальный поток.
|