1. Представление сетей на основе сетевых графов. Задача поиска максимального потока в сети. (ТИПИС)
Потоковая модель - это модель, построенная на основе особого типа графов - сетевых графов.
Дуги являются трубами пропускной способностью равной их весу. Вершины - узлами сопряжения труб. Графы такого типа обычно называются сетями.
Объекты, перемещаемые по дугам таких графов, называются единицами потока.
Количество единиц потока, перемещаемых по дуге, называется потоком в дуге.
Дуги являются ориентированными, т.е. единицы потока могут перемещаться только в одну сторону.
Если по условию задачи существует прямой и обратный поток, то вводится две противоположных дуги.
С помощью моделей данного типа (сетевых моделей) решаются задачи:
a) Расчет характеристик потоков в трубах.
b) Расчет характеристик транспортных систем города.
c) Расчет характеристик грузопотоков в производстве.
Характеристики сети
1) Cij - Пропускная способность дуги ij . Это количество единиц потока, которые может пропустить дуга. Больше этой величины поток в дуге не может принимать значения .
2) Fij - Величина потока по дуге. Это количество единиц потока, перемещаемых по дуге.
3) Div ( V ) . Количество потока вытекающего из вершины V.
Div ( V ) =
еFiv - еFvjВ зависимости от величины Div вершины V подразделяются на: 1) Вершины истоки - S. Это вершины, у которых. Div < 0. Если вершин истоков несколько, то их сводят в одну, соединяя с мнимым источником S0 дугами бесконечной пропускной способности; 2) Вершина называется стоком - T, если Div > 0; 3) Вершины промежуточные Div=0
Количество потока вытекающего из истока = втекающему в сток.
Div ( T ) = Div ( S )
Стандартный сетевой граф должен иметь одну вершину сток и одну вершину исток. Если по условию задачи существует несколько вершин истоков или стоков, то делается следующее преобразование:
- вводится общий мнимый исток S0
- S0 соединяется дугами с частными вершинами истоками
- для частных вершин истоков устанавливается нулевой порождаемый поток
- пропускная способность для дуг соединяющих общий исток с частными устанавливается равной порождаемому потоку в соответствующей вершине до преобразования
- порождаемый поток в общей вершине истоке устанавливается равным бесконечности
Общие характеристики сетевого графа.
Основной характеристикой сетевого графа является его пропускная способность, т.е. сколько единиц потока может переместиться из истока в сток при неограниченном порождаемом потоке в истоке.
Пропускная способность сетевого графа определяется с одной стороны пропускной способностью составляющих дуг, с другой их последовательностью соединения.
Пропускная способность определяет величину установившегося потока в сети, т.е. когда единицы потока достигли стока и подача единиц из истока не ограничена.
Кроме установившегося, различают начальный поток сети - это поток, в котором не все единицы достигли стока, и конечный поток-это поток, когда подача единиц потока в истоке прекращена, однако в сети единицы потока еще присутствуют.
Методы задания сетевых графов.
1) Графический
2) С помощью двух матриц смежности C и F
Алгоритм расчета максимальной пропускной способности сети (величины установившегося потока).
Исходные данные.
Дано: G
бU,Vс - ориентированный граф, который является сетью.С(N,N) - матрица смежности, задающая пропускную способность дуг графа.
Найти: W =
Sf sj =Sf is - количество потока, протекающего по сети.Алгоритм поиска максимального потока построен на поиске увеличивающих цепей для какого-либо начального потока.
Цепь является увеличивающей, если она состоит из дуг, позволяющих увеличить достигнутый в ней результирующий поток. Дуги, позволяющие увеличить результирующий поток в цепи, называются допустимыми. Дуга является допустимой, если поток в ней совпадает с направлением цепи и имеет значение меньшее, чем пропускная способность. Такие допустимые дуги называются согласованными. Величина, на которую согласованная дуга позволяет повысить поток по цепи рассчитывается как разность между ее пропускной способностью и достигнутой величиной потока.
Кроме того, допустимой является дуга, в которой поток совпадает с направлением цепи. Такие допустимые дуги называются несогласованными. Величиной, на которую позволяет увеличить поток в цепи несогласованная дуга является достигнутое в ней значение потока.
Результирующий поток по цепи определяется потоком в самой "узкой" дуге , то есть дуге с минимальным потоком, следовательно величина на которую можно увеличит результирующий поток определяется минимальным значением увеличения, определенным для всех дуг.
Задаться любым потоком, можно нулевым, т.е. потоком в котором во всех трубах поток нулевой f ij = 0.
По любому алгоритму поиска найти увеличивающую цепь, соединяющую источник и сток.
Если такая цепь есть то: пересчитать потоки, передаваемые по ее дугам, c учетом достигнутой величины увеличения . Переход к п.1, иначе: переход к п.2
Подсчитать W - величину потока, вытекающего из истока
W =
Sf sjДля поиска увеличивающей цепи можно использовать алгоритм поиска в ширину, в котором из всех смежных дуг для дальнейшего следования необходимо брать только допустимые дуги и из них отдавать предпочтения тем, которые обеспечивают максимальную величину увеличения потока.
Лучшие результаты обеспечивают алгоритмы, в которых для поиска увеличивающей цепи используется методы направленного поиска цепи с наименьшей длинной (алгоритм Дейкстры), где в качестве критерия оптимальности принимается величина наибольшего увеличения результирующего потока. Критерий "Макси-мина".
