Программирование на сетях (стр. 3 из 4)
Замечание: при выполнении п. 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
| i/j | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 0 | 7 | 4 | 2 | 0 | 0 |
| 2 | 3 | 0 | 8 | 4 | 1 | 0 |
| 3 | 6 | 8 | 0 | 0 | 2 | 0 |
| 4 | 5 | 9 | 0 | 0 | 8 | 4 |
| 5 | 0 | 5 | 2 | 3 | 0 | 5 |
| 6 | 0 | 0 | 0 | 6 | 7 | 0 |
Таблица 1.3
| i/j | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 0 | 1 | 2 | 2 | 0 | 0 |
| 2 | -1 | 0 | 0 | 0 | 1 | 0 |
| 3 | -2 | 0 | 0 | 0 | 2 | 0 |
| 4 | -2 | 0 | 9 | 0 | 4 | 0 |
| 5 | 0 | -1 | -2 | 0 | 0 | 3 |
| 6 | 0 | 0 | 0 | -2 | -3 | 0 |
Для выполнения п. 2 алгоритма рассчитаем матрицу R – XP0P, приведенную в табл. 1.4. Элементы (rij – xij0) этой матрицы позволяют судить о насыщенности ребер сети. Нулевые элементы соответствуют насыщенным ребрам, ненулевые – ненасыщенным. С помощью матрицы R – XP0P можно сформировать подмножество A вершин, в которое можно попасть из истока I, двигаясь только по ненасыщенным путям, выделить их (если поток XP0 P не максимален) и с их помощью увеличить мощность потока.
Таблица 1.4
| i/j | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 0 | 3 | 2 | 2 | 0 | 0 |
| 2 | -3 | 0 | 0 | 2 | 1 | 0 |
| 3 | -2 | 0 | 0 | 0 | 2 | 0 |
| 4 | -2 | -2 | 0 | 0 | 0 | 4 |
| 5 | 0 | -1 | -2 | 0 | 0 | 3 |
| 6 | 0 | 0 | 0 | -4 | -3 | 0 |
Таблица 1.5
| i/j | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 0 | 6 | 2 | 0 | 0 | 0 |
| 2 | 4 | 0 | 8 | 4 | 0 | 0 |
| 3 | 8 | 8 | 0 | 0 | 0 | 0 |
| 4 | 7 | 9 | 0 | 0 | 8 | 2 |
| 5 | 0 | 6 | 4 | 3 | 0 | 2 |
| 6 | 0 | 0 | 0 | 8 | 10 | 0 |
Вершины подмножества A выделяют постепенно, начиная с истока I. Для этого просматривают первую строку матрицы R – XP0 P( в общем случае строку I) и выписывают номера вершин iB1B, iB2B, …, iBkB, соответствующих ненулевым элементам стоки. Это и будут вершины, в которые можно попасть из истока, перемещаясь по ненасыщенным ребрам. Запишем выявленные вершины в виде списка
Далее рассматривают каждую из вершин iBkBполученного списка и составляют для нее свой список аналогичным образом. При этом вершины, встречающиеся в прежних списках, повторно не выписываются.
Если в этом процессе сток S не встретится, то поток максимален и задача решена; если же, напротив, при составлении очередного списка в нем появится сток S, то поток не максимален и его мощность можно увеличить. Для этого выделяют ненасыщенный путь из истока в сток. Построение ненасыщенного пути из I в S начинают с последнего ребра этого пути. Этим ребром будет (iBn-1B, S), где iBn-1 B– вершина, в список которой попал сток S. Далее находят ребро (iBn-2B, iBn-1B), где iBn-2B - вершина, в список которой попала вершина iBn-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 не максимален и существует путь из истока в сток, состоящий из ненасыщенных ребер.
Перейдем к п. 3 алгоритма – выделению ненасыщенных ребер пути из истока в сток и преобразованию имеющегося потока в новый поток большей мощности. В списке (1.7) последним ребром (in-1, S) является (4, 6), ребром (i Bn-2B, i Bn-1B) – ребро (2, 4), ребром (I, iB1B) – ребро (1, 2). Найденный путь по ненасыщенным ребрам из истока 1 в сток 6 пройдет через вершины 1, 2, 4 и 6.
Поскольку ненасыщенный путь найден, то следующим шагом является определение с помощью матрицы R – XP0 величины
, на которую можно увеличить поток по каждому ребру (i, j) выделенного пути, чтобы получить новый поток X1 мощности, большей на 
единиц. Как видно из табл. 1.4., по ребру (1, 2) можно дополнительно пропустить 6 ед., по ребру (2, 4) – 4 ед., по ребру (4, 6) – только 2 ед., так что 
Для построения матрицы нового потока X1 к соответствующим элементам xij0 матрицы XP0 прибавляется найденное значение
, после чего возвращаются к п. 2 алгоритма, и т.д. до получения максимального потока.Прибавим величину
к элементам x120 = 1, x240 = 0 и x460 = 2, обозначающим ненасыщенный путь (по всем остальным ребрам величина потока не изменится). Приходим к матрице нового потока X1 (см. табл. 1.5), мощность которого равна 7 ед. Этот поток вновь надо исследовать на оптимальность, т. е. вернуться к п. 2 алгоритма. Вновь составляем матрицу R – X1 (см. табл. 1.5), а по ней – списки вершин, достижимых из истока I по ненасыщенным путям: 
Из этих списков видно, что сток 6 снова в подмножестве A, а путь, ведущий в него, состоит из ненасыщенных ребер (1, 2), (2, 4), (4, 5), (5, 6). Новый поток X2, (его матрица представлена в табл. 1.6, получается преобразованием потока X1, если увеличить на
потоки по указанным ребрам найденного ненасыщенного пути. Мощность нового потока X2 составляет 9 ед. Для исследования этого потока составляется матрица R – X2 (табл. 1.8), а по ней – списки. 
(1.8)Таблица 1.6
| i/j | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 0 | 5 | 2 | 2 | 0 | 0 |
| 2 | -5 | 0 | 0 | 4 | 1 | 0 |
| 3 | -2 | 0 | 0 | 0 | 2 | 0 |
| 4 | -2 | -4 | 0 | 0 | 2 | 4 |
| 5 | 0 | -1 | -2 | -2 | 0 | 5 |
| 6 | 0 | 0 | 0 | -4 | -5 | 0 |
Таблица 1.7
| i/j | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 0 | 4 | 2 | 0 | 0 | 0 |
| 2 | 6 | 0 | 8 | 2 | 0 | 0 |
| 3 | 8 | 8 | 0 | 0 | 0 | 0 |
| 4 | 7 | 11 | 0 | 0 | 8 | 0 |
| 5 | 0 | 6 | 4 | 3 | 0 | 2 |
| 6 | 0 | 0 | 0 | 10 | 10 | 0 |
По спискам (1.8) видно, что сток 6 не попал в подмножество A вершин, достижимых из истока по ненасыщенным ребрам. Значит поток X2 максимален. Нанесем его на сеть с указанием направления потоков по отдельным ребрам (см. рис. 1.11).
Таблица 1.8
| i/j | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 0 | 4 | 2 | 0 | 0 | 0 |
| 2 | 6 | 0 | 8 | 2 | 0 | 0 |
| 3 | 8 | 8 | 0 | 0 | 0 | 0 |
| 4 | 7 | 11 | 0 | 0 | 8 | 0 |
| 5 | 0 | 6 | 4 | 3 | 0 | 2 |
| 6 | 0 | 0 | 0 | 10 | 10 | 0 |
