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