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

UptoLike

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

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