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

 

Пусть дан ориентированный связный граф без циклов G(N ,А). Зададим на нем некоторую функцию С таким образом, что каждой дуге графа (ij)ÎА поставим в соответствие некоторое неотрицательное число с _ij . Назовем дуги графа отрезками транспортного пути, а вершины - транспортными узлами. Числа с _ij назовем пропускными способностями транспортных дуг. Граф в целом тогда будет представлять собой транспортную сеть.

Рассмотрим только однопродуктовые модели транспортной сети. Тогда пропускная способность дуги - это максимально допустимая величина транспортного потока по этой дуге в единицу времени.

Назовем единственный начальный узел транспортной сети источником (s), а единственный конечный узел - стоком (t). Тогда потоком из источника s в сток t будем называть множество неотрицательных чисел f_ij , каждое из которых соответствует дуге (ij)ÎА, если они удовлетворяют следующим условиям (ограничениям):

0 £ f_ij £ c_ij

V ³ 0

Числа f_ij называются дуговыми потоками, а число V - суммарным потоком через сеть.

Первое ограничение требует того, чтобы в каждый транспортный узел входило столько потока, сколько из него выходит. Для стока t множество выходящих дуговых потоков пусто, а весь входящий суммарный поток величиной V поглощается этим узлом. Для источника s, наоборот, множество входящих пусто, а суммарный поток величиной V генерируется этим узлом.

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

Разобьем произвольным образом множество узлов сети на два подмножества Х и  так, что: Х È =N . Разрезом в сети называется множество дуг (ij)ÎА, у которых либо iÎХ, а jÎ , либо jÎХ, а iÎ .  Разрез называется разделяющим, если источник sÎХ, а сток tÎ .

Величиной разреза, или его пропускной способностью называется число С( Х, ) = . Обратите внимание, что суммирование здесь идет только по прямым дугам, т. е. дугам, ведущим от источника к стоку.

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

V£ С( Х, )

ТЕОРЕМА. В любой сети величина максимального потока из s в t равна пропускной способности минимального разреза, разделяющего s и t.

 

⇐ Предыдущая3456789101112Следующая ⇒

Поделиться: