ВУЗ:
Составители:
Рубрика:
l(v)=r(G). Множество всех центральных вершин графа называется
его центром.
Лекция 9. Матричное представление графов: матрица ин-
циденций, матрица смежности вершин. Список
смежности.
Матрица инциденций
Пусть G=(V,E) - граф, имеющий n вершин и m ребер:
V={v
1
,…,v
n
}, E={e
1
,…, e
m
}. Графу G можно поставить в соответст-
вие матрицу инциденций A размером n×m, строки и столбцы кото-
рой соответствуют вершинам и ребрам графа соответственно. При
этом
0, если ребро не инцидентно вершине ;
1, если ребро инцидентно вершине ;
2, если ребро - петля в вершине .
ji
ij j i
ji
ev
ae v
ev
⎧
⎪
=
⎨
⎪
⎩
Пример 9.1.
123456789
1
2
3
4
5
6
7
110000000
101000000
011100000
000120000
000001100
000001011
000000111
ee e e ee e ee
v
v
v
A
v
v
v
v
⎡
⎤
⎢
⎥
⎢
⎥
⎢
⎥
⎢
⎥
=
⎢
⎥
⎢
⎥
⎢
⎥
⎢
⎥
⎢
⎥
⎣
⎦
v
6
v
1
e
1
e
8
e
6
e
7
v
7
v
5
e
5
e
4
e
3
e
2
v
4
v
3
v
2
e
9
Т.к. каждое ребро инцидентно двум вершинам, то в каждом
столбце матрицы инциденций ровно по две единицы. Исключение
составляет петля. Каждый столбец, соответствующий петле со-
держит одну двойку.
При соответствующей нумерации вершин и ребер графа каж-
дому его компоненту будет соответствовать подматрица матрицы
инциденций, которая в этом случае имеет блочно-диагональную
структуру:
33
Страницы
- « первая
- ‹ предыдущая
- …
- 31
- 32
- 33
- 34
- 35
- …
- следующая ›
- последняя »
