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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

17
Направление ветвей в петле не имеет значения, поэтому стрелки на ветви петли
можно не рисовать. Граф на рисунке 13 имеет петлю с передачей
T
. Эту петлю
можно устранить, следующим образом. Для рисунка 13а имеем
212
Txaxx +=
;
23
bxx
=
.
Рис. 13 Исключение петли сигнального графа: а – исходный граф; б –
преобразованный граф.
Из первого уравнения, находим:
12
1
x
T
a
x
−
=
Таким образом, исключение петли не изменяет числа вершин в графе, а передачи
ветвей, входящих в вершину, при которой существовала петля, уменьшаются в
()
T−1 раз.
Для устранения контура в графе необходимо устранить любую одну вершину из
этого контура.
Рис. 14 Исключение контура сигнального графа: а – исходный граф; б –
преобразованный граф.
Для графа на рис 14а имеем:
312
cxaxx
+
=
;
23
bxx
=
;
34
dxx =
.
Исключаем из этих уравнений
2
x , получим:
313
bcxabxx
+
=
;
34
dxx =
(произошло слияние вершины
2
x с вершиной
3
x ). Устраняя петлю, получим:
13
1
x
bc
ab
x
−
=
;
34
dxx =
(рисунок 14 б и в)
5.
Объединение нескольких петель в одну петлю

Страницы