Рис. 11.3. (а) Граф G, потоки {у которого подчеркнуты, (б) Инкреиентальный граф Gd).

достижимого множества R (s) в инкрементальном графе № (). Если t R (s), т. е. если вершина t получила пометку, то в графе G (I) найдена цепь Р от: s к t. Аугментальная цепь в графе G является теперь цепью Р, где дуги т Р в А! являются прямыми дугами, а дуги ш Р в А} являются обратными дугами.

На рис. 11.3(a) дан пример вектора в графе, где подчеркнутые числа задают потоки, а другие числа у дуг задают пропускные способности. На рис. 11.3(6) изображен соответствующий инкрементальный граф G (I).

2.4. Декомпозиция потока

Иногда бывает желательно представить сложный поток как сумму простых потоков. Это бывает полезно не столько из-за того, что такая декомпозиция нужна на практике, а потому что она дает лучшее понимание природы потоков в сетях и служит удобным средством для обоснования многих потоковых алгоритмов.

Обозначим через h о {S) такой поток в графе G, в котором положено lij = h для дуг {xi, Xj) в S и lij = О для дуг {х xj) S, Очевидно, что h о (S) не всегда будет потоком, если множества дуг S произвольно, так как поток должен удовлетворять уравнению непрерывности (11.1) при некотором значении v. Совершенно очевидно, что для того, чтобы h о {S) представляло поток, множество дуг S должно быть или цепью от s к f в G, или циклом в G.

Для двух заданных потоков и л|з через + л|) обозначим поток, значение которого на дуге (х^, Xj) равно 1и + pij.

Теорема 2. Если - произвольный поток (от s к f) в графе G с (целочисленным) значением v, то можно представить в виде

1 = 1о(Р,)+1о{Р,)+...+и(Р,)+1о(ф,) + -}-1.(Ф2)+...+1о(Фь),

где Ру, . . ., Pt, - простые цепи (от s к t) в графе G, а Фу, . . . . . ., Oft - простые циклы в G.

(Pi и Oj не обязательно должны быть различными).

Доказательство. Для графа G = {X, А) с потоком построим унитарный граф G - (Х', А ) следующим образом. Множество вершин X графа G совпадает с множеством вершин X графа G. Если lij - поток по дуге (Xf, Xj) графа G, то между вершинами х\ и xj графа G проведем j;- параллельных дуг. Граф G будет тогда s-графом, и так как каждая дуга в G соответствует единице потока по дуге в G, то граф G представляет поток % в G.

В графе G степени вершин должны удовлетворять (в силу условия непрерывности (11.1)) условиям

do(x*)=dt(xp, Ух.фв- или t%

do{s) = dtit)v.

Если теперь добавить к графу v дуг возврата от вершины к вершине , то в графе G будет существовать эйлеров цикл (см, гл. 9). Удаление этих v дуг из эйлерова цикла даст v цепей от я* к f, которые в совокупности проходят по каждой дуге графа (? точно один раз. Пусть эти цепи будут Р[, Р', . . ., Р' . Цепи Pi не обязательно должны быть простыми, хотя (в силу определения эйлерова цикла) в них не должны содержаться одинаковые дуги,

Но так как любую непростую цепь можно рассматривать как сумму простой цепи (oTSg к tg) и некоторого числа простых попарно непересекающихся по лугам циклов, то

= 1о(Л)+1 (Р2)+...+Ь(.) + 1°(Ф1)+...+1°(Ф4

где Pi - простая цепь (от Sg к tg), а - простой цикл. Теорема доказана.

В общем случае не все циклы и цепи будут различными. Если только первые v цепей п к' циклов различны, причем цепь Pi встречается в списке Р^, . . ., Р„ hi раз, а цикл в списке

(дважды)

Js h

Xj Xj (дважды) (дважды) x

Рис. 11.4. Декомпозиция потока на элементарные (от s к f) потоки по цепям и циклам, (а) Поток %. (б) Цепи и циклы потока %.