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

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

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

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

Дуги сети могут быть разделены на два класса: (1) дуги обратных связей, т. е. те, которые принадлежат

контурам или образуют петли, и (2) каскадные дуги, т. е. дуги, не принадлежащие обратным связям [62]. На рис. 6.39 дуги являются дугами обратных связей, каскадные дуги. Вершины могут быть также классифицированы в зависимости от того, принадлежат они контурам или пет.

Рис. 6.39.

Рис.

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

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

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

Рис. 6.41.

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

На рис. 6.42 слева изображена сеть, а справа остаточная сеть. Источник и сток помечены знаком Здесь индекс определяется вершинами

Рис. 6.42.

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

Наконец, введем понятие инверсии пути в сети, под которой будем понимать переориентирование всех дуг

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

Рис. 6.43.

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

Подстановка дает

т. е. сеть не может быть упрощена.

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

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

Рис. 6.44.

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

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

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

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

изображенной на рис. 6.45, записывается как

Аналогичные преобразования могут быть выполнены при наличии нескольких петель.

(см. скан)

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

Рис. 6.45.

Рис. 6.46.

Рассмотрим сеть рис. 6.47 с соответствующими ей уравнениями

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

иметь вес Две параллельные дуги образуют новую дугу с коэффициентом усиления 6. После замены петли с коэффициентом усиления 6 на дугу с коэффициентом усиления и объединения результатов для получения коэффициента в получим

Рис. 6.47.

Рис. 6.48.

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