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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

22
52
1
33
41
1
22
dxbxxx
cxaxxx
+==
+==
(
)
()
"
21
42
"
2
"
32
53
"
3
1
1
x
a
x
xcxx
x
b
x
xdxx
⎟
⎠
⎞
⎜
⎝
⎛
=
−+=
⎟
⎠
⎞
⎜
⎝
⎛
=
−+=
Рис. 20 Сравнение двух типов инверсии сигнального графа: а – исходный граф; б
– инверсия пути с сохранением узлов, в, г – инверсия пути с сохранением ветвей.
Инверсия может быть упрощена, если расщепить каждый из узлов (
i
), не
принадлежащих источнику в инвертируемом пути (рис. 20) , на узел источника
(
'
i
) и узел стока (
i
), соединенные ветвью с единичной передачей, направленную
от
'
i
к
i
.
Чтобы инвертировать путь или контур, узлы которого расщеплены, нужно
изменить направление ветвей в этом пути, инвертировать их передачи и
изменить знаки передач других ветвей, концы которых касаются данного пути
(или контура). Следует заметить, что значение сигналов, обозначенных
штрихами у концов расщепленных узлов, изменяются при инверсии. До
инверсии узловой сигнал
'
i
x =
i
x
. После инверсии значение сигнала
'
i
x
обозначается по-другому, например
"
i
x , так как оно уже не равно значению
i
x .
Инверсии, изображенные на рис. 20 б, сохраняют соотношения, которые
существуют между узловыми сигналами, но типология графа изменяется.
Инверсии на рис. 20г сохраняют общую топологию графа, но узловые сигналы,
которые помечены штрихами, изменяются. Соотношения между узловыми
сигналами, непомеченными штрихами, остаются неизменными.
Инверсию, сохраняющую узлы, назовем инверсией первого типа, она сохраняет
все узловые
сигналы. Инверсию, сохраняющую ветви, назовем инверсией
второго типа, она сохраняет расположение всех ветвей (но изменяет направления
ряда ветвей). Для некоторых графов нет необходимости расщеплять узлы, чтобы
произвести инверсию, сохраняющую ветви. Например, если каждый узел имеет
не более одной входящее и не более одной выходящей ветви, то граф уже
обладает топологией,
пригодной для инверсии, сохраняющей ветви.
В прикладных задачах приходиться иметь дело с узлами, в которых сходиться
некоторое число ветвей, но выходит только одна ветвь и с узлами, где одна
входящая ветвь разделяется на два или большее число выходящих путей.

Страницы