Составители:
81
эквивалентного преобразования вершинного графа в реберный.
Основанием такого преобразования служит теорема об услови-
ях эквивалентности матриц смежности вершинного и реберного
графов
1
.
Методика, обеспечивающая выполнение условий эквивалентнос-
ти при преобразовании вершинного ориентированного графа без крат-
ных дуг в реберный граф, включает в себя три этапа.
1-й этап. Построение квазиканонической матрицы
смежности реберного графа
На данном этапе матрица смежности вершинного графа путем рас-
ширения и преобразования элементов матрицы с помощью построе-
ния двух вспомогательных матриц на каждой из последовательно про-
водимых итераций постепенно преобразуется в квазиканоническую
матрицу смежности реберного графа, эквивалентного исходному вер-
шинному.
Пусть
[]
n
ij
n
n
r
=
R
– матрица смежности вершин ориентированного
вершинного графа без кратных дуг.
Введем обозначение
[]
[]
()
0
.
n
n
=
R
R
1-я итерация.
1-й шаг. По матрице
[]
()
0
n
R
строят матрицу
[]
()
1
n
S
, элементы которой
определяются по формуле
() () () ()
() ()
10 0 0
11
,11,11.
nn
ij ij
kj ik
kk
sr r r i nj n
==
=+==
∑∑
(2.2.1)
2-й шаг. По матрице
[]
()
1
n
S
строят матрицу
[]
()
1
n
C
, элементы которой
вычисляются по формуле
1
Нечипоренко В. И. Структурный анализ систем (эффективность и надежность). М.: Сов.
радио, 1977. 216 с.
Страницы
- « первая
- ‹ предыдущая
- …
- 79
- 80
- 81
- 82
- 83
- …
- следующая ›
- последняя »
