Элементы теории графов и их технические приложения. Пронькин Ю.С - 26 стр.

UptoLike

ВУЗ: 

ТвГТУ | Тверь

Составители: 

Рубрика: 

26
с одним источником и одним стоком изменение направления дает новый граф,
передача которого от источника до стока равна передаче исходного графа.
Инвариантность передачи от источника до стока очевидна, так как изменение
направления приводит к новому графу, имеющему такие же топологические
характеристики, как исходный граф.
)(1
)(
)(1
)(
1
2
1
5
cfeb
cfega
cfeb
cdgab
x
x
x
x
+−
++
=
+−
+
=
)(1
)(1
)(
/
5
/
2
2
1
/
5
/
1
/
5
/
2
/
1
/
2
1
5
/
5
/
1
cfeb
dcb
gab
b
cfeb
gabdc
x
x
x
x
xx
xx
x
x
x
x
x
x
+−
=
≠
+
==
=
+−
+
=
Рис. 24 Изменение направления сигнального графа: а- исходный граф; б-
преобразованный граф.
На рис 24а показан первоначальный граф, а на рис 24б – граф с измененным
направлением. Откуда видно, что, хотя передача от источника до стока не
изменилась после изменения направления, соотношения между сигналами в
промежуточных узлах полностью меняются после изменения
направления.
Изменения направления сигнального графа эквивалентно транспонированию
матрицы его ветвей (
tt
jkkj
=
/
). Следовательно, матрица передачи сигнального
графа также транспонируется путем изменения направления графа. Т.е.
[
]
[
]
TT
jkkj
=
/
Расщеплении узла.
Операция расщепления (блокировки) узла применима к смешанным узлам и
заключается в разложении такого узла на два, один из которых является
источником, а другой – стоком. В новый сток собираются все входящие в
первоначальный узел ветви, из нового источника исходят все исходящие ветви.
Поскольку переменная в каждом узле определяется
только входящими ветвями и
передачи ветвей не зависят от переменных, операция расщепления узла всегда
допустима. Расщепление узла с петлей соответствует общему правилу.

Страницы