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

Перейдем к п. 3 алгоритма – выделению ненасыщенных ребер пути из истока в сток и преобразованию имеющегося потока в новый поток большей мощности. В списке (1.7) последним ребром (i n-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

Таблица 1.7

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

Таблица 1.8

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