Дискретно-непрерывная математика (стр. 90 )

Упражнение 1. На рис. 6.2 введите второй поток с единичной величиной по каждой дуге и проверьте приведенные выше соотно­шения.

Будем писать φ1<φ2 тогда и только тогда, когда φ1(а)< φ2(а) для каждой аА. Отношения между потоками φ1≤ φ2, φ1> φ2 и φ1≥φ2 определяются ана­логично. Говорят, что поток φ ограничен значениями φ 1 и φ 2, если величина φ (а) заключена между φ1 (a) и φ2(а) для каждой дуги сети. Очевидно, что досгаточным условием ограниченности потока φ потоками φ1 и φ2 является выполнение одного из следующих соотношений: φ1≤ φ≤φ2 или φ2≤ φ≤φ1. Вообще, по некоторым дугам поток φ может быть ограничен сверху потоком φ1, а по другим — потоком φ2.

Потоки φ 1 и φ 2 называются согласованными, если φ1 (a) · φ2(а) для каждой дуги аА. Другими слова­ми, φ1 и φ2 согласованы, если не существует дуг а, для ко­торых φ1 (a) и φ2(а) отличны от нуля и противоположно направлены. Потоки { φ1, φ2, ..., φп} в одной и той же

сети называются совместно согласованными, если они попарно согласованы.

Упражнение 2. Проверить, являются ли потоки упражнения 1 и рис. 6.2 совместно согласованными. Если нет, построить поток, сог­ласованный с потоком рис. 6.2.

Как будет показано ниже, каждый поток можно рас­сматривать состоящим из ряда простых потоков (опре­деленных в следующем разделе), соответствующих цепям и циклам в сети. Более тою, эти простые потоки совместно согласованы, т. е. распространяются в одном направлении по любой заданной дуге. Это простой, но важный факт, имеет место во многих прикладных за­дачах, где конфликтующие (не согласованные) множе­ства потоков не имеют смысла и не могут быть интер­претированы. Связь понятий согласованных и ограни­ченных потоков устанавливается теоремой 1 и играет важную роль при дальнейшем обсуждении.

Теорема 6.1. Если S={φ1, φ2,…., φn}—множество совместно согласованных потоков в сети N, ψ — произ­вольный поток в N и T S, то поток , ограничен потоками ψ и

Доказательство. Пусть а — любая дуга сети. Если φi(a) ≥0 для

i= 1, 2 ,... , п, то, очевидно,

Аналогично, если ср, φi(a) ≤0 для i= 1, 2 ,..., n, то

Так как для любой дуги а имеет место одна из этих ситуаций, то теорема доказана.

Упражнение 3. Пусть φ1— ноток, изображенный на рис. 9.2, и φ2 — поток, построенный в упражнении 2. Взять S={ φ1, φ2} и по­ложить

T={ φ1}. Построить произвольный ноток ψ и проверить утвер­ждение теоремы.

6.4. Простые потоки

Пусть в данной сети N(V, А)С есть множество дуг, образующих простую цепь или простой цикл в соответ­ствующем неориентированном графе. Предположим, что мы ориентируем ребра, проходя эти простые цепи и циклы в одном из возможных направлений. Дуга С будет называться нормальной, если ее вновь введенная ориентация совпадает с исходной и обращенной (инвер­тированной) в противном случае.

Определим φс на А следующим образом:

На рис. 6.4 показаны простая цепь С, ориентированная от v к w, ориентированный простой цикл S и соответст­вующие функции φс и φs.

Рис. 6.4.

Легко проверить, что если С — простая цепь, соеди­няющая v и w и ориентированная от v к w, то φс являет­ся потолом из v к w, величина которого равна 1. Этот поток называется простым потоком по цепи из v в w. Аналогично, если S — цикл, ориентированный в одном из двух направлений, то φs — поток в N, имеющий вели­чину, равную нулю, называется простым потоком по цик­лу. Потоки этих двух типов (и только этих) называют­ся далее простыми потоками. Простые потоки рассмат­риваются как элементарные блоки, из которых можно построить и на которые можно разложить любой поток.

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

Иногда удобно рассматривать другое представление потока, при котором структура сети и величины потоков по дугам задаются структурой некоторого ориентирован­ного графа. Пусть φ обозначает поток в сети N(V, А). Построим ориентированный граф U(N, φ)=(V′, А'), вершины которого находятся во взаимно однозначном соответствии с вершинами сети N. Для каждой дуги аА такой, что φ(а)≠0 в А' мы строим |φ(а)| строго параллельных дуг, соединяющих соответствующие вер­шины. Если a (v, w) и φ (a)>0, то эти дуги ориенти­рованы от v' к w' в графе А'. Если φ (а)<0, то дуги ориентированы от w' к v'. Таким образом, ориентация дуг графа U(N, φ) указывает действительное направле­ние потока в дугах N, а их число — величины соответ­ствующих потоков в дугах сети. Ориентированный граф U(N, φ) называется унитарным графом (с единичной пропускной способностью дуг), соответствующим пото­ку φ в сети N. На рис. 6.5 изображена сеть, задан поток и показан унитарный граф, соответствующий заданному потоку в сети.

Рис. 6.5.

Заметим, что U(N, φ) может не отражать полную структуру N, так как в нем не представлены дуги аА, для которых φ(а)=0. В частности, граф U(N, φ) может оказаться не связным и, следовательно, может не быть сетью. Если отвлечься от этой особенности, то можно считать, что, переходя к сети с единичным потоком по каждой дуге, мы исключили необходимость использова­ния функционального определения потока.

Упражнение 4. Построить унитарный граф, соответствующий расширенной сети, изображенной на рис. 6.3, используя поток, пока­занный на рис. 6.2.

Пусть v' обозначает вершину в U(N, φ), соответ­ствующую вершине v в сети N. Тогда легко видеть, что

В частнрсти, если φ — поток величины k из vi в vj, то U(N, φ) является псевдосимметрическим во всех вер­шинах, исключая, может быть, вершины v′i и v′j, для ко­торых мы имеем

Из известной теоремы следует, что U(N, φ) можно покрыть k простыми путями из vi в vj, возможно, в сочетании с не­сколькими простыми контурами. Этот факт играет центральную роль при последующем построении теории, где потоки общего вида разбиваются на простые потоки или синтезируются из простых потоков. Сформулируем тот же результат на языке потоков.

Теорема 6.2. Поток φ из v в w величины k можно представить как сумму

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

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

Рис. 6.6.

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

Упражнение 5. Применить теорему 2 к потоку, показанному на рис. 6.2, в расширенной сети, как показано на рис. 6.3, и получить его декомпозицию.

6.6. Потоки с ограничениями на дугах

Сеть N=(V, А) называется сетью с ограниченной пропускной способностью, если на А определены две функции α и β, принимающие целочисленные значения, удовлетворяющие соотношению для всех а А, Целые числа α(а) и