Составители:
Рубрика:
a
11
= 1, a
12
= 0, a
13
= 0,
a
21
= 0, a
22
= 1, a
23
= 0,
a
31
= −1, a
32
= −1, a
33
= 1,
a
41
= 0, a
42
= 0, a
43
= −1.
Итак,
A =
1 0 0,
0 1 0
−1 −1 1
0 0 −1
.
Нетрудно видеть, что матрица смежности такова:
B =
b
11
b
12
b
13
b
14
b
21
b
22
b
23
b
24
b
31
b
32
b
33
b
34
b
41
b
42
b
43
b
44
=
0 0 1 0
0 0 1 0
0 0 0 1
0 0 0 0
.
Заметим, что в каждом столбце матрицы A инциденций графа
G лишь два элемента отличны от нуля; они равны +1 и −1. По-
скольку по предположению граф G не имеет кратных дуг, то мат-
рица A не имеет одинаковых столбцов. Число ненулевых элементов
в строке произвольно. В каждом столбце и в каждой строке матри-
цы смежностей B, вообще говоря, может находиться любое число
ненулевых элементов, но ввиду того, что нет петель, все диагональ-
ные ее элементы равны нулю, а внедиагональные элементы могут
быть либо нулем, либо +1 (кроме того, поскольку нет кратных дуг,
то из соотношения b
ij
= 1, следует соотношение b
ji
= 0).
2.2. О реализации алгоритма
с данной матрицей инциденций
Предположим, что алгоритм с матрицей инциденций A реали-
зуется на некоторой вычислительной системе. Рассмотрим вектор-
столбец t = (t
1
, . . . , t
k
)
T
временной развертки (здесь t
i
— момент
включения функционального устройства, начинающего выполнять
операцию, находящуюся в i-й вершине графа алгоритма; верхний
индекс T означает транспонирование). Рассмотрим кроме этого
вектор реализации h = (h
1
, . . . , h
k
)
T
, где h
j
— время выполнения
83
Страницы
- « первая
- ‹ предыдущая
- …
- 80
- 81
- 82
- 83
- 84
- …
- следующая ›
- последняя »
