Элементы теории графов и их технические приложения: Учебно-методическое пособие. Часть 2

Федеральное агентство по образованию РФ Тверской государственный технический университет Кафедра высшей математики

Пронькин Ю.С., Егоров Ю.А.

Элементы теории графов и их технические приложения. Учетно-методическое пособие для студентов технических специальностей. Часть 2

Тверь 2008

2

УДК….519.17 ББК….22.17 В пособии рассматриваются основные понятия теории графов и их приложения к описанию и решению различных технических задач. Предназначенного для студентов технических специальностей, в программу которых входит изучение раздела «графы».

Элементы теории графов и их технические приложения Учебно-методическое пособие для студентов технических специальностей Часть 2 Составители: Пронькин Ю.С., Егоров Ю.А. Технический редактор Комарова Г.В. Подписано в печать 9.04.08 Физ.печ.л. 2,0 Усл.печ.л. 1,86 Уч.-изд.л. 1,74 РИЦ ТГТУ 170026, г. Тверь, наб. А. Никитина, 22

© Тверской государственный технический университет,2008 © Пронькин Ю.С., Егоров Ю.А., 2008

3

Успешное решение многочисленных задач в различных областях техники и гуманитарных наук предполагает наличие математической модели, отражающей связи между различными сторонами исследуемого явления. Такая модель является абстрактным и формальным представлением явления, как некоторой системы, изучение которой возможно математическими методами. Математические модели подразделяют на символические и иконографические. Символические математические модели представляют собой совокупность математических соотношений в виде формул, уравнений, операторов, логических условий или неравенств, которые определяют характеристики состояния системы в зависимости от конструкционных и технологических параметров в случае технической системы. Иконографические математические модели – это графическое отображение таких качественных свойств технических систем, по которым можно определить количественные характеристики системы или графическое отображение функциональных соотношений между параметрами и переменными системы. Применение таких моделей облегчает решение трудоёмких задач исследования и оптимизации сложных технических систем, позволяет непосредственно выявлять взаимосвязь между изменениями качественных характеристик, переменных и параметров системы и показателями эффективности функционирования системы. Такие модели подразделяют на две большие группы: топологические и сетевые модели. Основой которых являются потоковые и структурные графы, информационно-потоковые мультиграфы, информационные и сигнальные графы. Потоковые и структурные графы отображают особенности технологической топологии системы и дают возможность устанавливать непосредственную связь между изменениями технологической структуры и количественными характеристиками технических систем. Информационно – потоковые мультиграфы и информационные графы отображают характеристические особенности символических математических моделей и позволяют разрабатывать оптимальную стратегию решения задач исследования технических систем. Сигнальные графы графически изображают функциональные связи между переменными математических моделей технических систем. Их можно применять для определения динамических и статических характеристик технических систем, расчёта функций чувствительности характеристик систем к изменениям их параметров, а также для оценки устойчивости процессов функционирования технических систем. Сигнальные графы При решении задач анализа и синтеза технических систем необходимо выявить взаимные причинно-следственные связи между переменными, характеризующими процесс функционирования системы. Процесс функционирования технических систем, с этой точки зрения, можно рассматривать как процесс, при котором некоторое событие, называемое причиной, воздействуя на

4

ситуацию, вызывает следствие. В последовательности событий, соединённых причинно-следственными связями, следствие одного события становится причиной другого события и можно считать, что вдоль цепи событий распространяется причинное воздействие. Переменные технической системы, независимо от их природы и размерности можно обозначить термином “сигнал” и предположить, что сигналы распространяются вдоль технической системы. Иконографический моделью детально характеризующей самые разнообразные проблемы технической системы, с выявлением её тонкой внутренней структуры или структуры одного из её элементов и сохраняющей наглядное представление о прохождении сигналов через систему являются сигнальные графы. Они упрощают определение функциональных связей между переменными, входящими в математическую модель системы, представленную в форме матрицы преобразования. При этом объём математических операций с помощью формальных правил эквивалентного преобразования, получается близким к минимальному, что существенно в случае, когда задачи не настолько сложны, чтобы было целесообразно решать их с помощью вычислительных машин и в тоже время достаточно громоздки, если решать их методами линейной алгебры. Сигнальные графы дают возможность различные по природе процессы свести к одной и той же структуре прохождения и преобразования сигналов, что позволяет сделать важные обобщения о функционировании данной системы. Сигнальный граф – это ориентированный граф, соответствующий линейным или линеаризированным системам уравнений математической модели технической системы и отражающий причинно-следственные связи между переменными (сигналами) системы. Вершины сигнального графа соответствуют сигналам, а ветви – коэффициентам или передаточным функциям, характеризующим связь между этими сигналами. Таким образом, каждая ветвь сигнального графа отображает причинноследственную связь между сигналами (переменными), образующими начало и конец ветви, причём начало ветви истолковывается как причина , а её конец как следствие. Направление ветви указывает от причины к следствию. Вершины-источники сигнального графа отображают независимые (свободные) переменные, вершины-стоки – зависимые переменные технических систем. Вершины, соответствующие входящим и исходящим ветвям, называют смешанными. Их относят к зависимым переменным и называют зависимыми вершинами. Построение сигнальных графов выполняют на основании следующих правил: 1. Сигналы передаются вдоль ветвей только в направлении их ориентации. 2. Сигнал, проходящий вдоль какой-либо ветви, умножается на передачу этой ветви. 3. Сигнал, изображаемый какой – либо вершиной, является суммой всех сигналов, только приходящих в эту вершину (узел). 4. Значение сигнала, изображаемого какой-либо вершиной, передаётся по всем ветвям, выходящим из неё. Согласно этих правил значение сигнала в любой зависимой вершине сигнального графа определяется формулой.

5 N

X K = ∑a kj x j , где X k – значение сигнала в k - ой вершине сигнального графа; j=1

j=1, N – число вершин графа, связанных выходящими ветвями с k -м узлoм; akj - коэффициент передачи ветви, входящих в k - ю вершину.

Рис 1 Сигнальный граф (а) и разделение его смешанной вершины (б) Значение сигнала X k не зависит от выходящих из k – ой вершины ветвей графа. Смешанная вершина, выполняющая функции источника и стока, может быть разделена на две части (рис 1, б); вершину-сток ( X sk ) , объединяющую все входящие в данную вершину X k ветви, и вершину-источник ( X kJ ), инцидентную всем выходящим из данной - вершины X k ветвям. Эти две вершины соединяются ветвью, с коэффициентом передачи равным единице. Ветви сигнального графа выполняют функции операторов и в этом смысле могут быть линейными и нелинейными. В общем случае ветвь может выполнять сложные линейные операции, описываемые рациональными функциями комплексной переменной. Сигнальный граф изображает системы уравнений технической системы в графической форме, однако между сигнальным графом и системой уравнений не существует взаимно однозначного соответствия.

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

X J = ∑ a ji x i , где j = 1,…,N и a ji - коэффициент передачи ветви, i =1

выходящей из i-ой вершины и входящей в j – ю вершину графа. Коэффициенты передач ветвей сигнального графа всегда можно записать в виде квадратной матрицы передач. ⎛ a11a12 ...a1n ⎞ ⎜ ⎟ A = ⎜ a 21a 22 ...a 2n ⎟ ⎜ a a ...a ⎟ ⎝ n1 n 2 nn ⎠

6

Порядок матрицы А равен числу вершин сигнального графа n. В строки матрицы А записываются передачи к данной вершине от всех других смежных вершин графа, а в столбцы – передачи от данной вершины ко всем другим вершинам. Номера рядов матрицы А совпадают с номерами вершин, относительно которых определяются передачи входящих и выходящих ветвей. Если все элементы строки-нули, соответствующая вершина представляет собой источник; если все элементы столбца являются нулями, соответствующая вершина представляет собой сток сигнального графа. Для построения сигнального графа по системе уравнений технической системы, необходимо определить множество его вершин и составить матрицу передач ветвей графа А (в простейших случаях её в явном виде можно не выписывать). Следует отметить, что одной и той же системе уравнений могут отвечать разные сигнальные графы, называемые равносильными. Пусть задана система линейных уравнений технической системы ⎧b11 x1 + b12 x 2 + ... + b1j x j + ... + b1n x n = f1 ⎪ ⎪b 21 x1 + b 22 x 2 + ... + b 2 j x j + ... + b 2n x n = f 2 ⎨ ⎪b 31x1 + b 32 x 2 + ... + b 3 j x j + ... + b 3n x n = f 3 ⎪b x + b x + ... + b x + ... + b x = f n2 2 nj j nn n n ⎩ n1 1 по которой нужно построить сигнальный граф. На поле предполагаемого графа наносятся N точек, причём N=n+m, где nчисло уравнений (число неизвестных переменных) системы, а m – число правых частей (f j ) , не равных нулю (очевидно, что N ≤ 2n ). Затем нанесенные точки нумеруются. Каждой точке сопоставляется одна переменная x или f. В результате образуется совокупность узлов графа. Узлы, которым отвечают переменные x, являются зависимыми, независимым узлам соответствуют правые части f. В однородных системах (f j = 0) , для всех j все узлы зависимы. Располагать вершины сигнального графа на поле чертежа и сопоставлять им переменные можно произвольно. Обычно, когда необходимо составлять матрицу А, первым по порядку точкам условимся сопоставлять зависимые узлы, а оставшимся m точкам – независимые. В противном случае следует исходить из удобства изображения и наглядности графа. Передачи ветвей сигнального графа по заданной системе уравнений можно определить двумя основными способами, каждый из которых приводит к своему графу, которые являются равносильными. Первый способ приводит к графу, который называется нормализированным, второй – ненормализированным.

Построение нормализированного сигнального графа. Для построения этого графа система уравнения (3) переписывается так, чтобы в каждом уравнении коэффициент при одной переменной x был равен единице

7

(нормализированная переменная). Далее необходимо все уравнения разрешить относительно нормализированных переменных. Разрешим первое уравнение системы относительно x1 : b1j b b 1 x1 = 0 − 12 x 2 − ... − x j − ... − 1n x n + f1 b11 b11 b11 b11

(4)

Слагаемые в этом выражении являются составляющими x1 , а коэффициенты при x и f – передачами ветвей. Разрешая второе уравнение системы относительно x 2 , третье – относительно x 3 и т.д., получим соответствующие строки матрицы A H . Указанный порядок разрешения уравнений не обязателен. Номер строки матрицы A H определяется номером узла, соответствующего переменной X j , относительно которой разрешается уравнение. При этом графы будут различны, но равносильны. Матрица AH записывается следующим образом ⎛ 0a12 a13 ...a1j ...a1n a1(n +1) 00....0 ⎞ ⎜ ⎟ ⎜ a 21 0a 23 ...a 2 j ...a 2n 0a 2(n +1) 0....0 ⎟ ⎟ AH = ⎜ ⎜ a 31a 32 0...a 3 j ...a 3n 00a 3)n +1) ....0 ⎟ ⎜⎜ ⎟⎟ ⎝ a n1a n 2 a n3 ...a nj ...000...a nN ⎠

где a12 = −

b b12 b ; a13 = − 13 ; … , a1n = − 1n ; b11 b11 b11

a 1( n + 1) =

1 b 11

; a 2 ( n + 1) =

или в общем случае a ji = − b ji ( i ≠ j )

b

1

b 22 (i =1,2,3...,n);j =1,2,3...,n); aij = 0,

jj

a j( n + k ) = 0 (k ≠ j)

(k=1, 2, 3,…, m); a j ( n + k ) = 1 (k=j)

b

jj

В соответствии с полученной матрицей АН необходимо соединить узлы графа между собой. Матрица АН нормализованного графа называется нормализованной. Она характеризуется равенством нулю всех элементов главной диагонали, что соответствует отсутствию петель в нормализованном графе. Для однородной системы уравнений матрицу можно составить непосредственно по матрице коэффициентов при помощи равенства (5) A H = D × В + E n (5), в котором В - квадратная матрица коэффициентов системы уравнений, D – диагональная матрица, составленная из соответствую щих и противоположных по знаку обратных элементов диагонали матрицы B и En- единичная матрица порядка n . Например, если

⎛a B = ⎜⎜ ⎝c

b⎞ ⎟, d ⎟⎠

то

⎛ 1 ⎜− D=⎜ a ⎜ 0 ⎜ ⎝

⎞ 0 ⎟ ⎟ 1⎟ − ⎟ d⎠

8

При неоднородной системе уравнений формула (5) оказывается громоздкой и неудобной для пользования. Пример 1. Для системы уравнений

1 b ⎧ − = 1 ⎪ 2 a a 3 ⎨ d 1 ⎪− + = 1+ 2 ⎩ e e 3

x

x

x x x x x

0

1 e

В которой x0 и x1 - свободные переменные, построить нормализованные сигнальные графы.

Решение. Для построения графов преобразуем исходную систему уровней ⎧ x 2 = ax1 + bx 3 (11) (*) следующим образом: ⎨ ( 21) ⎩x 3 = ex1 + x 0 + dx 2 1 a ⎧ x 3 = x1 + x 2 ⎪ b b и ⎨ (**) 1 e 1 ⎪x 2 = − x 0 − x1 + x 3 d d d ⎩ Система уравнений (*) получена для случая, когда x 2 является выходной переменной уравнения ( 11 ), а x3 - выходной переменной уравнения ( 21 ) Разрешив уравнение ( 11 ) относительно x3 , а уравнение ( 21 ) – относительно x 2 получим систему уравнений (**)

Рис. 2 Сигнальные графы, соответствующие различным уровням и системам уравнений. Сигнальный граф, изображенный на рис.2а соответствует уравнению (*1), а сигнальный граф Рис. 2б – уровню (*2). Сигнальные графы систем уравнений (*) и (**) представлены на рисунках (2в) и (2г). Пример 2. По заданной системе уравнений x1 − a = 0 ⎧ ⎪bx − x + fx + ex = 0 ⎪ 1 2 3 4 ⎨ ⎪ gx1 + dx 3 − x 4 = 0 ⎪⎩ cx 2 − x 3 = 0

9

не составлял матрицу AH в явном виде, построить нормализованный сигнальный граф, в котором определить источники, стоки и смешанные вершины. По сигнальному графу составить матрицу AH . Решение. Определим число узлов сигнального графа: N=n+m=4+1=5. Нанесем узлы на поле графа (рис 3а) и пронумеруем их. Далее последовательно выразим переменные из уравнений системы, выборов один из возможных вариантов. x1 = a ⎧ ⎪x = bx + fx + ex ⎪ 2 1 3 4 ⎨ ⎪ x 4 = gx1 + dx 3 ⎪⎩ x 3 = cx 2

(***)

Рис. 3 Вершины сигнального графа (а); сигнальные графы, соответствующие первому (б), второму (в), третьему (г) и четвертому (д) уравнениям; сигнальный граф системы уравнений в целом (е). Подграфы, отвечающие нормализованным уравнениям системы (***) показаны на рис.3 (б - д). Объединяя их, получим граф, соответствующий заданной системе уравнений (***) рис 3е. Из рисунка следует, что узел а является источником, а остальные узлы - смешанными; сток отсутствует. Матрица A H записывается следующем образом ⎛0 ⎜ ⎜b AH = ⎜0 ⎜ ⎜g ⎜0 ⎝

0

0

0

0

f

e

c 0

0 d

0 0

0

0

0

1⎞ ⎟ 0⎟ 0⎟ ⎟ 0⎟ 0 ⎟⎠

Построение ненормализованного сигнального графа

10

Возвращаясь к системе уравнений (3) преобразуем её следующим образом. Прибавим к обеим частям i-го уравнения переменную Xi и разрешим это уравнение относительно этой переменной:

X i = (b ii + 1)x i + b i1x1 + b i 2 x 2 + ... + b in x n − f

Коэффициенты при переменной x i и fi соответствуют элементам матрицы A , по которой может быть построен сигнальный граф. В отличие от нормализованной записи уравнений, в нашем случае каждая переменная x i выражается через все переменные, что приводит к образованию петель с передачами ( bii +1) и передачи ветвей в ненормализованной форме проще, чем в нормализованной. Рассмотрим общий принцип построения ненормализованного сигнального графа. Для чего представим систему уравнений (3) в матричной форме: B × X = F , условившись в верхних строках записывать уравнения, у которых правые части отличны от нуля. Таким образом, B - квадратная матрица порядка n коэффициентов b; X - матрица-столбец переменных x, имеющая n элементов; F - матрица-столбец правых частей f , содержащая m первых элементов, отличных от нуля. Прибавим к обеим частям равенства B × X = F матрицу X .

B×X + X = F + X

Выполнив элементарное преобразование, найдем

X = (B + E n )× X − F

(6)

Для нахождения матрицы A перепишем уравнение (6) в виде ⎛ − Em X = (B + E n ) × ⎜⎜ ⎝ 0 (n − m )m

(

⎞⎛ X ⎞ ⎟⎜⎜ * ⎟⎟ ⎟ F ⎠⎝ ⎠

)

(7)

В последнем выражении матрицы, входящие в выражение (6), играют роль элементов (подматриц) матрицы (7), а матрица F* имеет лишь элементы матрицы F отличные от нуля. Уравнение (7) представляет собой записанную в матричной форме систему уравнений, разрешенных относительно каждый переменной X , причем каждая такая переменная выражена через все переменные x и все правые части. Следовательно, первая матрица правой части является матрицей A , порядок которой равен N . Итак, по заданной системе линейных уравнений можно сразу записать матрицу A в следующем виде: ⎛ − Em ⎞ ⎟ A = (B + E n ) × ⎜⎜ (8) ⎟ 0 ⎝ (n − m )m ⎠ Эта матрица имеет N = m + n столбцов и n строк. Для того чтобы сделать данную матрицу квадратной, нужно добавить m нулевых строк, соответствующих числу узлов-источников. То же равенство (8) используется для составления графа однородной системы, только в этом случае m = 0 , формула упрощается и принимает вид (A ) = (B + En ) (9) т.е. к диагональным элементам матрицы В нужно добавить единицы.

(

)

11

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

⎧a1 x1 + a 2 x 2 + a 3 x 3 = f1 ⎪ ⎨ b 2 x 2 + b3x3 = 0 ⎪ c x +c x =f 1 1 2 2 3 ⎩ построить ненормализованный сигнальный граф. Проверить решение путем составления системы уравнений по построенному сигнальному графу. Решение. Перепишем систему уравнений следующим образом

⎧a1 x1 + a 2 x 2 + a 3 x 3 = f1 ⎪ ⎨ c1 x 1 + c 2 x 2 = f 3 ⎪ b x +b x =0 2 2 3 3 ⎩ Учитывая, что n = 3 и m = 2 , запишем матрицу A по формуле (8) a3 −1 0 ⎞ ⎛ a1 + 1 a 2 ⎟ ⎜ A = ⎜ c1 c1 + 1 0 0 − 1⎟ ⎜ 0 b2 b 3 + 1 0 0 ⎟⎠ ⎝

Сигнальный граф изображен на рисунке 4

Рис. 4 Графу отвечает следующая система уравнений:

12

⎧x1 = −f1 + (a1 + 1)x + a 2 x 2 + a 3 x 3 ⎪ ⎨ x 2 = −f 3 + c1x1 + (c 2 + 1)x 2 ⎪ x 3 = b 2 x 2 + (b 3 + 1)x 3 ⎩ Пример 4. Построить нормализованный и ненормализованный сигнальные графы по следующей системе уравнений ⎧ c1x1 + c 2 x 2 + c 3 x 3 = 0 ⎪ ⎨b1x1 + b 2 x 2 + b 3 x 3 = 0 ⎪a x + a x + a x = 0 2 2 3 3 ⎩ 1 1

Составить матрицу A . Доказать, что построенные сигнальные графы равносильны. Решение. Для составления нормализованного графа выразим переменные из уравнений системы: a a ⎛ a ⎞ a x1 = − 2 x 2 − 3 x 3 ⎜ 0 − 2 − 3⎟ a1 a1 a1 a1 ⎟ ⎜ b3 b1 ⎜ b1 b ⎟ x 2 = − x1 − x 3 Составим матрицу A H : A H = ⎜ − 0 − 3⎟ b2 b2 b2 ⎟ ⎜ b2 c1 c2 ⎜ − c1 − c 2 x 3 = − x1 − x 2 0 ⎟⎟ ⎜ c3 c3 c3 ⎝ c3 ⎠ Нормализованный сигнальный граф изображен на рисунке 5

Рис. 5 нормализованный сигнальный граф Матрица ненормализованного сигнального графа имеет вид a2 a2 ⎞ ⎛ a1 + 1 ⎜ ⎟ A = B + E = ⎜ b1 b 2 + 1 b3 ⎟ ⎜ c c2 c 3 + 1⎟⎠ ⎝ 1

граф, ей соответствующий изображен на рисунке 6

13

Рис. 6 Ненормализованный сигнальный граф Составим системы уравнений по графам: Для рисунка 6 Для рисунка 5 ⎧ a a2 x 2 − 3 x3 ⎪ x1 = − a1 a1 ⎪ b3 b1 ⎪ x1 − x3 ⎨x 2 = − b b 3 2 ⎪ c1 c2 ⎪ = − − x x x2 3 1 ⎪ c c 3 3 ⎩

⎧ x1 = (a1 + 1)x1 + a 2 x 2 + a 3 x 3 ⎪ ⎨x 2 = b1x1 + (b 2 + 1)x 2 + b 3 x 3 ⎪ x = c x + b x + (c + 1)x 2 2 3 3 ⎩ 3 1 1

Очевидно, что эти системы равносильны, а следовательно, равносильны и графы. Пример 5. Построить сигнальные графы для определения кинетических характеристик некоторых химических реакций. 1. Рассмотрим реакцию разложения гексафенилэтана, протекающую в хлороформе с образованием трифенилметила. Она имеет первый порядок; k ⎯→ 2B . константа скорости K = K 0 мин −1 при 0 0 С. Схема реакции: А ⎯ Уравнения кинетики реакции: dC A 1 dC B = kC A = −kCA ; 2 dt dt где C A и C B - концентрации веществ A и B . Начальные условия: C A (0) = C*A , C B (0) = 0 Применяя преобразование Лапласа к уравнениям кинетики, получим: C A = −S −1kC A , C B = 2S −1kCA Строим по этим уравнениям сигнальный граф (Рис. 7)

Рис. 7 2. Процесс алкилирования бензола пропиленом в присутствии фтористого водорода состоит из четырех последовательных реакций псевдопервого порядка. Обозначим компоненты: A - бензол; B - изопропилбензол; C - диизопропил-

14

бензол; D - триизопропилбензол; E - тетраизопропилбензол. Схема реакции: k

k

k

k 4 A ⎯ ⎯1 → B ⎯ ⎯2 → C ⎯ ⎯3 → D ⎯ ⎯ ⎯ → E * при этом концентрация C A (0 ) = C A мол .% Система кинетических уравнений имеет вид:

dC A ⎧ = − kC A ⎪ dt ⎪ dC a = k C −k C ⎪ 1 A 2 B ⎪ dt ⎪ dC C = k 2 C B − k 3C C ⎨ ⎪ dt ⎪ dC D = k C − k C 3 C 4 D ⎪ dt ⎪ dC E = k 4C D ⎪ dt ⎩

⎛d ⎞ Используем преобразование Лапласа к этой системе ⎜ → S ⎟ ⎝ dt ⎠

⎧ ⎪ ⎪⎪CB ⎨C C ⎪C ⎪ D ⎪⎩

C A = −S −1k 1C A = S −1k 1C A − S − `1k 2CB = S −1k 2CB − S −1`k 3CC = S −1k 3CC − S − `1k 4C D CE = S −1k 4C D

Сигнальный граф этой системы уравнений представлен на Рис. 8.

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

15

от друга топологией и передачами ветвей. Приведение графа одной топологии к равносильному графу другой топологии называют преобразованием графа. Преобразование графа может иметь целью не только упрощение его решения, но и достижения большей наглядности, выявления существенности каких-либо отдельных ветвей. Если результатом преобразования является граф, не допускающий исключений узлов, контуров и петель, он называется конечным. Для получения такого графа нужно располагать системой правил, позволяющих исключать узлы и петли исходного графа. Эквивалентное преобразование сигнального графа состоит в устранении некоторых его вершин с целью получения конечного графа, который обнаруживает функциональные связи только между переменными, представляющими интерес для исследователя. Этот метод преобразования графа отвечает методу последовательного преобразования системы уравнений путем исключения из уравнений некоторых неизвестных. Переменную можно исключить, устранив из сигнального графа вершину (узел). Продолжая упрощения, можно прийти к решению графа относительно одной переменной. Для эквивалентного преобразования сигнальных графов используют следующие основные правила: Передача последовательного соединения ветвей равна произведению 1. передач этих ветвей. Доказательство: x 2 = ax1 и x 3 = bx 2 ; подставив в последнее уравнение вместо x 2 его значение из предыдущего, получим x 3 = abx1 (Рис. 9)

Рис. 9 Определение передачи последовательного соединения ветвей сигнального графа, а – сходный граф; б – преобразованный граф. n

В общем случаи можно записать x n = ∏ a i x 0 , где x 0 - сигнал источника; x n i −1

сигнал стока; a i - коэффициент передачи i-ой ветви.

Рис. 10 Определение передачи параллельных одинаково направленных ветвей сигнального графа, а-исходный граф; б–преобразованный граф.

16

2. Передача параллельных одинаково направленных ветвей равна сумме передач этих ветвей (рисунок 10). Действительно, x 2 = ax 1 + bx 1 = (a + b )x 1 . В n

общем виде: xn = ∑ a i x 0 . i =1

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

Рис. 11 Устранение простого узла в сигнальном графе: а - исходный граф; б – преобразованный граф. Для графа рис. 11 запишем следующие уравнения: x 4 = ax1 ; x 2 = bx 4 ; x 3 = cx 4 из которых получаем x 2 = abx1 и

x 3 = acx1

Рис 12 Устранение простого узла в сигнальном графе: а – исходный граф; б – преобразованный граф. Для графа на рис. 12 имеем:

x 5 = ax1 + cx 4 x 2 = bx 5 = abx1 + bcx 4 x 3 = dx 5 = adx1 + dcx 4 При устранении простого узла из сигнального графа данный узел в графе не рисуется, а все пути, проходящие через этот простой узел, должны быть сохранены. 4. Исключение петли и контура сигнального графа.

17

Направление ветвей в петле не имеет значения, поэтому стрелки на ветви петли можно не рисовать. Граф на рисунке 13 имеет петлю с передачей T . Эту петлю можно устранить, следующим образом. Для рисунка 13а имеем x 2 = ax1 + Tx 2 ; x 3 = bx 2 .

Рис. 13 Исключение петли сигнального графа: а – исходный граф; б – преобразованный граф. a Из первого уравнения, находим: x 2 = x1 1− T Таким образом, исключение петли не изменяет числа вершин в графе, а передачи ветвей, входящих в вершину, при которой существовала петля, уменьшаются в (1 − T) раз. Для устранения контура в графе необходимо устранить любую одну вершину из этого контура.

Рис. 14 Исключение контура сигнального графа: а – исходный граф; б – преобразованный граф. Для графа на рис 14а имеем: x2 = ax1 + cx3 ; x 3 = bx 2 ; x 4 = dx 3 . Исключаем из этих уравнений x 2 , получим: x3 = abx1 + bcx3 ; x 4 = dx 3 (произошло слияние вершины x 2 с вершиной x 3 ). Устраняя петлю, получим: x3 =

ab x1 ; x 4 = dx 3 (рисунок 14 б и в) 1 − bc

5. Объединение нескольких петель в одну петлю

18

Петли при узле x 2 (Рис. 15) с передачами T 1 , T 2 и T3 можно заменить одной петлей с передачей:

T =

n

∑ T i , так как

i =1

x 2 = ax1 + T1x 2 + T2 x 2 + T3 x 2 = ax1 + (T1 + T2 + T3 )x 2 = ax1 + Tx 2 .

Рис. 15 Объединение нескольких петель сигнального графа в одну. Перенос конца ветви из одного узла в другой ( неполное исключение узла). На рис 16а сигнальный граф имеет два источника х1 и х4. Ветвь с передачей e может быть передана так, чтобы сигнал из х4 попадал в х3, а не в х2. Преобразование распадается на три этапа, показанные на рис 16 б – г. Первый этап заключается в расщеплении узла х2 на два узла x'2 и x''2. При этом в новой узловой точке x'2 оканчиваются ветви с передачами b и a. Т.к x''2=1· x'2+e x4,то переменная x'2 определяется уравнением 1· x'2= x''2 - e x4, переменная x''2 при этом остается той же, что и x2. 6.

Рис. 16 Неполное исключение узла сигнального графа: а – исходный граф; б – г – этапы преобразования графа. На втором этапе начала ветви x''2 x5 перемещается в узловую точку x'2. При этом из приведенного уравнения для x'2 следует, что x'2 не содержит всех сведений, имеющихся в x2. Для того, чтобы сохранить прежние значения (рис 16в) необходимо добавить ветвь, идущую от x4 непосредственно в x5. Точка x5 является некоторой узловой точкой, принимающей ветвь из x2. Следовательно,

19

изображенная на рис 16в образует в точке x''4 собственную петлю. На последнем этапе ликвидируем узловую точку x''2 см рис 16г. Таким образом, если в первоначальном графе (рис 16а) иметься ветвь, выходящая из x2 и приходящая в x3, то перемещение конца ветви е является простой операцией, требующей лишь нового определения переменной, изображенной узловой точкой x2. 7 Перенос начала ветви из одного узла в другой. Пояснение преобразования дают графы изображенные на рис 17а,б.

Рис 17 Перенос начала ветви сигнального графа: а, б – этапы преобразования графа. Начало ветви x2 x4 может быть перенесено из угловой точки x2 в угловую точку x3. При этом кроме новой ветви x3 x4 с передачей hd появляется ветвь x1 x4 с передачей ad и петля в точке x4 с передачей ed. Равносильность графов на рис 17а, б следует из эквивалентности узловых сигналов в соответствующих узлах этих графов. Для графа на рис 17, а имеем: x2 = ax1 + hx3 + ex4 x3 = bx2 + fx6 x4 = dx2 = adx1 + hdx3 + edx4 Для графа на рис. 17 б находим x2 = ax1 + hx3 + ex4 x3 = bx2 + fx6 x4 = adx1 + hdx3 + edx4 8. Инверсия прямого пути или контура. Прямым путем называется элементарный путь, соединяющий источник и сток графа. Как уже указывалось ранее, информация, содержащаяся в графе, эквивалентна информации в некоторой системе уравнений. Пусть имеется уравнение х3=с(аx1 +bx2 ) Этому уравнению отвечает сигнальный граф изображенный на рис 18а, в которой x1 x2 являются источниками (причинами), а x3 - стоком (следствием). Можно изменить причину и следствие, разрешив уравнение относительно x1 или x2. Например, если считать x3 и x2 причиной, а x1 следствием, то

20

X1 =

1 b + ( − ) x2 x 3 ac a

Этому уравнению соответствует граф 18б, в котором осуществлена инверсия прямого пути по сравнению с исходным графам (рис 18а)

Рис 18. Исходный сигнальный граф (а) и граф, в котором осуществлена инверсия прямого пути (б). Для перехода от исходного сигнального графа к инвертированному графу необходимо: а) Изменит направление всех осей прямого пути или контура на противоположное; б) Изменит передачи всех ветвей, находящихся на пути (или принадлежащие контуру) от новой причины к новому следствию на обратные; в) Перенести конец ветви, соединяющей узлы, не являющиеся причиной и следствием или не принадлежащие прямому пути (контуру), в узел, в который переносится инвертируемая ветвь, оставив начало ее в старом узле. Передача 1 этой ветви умножается на величину − , где а – коэффициент передачи a инвертируемой ветви. Коэффициент передачи инвертированного пути (контура) является обратной величиной коэффициента передачи прямого исходного пути (контура). Инверсия любой ветви некоторого прямого пути (контура) вызывает инверсию всего рассматриваемого пути (контура).

21

Рис. 19. Примеры (а - г) инверсии прямого пути сигнального графа. Примеры инверсии прямого пути от источника к стоку приведены на рис. 19 а – г. В первом примере сложность исходного сигнального графа снижается, так как в инверсном графе полностью исключаются все контуры. Инверсия, таким образом, может приводить к снижению сложности графа, если он содержит несколько петель и не слишком много путей, параллельных инвертируемому пути. Если необходимо инвертировать путь, состоящий из нескольких ветвей, то удобнее начинать инверсию со стороны старого источника, переходя от ветви к ветви в направлении старого стока

x 2 = ax1 + cx 4 x 3 = bx 2 + dx 5

⎛1⎞ ⎛ c⎞ x1 = ⎜ ⎟ x 2 + ⎜ − ⎟ x 4 ⎝a⎠ ⎝ a⎠ ⎛1⎞ ⎛ d⎞ x 2 = ⎜ ⎟x 3 + ⎜ − ⎟x 5 ⎝b⎠ ⎝ b⎠

22

x 2 = x12 = ax1 + cx 4 x 3 = x13 = bx 2 + dx 5

x"3 = x 3 + (− d )x 5 ⎛1⎞ x 2 = ⎜ ⎟x"3 ⎝b⎠ x"2 = x 2 + (− c )x 4 ⎛1⎞ x1 = ⎜ ⎟x"2 ⎝a⎠ Рис. 20 Сравнение двух типов инверсии сигнального графа: а – исходный граф; б – инверсия пути с сохранением узлов, в, г – инверсия пути с сохранением ветвей. Инверсия может быть упрощена, если расщепить каждый из узлов ( i ), не принадлежащих источнику в инвертируемом пути (рис. 20) , на узел источника '

( i ) и узел стока ( i ), соединенные ветвью с единичной передачей, направленную ' от i к i . Чтобы инвертировать путь или контур, узлы которого расщеплены, нужно изменить направление ветвей в этом пути, инвертировать их передачи и изменить знаки передач других ветвей, концы которых касаются данного пути (или контура). Следует заметить, что значение сигналов, обозначенных штрихами у концов расщепленных узлов, изменяются при инверсии. До инверсии узловой сигнал x 'i = x i . После инверсии значение сигнала x 'i обозначается по-другому, например x "i , так как оно уже не равно значению x i . Инверсии, изображенные на рис. 20 б, сохраняют соотношения, которые существуют между узловыми сигналами, но типология графа изменяется. Инверсии на рис. 20г сохраняют общую топологию графа, но узловые сигналы, которые помечены штрихами, изменяются. Соотношения между узловыми сигналами, непомеченными штрихами, остаются неизменными. Инверсию, сохраняющую узлы, назовем инверсией первого типа, она сохраняет все узловые сигналы. Инверсию, сохраняющую ветви, назовем инверсией второго типа, она сохраняет расположение всех ветвей (но изменяет направления ряда ветвей). Для некоторых графов нет необходимости расщеплять узлы, чтобы произвести инверсию, сохраняющую ветви. Например, если каждый узел имеет не более одной входящее и не более одной выходящей ветви, то граф уже обладает топологией, пригодной для инверсии, сохраняющей ветви. В прикладных задачах приходиться иметь дело с узлами, в которых сходиться некоторое число ветвей, но выходит только одна ветвь и с узлами, где одна входящая ветвь разделяется на два или большее число выходящих путей.

23

На рис. 21 сравниваются два типа инверсии. На рис. 21а представлен первоначальный сигнальный граф, в котором путь abc нужно инвертировать. Инверсия, сохраняющая узлы этого пути, дает новый граф (рис. 21б), передача которого от источника до стока есть инверсия передачи (рис. 21а). Отношение узловых сигналов x1 и x 4 одинаково для инвертированного и исходного графов. Передача инвертируется в графе (рис. 21б) просто потому, что роли источника и стока взаимно заменены. Граф на рис. 21в показывает результат инверсии, сохраняющей ветви, выполненной с расщеплением второго и третьего узлов. На рис. 21г представлен исходный граф с расщепленными вторым, третьим и пятым узлами, что необходимо для инверсии контура bghd. Шестой узел имеет только одну входящую ветвь, поэтому не может быть растянут. На рис. 21д контур инвертируется, и передача от источника до стока вычислена для сравнения с предыдущими случаями.

x4 abc = x1 1 − (de + fg + bghd ) + defg

x1 x4

=

1 ⎡⎛ 1 gf ⎞⎛ 1 ed ⎞ ghd ⎤ ⎢⎜ − ⎟⎜ − ⎟ − ⎥ c ⎣⎝ b b ⎠⎝ a a ⎠ a ⎦

x1 1 ⎡⎛ 1 gf ⎞⎛ 1 ed ⎞ ghd ⎤ = ⎜ − ⎟⎜ − ⎟ − x 4 c ⎢⎣⎝ b b ⎠⎝ a a ⎠ a ⎥⎦

x4 abc = x1 1 − (de + fg + bghd ) + dcfg

24

− ac x4 dhg = x1 ⎞ 1⎛1 ⎞1⎛1 1 − ⎜ − e ⎟ ⎜⎜ − f ⎟⎟ b⎝d ⎠h⎝g ⎠ Рис 21. Сравнение двух типов инверсии сигнального графа: а – исходный граф; б – инверсия пути с сохранением узлов; в – инверсия пути с сохранением ветвей; г – граф с расщепленными ( блокированными) узлами; д – инверсия контура bghd графа. Два типа инверсии сигнального графа отвечают всем возможным системам алгебраических уравнений технических систем, написанных в форме «причина – следствие». Если задача исследования сформулирована в виде сигнального графа в соответствии с принципом «причина – следствие», любые другие формулировки этой задачи, выполненные на основе того же принципа (с тем же числом переменных), получаются непосредственно с помощью процесса топологической инверсии данного графа. Нормирование передач ветвей сигнального графа. Поскольку передача сигнального графа зависит только от передач путей или контуров, очевидно, что передачи ветвей могут быть нормирована любым способом, поскольку такое нормирование не изменяет значений передач путей или контуров. Нормирование позволяет характеризовать структуру передачи минималь ным числом независимых параметров. Чтобы выявить, какие ветви можно нормировать без изменения выражения общей передачи, нужно объединить все стоки и все источники в одну базовую вершину и пренебречь направлениями всех ветвей, изображенных на рис. 22а. Иначе говоря, нужно построить ненаправленный циклический граф (рис.22б), соответствующий исходному сигнальному графу. Теперь построим произвольное дерево данного ненаправленного циклического графа. Ветви дерева могут быть нормированы к единицы (или любому другому значению), после чего передачи остающихся ветвей всегда можно изменить так, чтобы восстановить первоначальные значения общих передач всех путей и контуров сигнального графа.

25

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

Рис 23 Способы нормирования передач ветвей сигнального графа. На рис 22а показан граф, а на рис 23а, б – два из многих возможных способов, которыми определенные передачи ветвей исходного графа можно нормировать к единице без изменения выражения общей передачи от источника до стока. Изменение направления сигнального графа. Ранее было показано, что инверсия пути от источника до стока дает новый граф, передача которого равна обратному значению передачи первоначального графа. Изменение направления сигнального графа представляет собой другое преобразование, которое можно применять, чтобы получить новый граф, имеющий такую же передачу, как и заданный граф. Указанная операция выполняется с помощью изменения направлений всех ветвей в графе. При этом каждая ветвь tjk заменяется новой ветвью t´jk и

t´jk = tjk. Для сигнального графа

26

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

x x x x

x x x x x x

5

2

=

/

=

1 / 2 / 5

=

a + g ( e + cf ) 1 − b ( e + cf )

1

5 2 /

( ab + g ) cd 1 − b ( e + cf )

1

/ 1 /

=

=

dc ( ab + g ) = 1 − b ( e + cf )

x x

/ 2 / 1

x x

/ 5 / 5

=

x x

5 1

b ≠ ab + g

x x

1 2

dcb 1 − b ( e + cf )

Рис. 24 Изменение направления сигнального графа: а- исходный граф; бпреобразованный граф. На рис 24а показан первоначальный граф, а на рис 24б – граф с измененным направлением. Откуда видно, что, хотя передача от источника до стока не изменилась после изменения направления, соотношения между сигналами в промежуточных узлах полностью меняются после изменения направления. Изменения направления сигнального графа эквивалентно транспонированию матрицы его ветвей ( t kj/ = t jk ). Следовательно, матрица передачи сигнального графа также транспонируется путем изменения направления графа. Т.е.

[T ] =[T ] /

kj

jk

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

27

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

Рис. 25 Сигнальный граф двух последовательно соединенных подсистем технического устройства. Если сложному графу возможно придать форму, которую можно разделить линией так что все отрезки, пересекаемые ею, направлены в одну сторону, то техническая система может рассматриваться как последовательная комбинация двух более простых подсистем: одна слева от упомянутой лини, другая – справа. Это свойство графа, изображенного на рис 25 называется декомпозицией сигнального графа. С точки зрения системы совместных уравнений сигнальный граф в форме, допускающей декомпозицию, эквивалентен уравнениям, для которых определитель системы можно считать произведением определителей более низкого порядка. Пример 1. Упростить сигнальный граф, изображенный на рис 26 а, используя операцию расщепления узла.

Рис. 26 Упрощение сигнального графа расщеплением узла:а - исходный граф; б – г этапы упрощения.

28

Решение. Устранению подвергаются одновременно два узла (узлы 3 и 4 на рис 26 а). Граф с расщепленными узлами показан на рис 26 б, который строиться с учетом передач путей от источников к стокам и последующего объединения расщепленных узлов. Тот же граф может получить непосредственно из исходного (рис 26а), учитывая, что через устраняемые узлы 3 и 4 проходят следующие элементарные пути: от узла 2 к узлу 2-efx2; от узла 2 к узлу 5-edhx2; от узла 5 к узлу 5-ghx5. Упрощения переведены на рис 26 а – г . Осуществить операцию инверсии ветви с в сигнальных графах, Пример 2. изображенных на рис. 27 а, б.

Рис. 27 Инверсия ветви с в сигнальных графах: а, б – исходные графы; преобразованные графы.

в, г –

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

Рис 28 Приведение сигнального графа (а) к конечному (б). Граф на рис 28а имеет два узла – источника с петлями, передачи которых равны c =2h и d=4h. Для того чтобы система уравнений имела ненулевые решения, необходимо выполнение следующих условий: 2h=1 и 4h=1. Эти условия несовместимы, и, следовательно, система уравнений представляемая графом, всегда имеет нулевые решения. Рассмотренный граф приводит к конечному в виде замкнутого контура (рис 28б). Условия равенства единице передачи неустранимой петли выражается

29

a b ⋅ = 1 . Только при выполнении этого условия система, 1− d 1− c соответствующая данному графу, имеет ненулевые решения. Граф, изображенный на рис 29а, можно упростить и привести к конечному.

соотношением

Рис 29. Приведение сигнального графа к конечному: а – исходный граф; б – д – приведения исходного графа к конечному. Переход от графа на рис 29а к графу на рис 29б сделан для исключения узла 2; от рис 29б к рис 29в для исключения петель в узлах 1 и 3; от рис 29в к рис 29г – для исключения узла 3; от рис 29г к рис 29д – для исключения петель в узлах 1 и 4. Конечный граф представляет собой замкнутый контур с передачей, не равной единице, т. е система, отвечающая графу имеет только нулевое решение. Пример 4. Упростить сигнальный граф, изображенный на рис 30а, для определения передачи между вершинами

30

Рис 30 Упрощение сигнального графа: а – исходный граф; б – ж – этапы преобразования исходного графа. Эквивалентное преобразование графа, изображенного на рис 30а проводим по этапам: 1. Добавляем вершину х6 и объединяем параллельные ветви b и с (рис 30б) 2. Исключаем простой узел х3 и объединяем группы ветвей х2 –х3 ,х3 –х5 в путь х2 - х5 (рис 30в) 3. Исключаем сложный узел х2. Пути х1 –х5, х1 –х4 и х4 –х5 должны быть преобразованы. Следует помнить, что путь из узла х4 в узел х5 проходит не только через ветвь g но и через ветви f и (b+c)d, инцидентные вершине х4 (рис 30г). 4. Исключаем узел х4, принадлежащей l2=fe (рис 30д) 5. Преобразуем параллельные ветви между вершинами х1 и х5 (рис 30е) 6. Исключаем узел х5, принадлежащий петле l (рис 30ж).