 |
Транспортные сети. Теорема форда-фалкерсона о максимальном потоке в транспортной сети
|
|
|
|
Определение.Транспортная сеть − это связный ориентированный граф 
без петель, удовлетворяющий следующим условиям:
1. Существует только одна вершина с нулевой степенью захода; эта вершина называется источником и обозначается через 
.
2. Существует только одна вершина с нулевой степенью исхода; эта вершина называется стоком и обозначается через 
.
3. Каждой дуге 
в сети 
сопоставляется неотрицательное вещественное число, называемое пропускной способностью дуги 
; оно обозначается через 
или 
. (Если не существует дуги, ориентированной из 
в 
, то полагаем, что 
.)
Моделью транспортной сети может служить водопроводная система, в которой сечения труб определяют пропускные способности соответствующих труб, т.е. количество жидкости. которое может пропустить труба за единицу времени.
Потоком 
в транспортной сети является функция, сопоставляющая каждой дуге 
неотрицательное вещественное число 
так, что выполняются следующие условия:
1. 
для любой дуги 
;
2. 
для любого 
.
(Требование 2 − это условие сохранения баланса. Образно говоря, ″сколько втекает в вершину, столько и вытекает из неё″.)
Величина потока 
обозначается через 
и определяется выражением
.
Говорят, что поток 
максимален, если не существует потока такого, что > 
.
Постановка задачи. Найти максимальный поток в заданной транспортной сети.
Пусть 
, 
. Разрез 
, 
определяется как множество дуг 
, у которых начало и конец лежат в разных подмножествах 
и 
. Разрез состоит из прямых дуг, ориентированных из в , и обратных дуг, ориентированных из в . Если 
, 
, то соответствующий разрез называется (
- ) - разрезом. См. рис. 1.
Далее рассматриваются только 
- 
- разрезы.
Пропускная способность 
, 
разреза , определяется как сумма пропускных способностей прямых дуг разреза. Разрез, пропускная способность которого не больше, чем у любого другого разреза, называется минимальным. (В транспортной сети может быть несколько минимальных разрезов, конечно, с одинаковыми пропускными способностями.)
|
|
|
Поток из в определяется как
Аналогично определяется поток из в :
1. Лемма. Для любого - - разреза < 
, 
> имеет место равенство
.
Доказательство. Для фиксированного 
имеем
Суммируя по всем , получаем
С другой стороны,
2. Следствие. Для любого потока и любого - - разреза < , >
(, ).
Доказательство. 
. ∎
Для потока и разреза < , > прямую дугу 
, где 
, 
, будем называть - насыщенной (соответственно, - не 
), если 
(соответственно, если 
). Обратную дугу 
, где 
, 
, будем называть - нулевой (соответственно, - положительной), если 
(соответственно, если 
).
3. Лемма. Если величина потока равна пропускной способности некоторого разреза 
, , то − максимальный поток, а 
− минимальный разрез. Для данного разреза прямые дуги являются насыщенными, а обратные − нулевыми.
Доказательство. Пусть 
− максимальный поток, а 
− минимальный разрез. Так как 
и, по условию, 
, то 
. ∎
Рассмотрим в транспортной сети цепочку 
рёбер
, 
, 
, 
, 
,
соединяющую источник 
и некоторую вершину 
. Заметим, что рёбра получаются из дуг путём снятия ориентации. Соответствующие дуги, составляющие цепочку, могут быть как прямыми, т.е. ориентированными из в , так и обратными, т.е. ориентированными из в .
Для ребра 
полагаем
Цепочка называется - ненасыщенной, если 
. -ненасыщенная цепочка из в называется - дополняющей.
Наличие в сети -дополняющей цепочки позволяет увеличить величину потока, вводя новый поток 
При этом
.
4. Теорема. Поток в транспортной сети максимален тогда и только тогда, когда в сети отсутствуют -дополняющие цепочки.
|
|
|
Доказательство. Необходимость. Если поток максимален, то в сети заведомо нет 
-дополняющих цепочек. В противном случае можно было бы построить новый поток 
, величина которого больше, чем у потока .
Достаточность. Предположим, что сеть с потоком не содержит -дополняющих цепочек. Покажем, что в этом случае − максимальный поток.
Разобьём множество 
вершин сети на два непересекающихся подмножества 
и 
: в 
включим те вершины 
, до которых существуют -ненасыщенные цепочки из источника 
, а в включим остальные вершины, т.е. 
. Очевидно, что 
.
Пусть 
− произвольная дуга разреза 
, 
. Если 
− прямая дуга, т.е. 
, 
, то является -насыщенной дугой, поскольку иначе существует -ненасыщенная цепочка из в 
и 
. Аналогично, если − обратная дуга, т.е. 
, , то является -нулевой дугой 
. Таким образом, 
для прямых дуг и 
для обратных дуг разреза < 
, >. Тогда 
, 
, 
, , 
и 
, 
, 
, . Из леммы 3 вытекает, что < , > − минимальный разрез, а − максимальный поток .∎
5. Следствие (теорема Форда-Фалкерсона). Величина максимального потока в транспортной сети равна пропускной способности минимального разреза.
|
|
|
