183623 (629883), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

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

1. Построить некоторый начальный поток XP^0P = {xB_ijPB^0P}.

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

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

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

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

Рис. 1.10

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

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

Мощность потока XP^{0 P}рассчитаем по формуле (1.4).

f = xB_12B + xB_{13 B}+ xB_14B = xB_46B + xB_56B = 1 + 2 + 2 = 2 + 3 = 5.

Таблица 1.2

Таблица 1.3

Для выполнения п. 2 алгоритма рассчитаем матрицу R – XP^0P, приведенную в табл. 1.4. Элементы (r_ij – x_ij⁰) этой матрицы позволяют судить о насыщенности ребер сети. Нулевые элементы соответствуют насыщенным ребрам, ненулевые – ненасыщенным. С помощью матрицы R – XP^0P можно сформировать подмножество A вершин, в которое можно попасть из истока I, двигаясь только по ненасыщенным путям, выделить их (если поток XP^{0 P} не максимален) и с их помощью увеличить мощность потока.

Таблица 1.4

Таблица 1.5

Вершины подмножества A выделяют постепенно, начиная с истока I. Для этого просматривают первую строку матрицы R – XP^{0 P}( в общем случае строку I) и выписывают номера вершин iB_1B, iB_2B, …, iB_kB, соответствующих ненулевым элементам стоки. Это и будут вершины, в которые можно попасть из истока, перемещаясь по ненасыщенным ребрам. Запишем выявленные вершины в виде списка

Далее рассматривают каждую из вершин iB_{k B}полученного списка и составляют для нее свой список аналогичным образом. При этом вершины, встречающиеся в прежних списках, повторно не выписываются.

Если в этом процессе сток S не встретится, то поток максимален и задача решена; если же, напротив, при составлении очередного списка в нем появится сток S, то поток не максимален и его мощность можно увеличить. Для этого выделяют ненасыщенный путь из истока в сток. Построение ненасыщенного пути из I в S начинают с последнего ребра этого пути. Этим ребром будет (i B_n-1B, S), где i B_{n-1 B}– вершина, в список которой попал сток S. Далее находят ребро (i B_n-2B, i B_n-1B), где i B_n-2B - вершина, в список которой попала вершина i B_n-1B, и т.д., пока не встретится ребро (I, iB_1B), которым начинается искомый ненасыщенный путь.

В данном примере I = 1, S = 6. Построим подмножество A, начиная с вершины. В табл. 1.4 в первой строке ненулевые элементы стоят во втором и третьем столбцах. Следовательно, запишем .

Последовательно составляем списки вершин 2 и 3. Во второй строке матрицы три элемента отличны от нуля: 4, 8, 4. Цифры 4 и 8 соответствуют вершинам 7 и 3, которые уже вошли в подмножество A, поэтому эти вершины повторно в списки не включаем. В четвертом столбце цифра 4 встречается впервые, поэтому включаем ее в список вершины . Переходим к вершине 3. В третьей строке матрицы R – XP^{0 P}ненулевым элементам соответствуют вершины 1 и 2, которые уже встречались в списках. Значит, список вершины 3 будет пустым: … Аналогичным образом составляется список вершины . Повторим полученный набор списков:

( 1.7)

Просматривая списки, замечаем что сток (вершина 6) попал в подмножество A. Значит поток XP⁰ не максимален и существует путь из истока в сток, состоящий из ненасыщенных ребер.

Перейдем к п. 3 алгоритма – выделению ненасыщенных ребер пути из истока в сток и преобразованию имеющегося потока в новый поток большей мощности. В списке (1.7) последним ребром (i _n-1, S) является (4, 6), ребром (i B_n-2B, i B_n-1B) – ребро (2, 4), ребром (I, iB_1B) – ребро (1, 2). Найденный путь по ненасыщенным ребрам из истока 1 в сток 6 пройдет через вершины 1, 2, 4 и 6.

Поскольку ненасыщенный путь найден, то следующим шагом является определение с помощью матрицы R – XP⁰ величины , на которую можно увеличить поток по каждому ребру (i, j) выделенного пути, чтобы получить новый поток X¹ мощности, большей на единиц. Как видно из табл. 1.4., по ребру (1, 2) можно дополнительно пропустить 6 ед., по ребру (2, 4) – 4 ед., по ребру (4, 6) – только 2 ед., так что

Для построения матрицы нового потока X¹ к соответствующим элементам x_ij⁰ матрицы XP⁰ прибавляется найденное значение , после чего возвращаются к п. 2 алгоритма, и т.д. до получения максимального потока.

Характеристики

Список файлов курсовой работы