Доказательство. Пусть N = ((V, U), c) - некоторая транспортная сеть.
Пусть N = ((V, U), c) - некоторая транспортная сеть.
Последовательность Н = x 1,..., xk разных вершин этой сети называется цепью, если
" i = 1,..., k - 1 ((xi, xi +1)Î U Ú (xi +1, xi)Î U).
То есть любые две соседние вершины цепи соединяются между собой ребром одним из двух возможных способов. При этом, если (xi, xi +1)Î U, то такое ребро называется прямым. Если же (xi +1, xi)Î U, то такое ребро называется обратным.
Множество всех прямых и обратных ребер цепи Н обозначается как U (H). Множества прямых и обратных ребер той же цепи обозначаются как U+ (H) и U- (H) соответственно.
Построим по шагам поток y в транспортной сети N.
1. Положим i = 0 и методом насыщения дуг построим некоторый полный поток y i в сети N.
2. Пока это возможно, повторяем следующие действия.
2.1. Найдем цепь Н = x 1, x 2,..., xk - 1, x k, где I = x 1 и S = x k,для которой выполняются условия:
" u Î U+ (H) (y i (u) < c (u)); (1)
" u Î U- (H) (y i (u) > 0). (2)
2.2. Если такая цепь H найдена, то вычислим значения:
d 1 = min (c (u)- y i (u)), где u Î U+ (H).
d 2 = min (c (u)), где u Î U- (H).
d = min (d 1, d 2).
(Заметим, что d является целым числом и d > 0.)
2.3. Определим функцию y i+ 1 следующим соотношением:
y(u)+ d, если u Î U+ (H)
y i+ 1(u) = y(u)- d, если u Î U- (H)
y(u), если u Ï U (H).
3. Увеличим значение i на 1.
Действие 2 в приведенной процедуре повторяется конечное число раз, поскольку на всяком шаге величина новой функции y i+ 1 на одном из ребер, ведущих в сток сети, увеличивается на целое число d > 0. Поэтому число повторений выполнения действия 2 не превышает суммы пропускных способностей всех ребер, ведущих в S.
Пусть y k - последняя из функций, определяемых при выполнении приведенной процедуры. Положим y = y k.
Покажем, что y является максимальным потоком в сети N.
1. y является потоком, поскольку если некоторая функция y i - это поток, то действие 2 по потоку y i определяет новый поток y i+ 1.
Действительно, при определении y i+ 1 значения потока изменяются только для ребер из U (H). При этом поток в прямых ребрах возрастает, а в обратных убывает на такую величину, что новое значение для каждого ребра сети не превосходит пропускную способность этого ребра и не становится отрицательным. Поэтому для y i+ 1 выполняется первое условие определения потока в сети.
Для всякой внутренней вершины цепи H сохраняется равенство суммарных входного и выходного потоков.
Действительно, пусть aj - внутренняя вершина из H.
Рассмотрим возможные случаи прохождения ребер из U (H) через вершину aj
1. aj -1 aj a j +1
При этом входящий и выходящий потоки вершины aj увеличиваются на d.
2. aj -1 aj aj +1
В этом случае входящий поток для вершины aj по одному входному ребру возрастает на d, а по другому входному ребру убывает на d, а его величина оказывается неизменной, совпадающей с выходным потоком этой вершины.
aj -1 aj aj +1
3.
Входящий и выходящий потоки для aj уменьшаются на d, оставаясь равными.
aj -1 aj aj +1
4.
Выходящий поток вершины aj по одному ребру возрастает на d, а по другому ребру убывает на d.
Во всех случаях суммарный входящий поток вершины a j для y i + 1 остается равным суммарному выходящему потоку этой вершины, если такое равенство имеет место для y i. Поэтому для y i + 1 выполняется и второе условие определения потока в сети.
2. Покажем, что y является максимальным потоком.
2.1. Обозначим как R - множество таких вершин сети N, что a R тогда и только тогда, когда для всякой цепи H, начинающейся в истоке I и заканчивающейся в a, не выполняются условия
" u Î U+ (H) (y i (u) < c (u)) (1)
" u Î U- (H) (y i (u) > 0) (2)
Множество R является непустым, так как из определения функции y следует, что S Î R.
Множество остальных вершин сети обозначим F. Так как для I выполнены условия (1) и (2). Действительно, единственная цепь, ведущая из I в I, состоит из вершины I. Для этой цепи выполняются условия (1) и (2).Значит I F и F не является пустым множеством.
2.2. Обозначим как L множество ребер сети N, начала которых принадлежат множеству F, а концы - множеству R.
Всякий путь W из I в S содержит хотя бы одно ребро из L, поскольку его начало лежит в F, а конец - в R. Следовательно, в последовательности W содержатся две последовательно идущие вершины a и b, для которых a Î F и b Î R. Поэтому L образует сечение сети N.
2.3. Все ребер сечения L справедливо свойство:
" u Î L (y(u) = c (u)).
То есть все ребра L полностью нагружены потоком. В противном случае, если ребро u = (a, b),является недогруженным, то вершина b такого ребра из L, не может принадлежать R.
Действительно, если y(u) < c (u), то найдется цепь, ведущая в b, которая проходит через u, в которой все прямые ребра недогружены, а по обратным ребрам течет ненулевой поток. Такая цепь может быть получена добавлением вершины b к цепи, ведущей в a, для которой выполнены условия (1) и (2). Последнее ребро для такой цепи является прямым и оно недогружено.Поэтому bÎ F, а это противоречит предположению, что bÎ R.
2.4. Если u = (a, b) - это ребро, для которого a R и b F, то y(u) = 0.
Чтобы убедиться в справедливости последнего свойства, предположим противное: существует такое ребро u = (a, b), что a R, b F иy(u) > 0.
Тогда, так как b F, то существует цепь H = I,..., b, для которой выполнены условия (1) и (2). Но тогда эти же условия выполнены и для цепи H * = I,..., b, a. Поскольку в ней вершины a и b связаны обратным ребром, по которому течет ненулевой поток.
Поэтому a F, что противоречит предположению о том, что a R.
Следовательно, поток между вершинами множеств F и R может протекать лишь в одном направлении.
2.5. Поэтому суммарный поток, проходящий через ребра сечения L, в дальнейшем распространяется только между вершинами множества R и полностью входит в сток S.
Следовательно, справедливо соотношение y(N) = c (L).
То есть y - это максимальный поток, так как его величина совпадает с пропускной способностью сечения L, величину которого не превосходит ни один поток в сети.
Дата добавления: 2015-09-27 | Просмотры: 373 | Нарушение авторских прав
|