ВУЗ:
Составители:
55
Кроме матрицы смежности вершин графа в теории графов ис-
пользуется матрица смежности дуг графа, которая получается на ос-
нове определения смежности дуг.
Задание графа матрицей инциденций. Определим число s
ij
сле-
дующим образом:
Матрица S=
⎜⎜
s
ji
⎜⎜
размера n
×
m называется матрицей инциден-
ций графа. Матрица инциденций для графа на рис. 2.19 имеет вид
11100000
00110000
10011000
00001110
00000111
01000001
−−
−
−
−
−−
−
=S .
Все рассмотренные способы задания графов допускают преоб-
разование друг в друга.
Пути и маршруты, контуры и циклы. Пу-
тем (или ориентированным маршрутом) оргра-
фа называют последовательность дуг, в кото-
рой конечная вершина всякой дуги, отличной
от последней, является начальной вершиной
следующей. Можно встретить и другие форму-
лировки. Например, путь
между начальной r и
конечной j вершинами графа G представляет
собой направленную последовательность ин-
цидентных дуг (или смежных вершин).
На рис. 2.20 последовательности (2.2) - (2.4) являются путями.
а
6
а
5
а
9
а
8
а
4
(2.2)
S
ij
=
⎪
⎩
⎪
⎨
⎧
−
+
,0
,1
,1
если u
j
исходит из x
i
;
если u
j
заходит из x
i
;
если
ду
ги u
j
нет.
а
1
а
2
а
3
а
4
а
5
а
6
а
7
а
8
х
1
х
2
х
3
х
6
х
4
х
5
а
9
а
10
Рис. 2.20
Страницы
- « первая
- ‹ предыдущая
- …
- 57
- 58
- 59
- 60
- 61
- …
- следующая ›
- последняя »
