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

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

Приводимые ниже рассуждения несколько предвос­хищают результаты, строго обоснованные в главе 6, где, в частности, показывается, что максимально допус­тимый поток между двумя определенными вершинами в направленном графе равен минимальной пропускной способности разреза, разделяющего эти вершины. Там же предлагается систематический метод определения та­кого критического разреза.

Таким образом, матрица В однозначно определяет матрицу Т. Одна из интересных задач заключается в оп­ределении условий, при которых данная симметрическая матрица может рассматриваться (реализуется) как тер­минальная матрица пропускных способностей Т. Другая задача состоит в том, чтобы найти систематическую процедуру получения В из T (здесь может быть несколь­ко матриц В), которая обеспечивала бы минимально возможную сумму пропускных способностей ребер. Эта задача известна как задача синтеза сети связи с задан­ными терминальными характеристиками.

Beрнемся к задаче-реализуемости матриц. Рассмот­рим разрез, соответствующий минимальному элементу t1 в Т. Этот разрез разделяет граф на две компоненты: С1, С2, и позволяет записать Т в виде

где ТC1 и ТC2 —терминальные матрицы пропускных способностей для С1 и С2, а T(t1) и ее транспонирован­ная матрица T'(t1) дают элемент (везде равный t1), по­казывающий связь между парами вершин по одной из каждой компоненты (величина t1 соответствует пропуск­ной способности разреза).

Опишем следующий процесс, как необходимое и достаточное условие реализу­емости матриц. Перегруппируем рассматриваемую мат­рицу, как это сделано с матрицей Т, где tij≥t1, ТC1 и ТC2 —терминальные матрицы пропускных способностей.

Таким образом, можно построить два графа, разрезы которых имеют пропускные способности, указанные в этих матрицах, и объединить их разрезом с минималь­ной пропускной способностью. Путем соответствующих перестановок строк и столбцов каждая из матриц ТC1 и ТC2 может быть представлена в такой же форме, как и Т. Следовательно, каждая матрица может быть в дальнейшем разбита на четыре подматрицы (если пос­ледняя не представляет собой единственный элемент). Процесс перестроения матриц и их разбиения может быть продолжен до тех пор, пока диагональные подмат­рицы разбитой матрицы Т не окажутся одиночными эле­ментами и/или симметрическими матрицами 2×2.

Чен сформулировал следующее правило. На каждом этапе разбиения пропускная способность каждого ребра, которое связывает разделяемые подгра­фы, делится поровну между этими двумя подграфами. Пропускная способность новой дуги есть разность новой терминальной пропускной способности и половины ис­ходной пропускной способности дуг между разделяемым и всеми другими подграфами.

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

5.17. Граф потока сигналов

Введем общее понятие потока сигналов в ориенти­рованных графах или сетях, которые имеют источники [δ-(v)=0], стоки [δ+(v)=0] и, возможно, контуры и петли. Наличие контуров и петель соответствует поня­тиям обратных связей в сетях. Кроме понятий коэффи­циентов усилия, соответствующих каждой дуге, исполь­зуем понятие сигнала xj, передаваемого из вершины vj. Величина xj называется весом vj. Задача анализа сетей состоит в том, чтобы найти выражения для полного потока сигналов от источника к стоку (который часто называется коэффициентом усиления в стоке) через зна­чения сигналов и коэффициенты усиления дуг. Связь между сигналами в различных вершинах может быть представлена в общей функциональной форме или в специальной форме линейных отношений. В последнем случае можно ввести соответствующие операции на сети и установить соответствие между этими операциями, например, и решением системы совместных линейных уравнений.

Сама сеть может представлять некую реальную фи­зическую систему. От такой системы, вообще говоря, можно непосредственно перейти к ее уравнениям. Однако часто удобно переходить к сетевому представлению и с учетом его соответствия линейным системам попытаться найти составляющие отдельных элементов сети в общем потоке.

Введем в общем виде несколько полезных для нас понятий, относящихся к сети.

Дуги сети могут быть разделены на два класса: (1) дуги обратных связей, т. е. те, которые принадлежат контурам или образуют петли, и (2) каскадные дуги, т. е. дуги, не принадлежащие обратным связям. На рис. 5.39 дуги v2v3, v3v2, v4 v4 являются дугами об­ратных связей, a v1v2, v2v4, v4v5 — каскадные дуги.

Рис. 5.39.

Вер­шины могут быть также классифицированы в зависи­мости от того, принадлежат они контурам или нет.

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

Рис. 5.40.

Любая вершина блока обратной связи может быть разделена на две вершины, одна из которых инцидентна только исходящим дугам исходной вершины, а другая — входящим дугам. При этом все дуги обратных связей, инцидентные исходной вершине, становятся каскадными дугами новой сети. На рис. 5.41 слева приведен блок об­ратной связи, а справа показан его вид после разделения вершины v2.

Рис. 5.41.

Индекс блока обратной связи равен мини­мальному числу вершин, разделение которых переводит все дуги в каскадные (т. е. разрывает все контуры обратных связей). Операция разделения вершин сущест­венно упрощает сеть и позволяет вычислить общий поток без учета влияния контуров. После нахождения вершин, участвующих в вычислении индекса блока (может быть несколько групп таких вершин с одинаковым числомвершин в каждой), образуется остаточная сеть, включающая в себя выделенные вершины, источники и стоки. Все другие вершины удаляются. Дуги между двумя вер­шинами и петли в остаточной сети соответствуют (1) ду­гам, инцидентным этим вершинам в исходной сети, (2) путям, связывающим эти вершины в исходной сети и проходящим только через отброшенные вершины, и (3) петлям, которые могут быть либо петлями в исходной сети, либо контурами, проходящими через удаленные вершины.

На рис. 5.42 слева изображена сеть, а справа оста­точная сеть.

Рис. 5.42.

Источник и сток помечены знаком ×. Здесь индекс определяется вершинами v3 и v4. Сеть можно упростить путем стягивания каждого полного блока об­ратной связи в одну вершину. При этом новая вершина, как это показано, связывается со всеми другими вер­шинами с помощью каскадных дуг. Если между верши­нами блока и другой вершиной или другим блоком проходило более одной дуги, то все они заменяются од­ной дугой.

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

Введем теперь алгебраические операции, связанные с предыдущими понятиями. В каскадной сети вес в лю­бой вершине является функцией весов всех вершин, соответствующих началь­ном вершинам дуг, которые заканчиваются в данной вершине. Пред­полагается, что эти веса как бы трансформируются при прохождении по дугам в соответствии с коэффициентами усиления последних. Например, запись хj=fj(xi, хk) будет озна­чать, что вершина vj является конечной вершиной двух дуг, начинающихся в vi и vk, xi и xk также функциональ­но связаны с другими вершинами и т. д. Подставляя выражения для хi и хk в fj, получаем связи xj с весами непосредственно предшествующих вершин и т. д. В ре­зультате, используя подстановку и последовательное исключение промежуточных вершин, получим связи xi с источниками. Такое упрощение невозможно в сети с об­ратной связью. Пусть, например, на рис. 5.43 x1 — вес v1, и пусть