Основы синтеза и диагностирования автоматов. Воронин В.В. - 58 стр.

UptoLike

ВУЗ: 

ТОГУ | Хабаровск

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

Рубрика: 

54
фа считается списковый. Он используется в двух вариантах (по чис-
лу способов определения гра-
фа). В первом варианте пере-
числяется множество пар, обра-
зующих дуги. Во втором вари-
анте задается множество вер-
шин и отображение Г: Х
→Х. Например, для графа на рис. 2.19 полу-
чим U={(2,1),(3,2),(4,3),(5,4),(6,5),(1,6),(2,3),(6,4)}; X={1,2,3,4,5,6};
Г(1)={2}; Г(2)={3}; Г(3)={2,4}; Г(4)={5,6}; Г(5)={6}; Г(6)={1}.
Прежде чем рассматривать другие способы задания, дадим три
определения. Две вершины х
i
и х
j
называют смежными, если они раз-
личны и существует дуга, идущая из х
i
в х
j
. Дуга u называется инци-
дентной вершине x, если она заходит в эту вершину или исходит из
нее. Дуги, имеющие общие вершины, называются смежными.
Задание графа матрицей смежности вершин. Обозначим через
x
1
,
x
2
, …, x
n
вершины графа, а через u
1
,
u
2
, …, u
m
– его дуги. Введем
следующие числа:
⎩
⎨
⎧
=
смежны. не , вершины если,0
смежны; , вершины если,1
ij
ij
ij
xx
xx
r
Квадратная матрица R=
⎜⎜
r
ji
⎜⎜
размера n
×
n называется матрицей
смежности вершин графа. Для графа на рис. 2.19 имеем следующую
матрицу. Из этой матрицы видно, что: 1)
множество U есть множество координат
ненулевых клеток матрицы R; 2) отобра-
жение Г(x
i
) – множество номеров ненуле-
вых клеток в i-ом столбце R; 3) Г
-1
(x
i
) –
множество номеров ненулевых клеток в
i-й строке R.
011000
001000
000100
000010
000101
100000
=R
1
2
3
4
5
6
7
3
8
1 2 4 5 6
Рис. 2.19

Страницы