Программирование на сетях

Рассмотрим случай 1. Если , то

Построенное разбиение является разрезом A/B. По условию разбиения для любой вершины существует путь из истока в i, состоящий из ненасыщенных ребер, а для любой вершины

такого пути нет. Отсюда следует, что любое ребро (i,j) разреза A/B будет насыщенным (иначе j принадлежало бы A), т.е. xij = rij. Просуммируем все эти равенства по всем и всем и получим

(1.6)

В этом равенстве слева – величина X потока через разрез, справа – пропускная способность R разреза A/B. Из равенства (1.6) по теореме Форда - Фалкерсона следует, что поток X = {xij} является максимальным.

Рассмотрим случай 2. Если то существует путь из ненасыщенных ребер, ведущий из истока в сток. По ребрам этого пути можно пропустить дополнительный поток величиной , где минимум берется по всем ребрам, входящими в этот путь. Потоки xBijB по всем остальным ребрам остаются без изменения. В результате мощность суммарного потока возрастет на величину и это будет новый поток X = {xBijPB1P}.

При объединении двух рассмотренных случаев просматривается следующий алгоритм построения максимального потока:

1. Построить некоторый начальный поток XP0P = {xBijPB0P}.

2. Найти подмножество A вершин, достижимых из истока I по ненасыщенным ребрам. Если в этом процессе сток S не попадет в подмножество A, то построенный поток максимальный и задача решена. Если же сток S попал в A, то перейти к п. 3 алгоритма.

3. Выделить путь из истока I в сток S, состоящий из ненасыщенных ребер, и увеличить поток xBij Bпо каждому ребру этого пути на величину , где минимум берется по ребрам (i,j) упомянутого пути. Это означает, что будет построен новый поток XP1P = {xBijPB1P}. После этого надо вернуться к п. 2 данного алгоритма.

Замечание: при выполнении п. 3 алгоритма на каждом шаге по крайней мере одно из ненасыщенных раннее ребер становится насыщенным. Поскольку число ребер в сети конечно, то через конечное число шагов максимальный поток будет построен.

Разберем на примере предложенный алгоритм.

Рис. 1.10

На рис. 1.10 изображена сеть с истоком I в вершине (1) и стоком в вершине (6). В скобках проставлена пропускная способность ребер в прямом и обратном направлении. В табл. 1.2 показана матрица пропускных способностей сети.

В соответствии с п. 1 алгоритма сформируем на сети первоначальный поток XP0P. В этом потоке по пути 1 – 3 – 5 – 6 перемещаются 2 ед., поскольку ограничивает величину потока ребро (3, 5); по пути 1 – 2 – 5 – 6 перемещается 1 ед., лимитирующим является ребро (2, 5); по пути 1 – 4 – 6 – 2 – 2 ед., и ребро (1, 4) становится насыщенным. Матрица потока представлена на табл. 1.3.

Мощность потока XP0 Pрассчитаем по формуле (1.4).

f = xB12B + xB13 B+ xB14B = xB46B + xB56B = 1 + 2 + 2 = 2 + 3 = 5.

Таблица 1.2

Таблица 1.3

 Скачать реферат