Составители:
Рубрика:
§ 2. Матричные представления графов алгоритмов
2.1. Матрицы инциденций и смежности
Рассмотрим ориентированный граф G = (V, E) без петель
и кратных дуг. Пусть все вершины занумерованы числами
i = 1, 2, . . . , n, а дуги перенумерованы числами j = 1, 2, . . . , k .
Определение 2.1. Прямоугольная матрица A = (a
ij
) разме-
ров n × k
a
i,j
=
(
+1, если j-я дуга выходит из i-й вершины,
−1, если j-я дуга входит в i-ю вершину,
0 во всех остальных случаях,
называется матрицей инциденций графа G.
Определение 2.2. Квадратная матрица B = (b
ij
) размеров
n × k
b
i,j
=
½
1, если из i-й вершины в j-ю идет дуга,
0 в противном случае,
называется матрицей смежности графа G.
Пример. Рассмотрим граф алгоритма сложения чисел a и b,
изображенного на рис. 13 (кружками отмечены вершины графа,
внутри кружков — номера вершин, а номера ребер находятся в ром-
биках).
Рис. 13. Граф алгоритма сложения чисел.
Очевидно, здесь n = 4, k = 3; матрица инциденций имеет вид
A =
a
11
a
12
a
13
a
21
a
22
a
23
a
31
a
32
a
33
a
41
a
42
a
43
,
82
Страницы
- « первая
- ‹ предыдущая
- …
- 79
- 80
- 81
- 82
- 83
- …
- следующая ›
- последняя »
