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

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

Обозначим через такой поток в графе в котором положено для дуг для дуг Очевидно, что не всегда будет потоком, если множества дуг произвольно, так как поток должен удовлетворять уравнению непрерывности (11.1) при некотором значении Совершенно очевидно, что для того, чтобы представляло поток, множество дуг должно быть или цепью от или циклом в

Для двух заданных потоков через обозначим поток, значение которого на дуге равно

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

где простые цепи (от в графе

— простые циклы в

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

Доказательство. Для графа с потоком построим унитарный граф следующим образом. Множество вершин графа совпадает с множеством вершин X графа Если поток по дуге графа то между вершинами графа проведем параллельных дуг. Граф будет тогда -графом, и так как каждая дуга в соответствует единице потока по дуге в то граф представляет поток

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

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

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

где простая цепь (от простой цикл. Теорема доказана.

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

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

раз, то можно записать в виде

где суммирование понимается как сложение потоков в указанном выше смысле.

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

Рис. 11.4 дает пример потока и его декомпозицию на простые цепи (от и циклы.