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

Для выполнения п. 2 алгоритма рассчитаем матрицу R – XP0P, приведенную в табл. 1.4. Элементы (rij – xij0) этой матрицы позволяют судить о насыщенности ребер сети. Нулевые элементы соответствуют насыщенным ребрам, ненулевые – ненасыщенным. С помощью матрицы R – XP0P можно сформировать подмножество A вершин, в которое можно попасть из истока I, двигаясь только по ненасыщенным путям, выделить их

(если поток XP0 P не максимален) и с их помощью увеличить мощность потока.

Таблица 1.4

Таблица 1.5

Вершины подмножества A выделяют постепенно, начиная с истока I. Для этого просматривают первую строку матрицы R – XP0 P( в общем случае строку I) и выписывают номера вершин iB1B, iB2B, …, iBkB, соответствующих ненулевым элементам стоки. Это и будут вершины, в которые можно попасть из истока, перемещаясь по ненасыщенным ребрам. Запишем выявленные вершины в виде списка

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

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

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

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

(1.7)

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

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