7.5. Другое представление потока

Иногда удобно рассматривать другое представление потока, при котором структура сети и величины потоков по дугам задаются структурой некоторого ориентированного графа. Пусть обозначает ноток в сети

Построим ориентированный граф вершины которого находятся во взаимно однозначном соответствии с вершинами сети Для каждой дуги такой, что в А мы строим строго параллельных дуг, соединяющих соответствующие вершины. Если то эти дуги ориентированы от в графе А. Если то дуги ориентированы от Таким образом, ориентация дуг графа указывает действительное направление потока в дугах а их число — величины соответствующих потоков в дугах сети. Ориентированный граф называется унитарным графом (с единичной пропускной способностью дуг), соответствующим потоку в сети На рис. 7.5 изображена сеть, задан поток и показан унитарный граф, соответствующий заданному потоку в сети.

Рис. 7.5.

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

Упражнение 7.4. (см. скан)

Пусть обозначает вершину в соответствующую вершине сети Тогда легко видеть, что

В частнрсти, если поток величины из то является псевдосимметрическим во всех вершинах, исключая, может быть, вершины для которых мы имеем

Из теоремы 3.7 следует, что можно покрыть простыми путями из возможно, в сочетании с несколькими простыми контурами. Этот факт играет центральную роль при последующем построении теории, где потоки общего вида разбиваются на простые потоки или синтезируются из простых потоков. Сформулируем тот же результат на языке потоков.

Теорема 7.2. Поток из величины можно представить как сумму

для некоторого где согласованные простые потоки, из которых являются простыми потоками по цепи, а остальные — простыми потоками по циклу.

Будем называть такое множество согласованных простых потоков декомпозицией потока Естественно, что каждый поток может иметь более одной декомпозиции. На рис. 7.6 показаны, например, две декомпозиции одного и того же потока из и в величины 3.

Рис. 7.6.

Обратим внимание на то, что одна из них содержит простой поток по циклу, а другая — нет.

Упражнение 7.5. (см. скан)