Построение полного потока

1. Образуем нулевой поток y₀, полагая

" u Î U (y₀(u) = 0).

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

2. 1. Пусть определен поток y _i.

2. 2. В N найдем такой путь W, ведущий из I в S, что

" u Î E (W) ((c (u) - y _i (u)) > 0).

2. 3. Обозначим как d значение

.

2. 4. Переопределим y _i в y _{i +1}по следующей схеме:

y _{i + 1} (u) =

Приведенная процедура при каждом выполнении действий 2 делает полностью нагруженным хотя бы одно еще не полностью нагруженное ребро сети. При этом ребра, полностью нагруженные ранее, также остаются полностью нагруженными.

Поэтому приведенная процедура заканчивает свою работу за конечное время. Кроме того, если y _i является потоком в сети N, то потоком является и функция y _{i +1}.

Предположим, что заданная процедура заканчивает работу за k шагов. Тогда функция y _k образует полный поток в сети N.

Полный поток транспортной сети может быть не максимальным потоком. Например, поток в транспортной сети, приведенной на рис. 6.5, является полным потоком и имеет величину 1.

1 (0)

1 (0)

1 (1) S

Дата добавления: 2015-03-31