Составители:
Рубрика:
ортогональна всем решениям системы Az = 0.
Пусть z = (z
1
, . . . , z
k
)
T
— решение системы
Az = 0. (2.6)
Это означает, что линейная комбинация векторов-столбцов мат-
рицы A с коэффициентами z
1
, . . . , z
k
представляет собой нулевой
вектор-столбец. Каждый вектор-столбец является образом некото-
рой дуги графа алгоритма. Это дает основание говорить о линей-
ной комбинации дуг, о линейно независимых дугах и т.п. В целях
упрощения и большей наглядности перейдем от исходного к изо-
морфному графу.
2.5. О представлении графа алгоритма
в пространстве R
n
. Условия существования циклов
Рассмотрим n-мерное арифметическое пространство R
n
и
отождествим вершины v
1
, . . . , v
n
графа G с единичными координат-
ными векторами e
1
, . . . , e
n
из R
n
. Каждой дуге (v
i
, v
j
) этого графа
поставим в соответствие вектор e
i
− e
j
пространства R
n
. Посколь-
ку по предположению исходный граф G не имеет петель и не имеет
кратных дуг, то очевидно, что построенный граф изоморфен гра-
фу G. В дальнейшем, для обоих графов будем использовать одни
и те же обозначения; это не приведет к путанице. Теперь (v
i
, v
j
) и
v
i
− v
j
— различные обозначения одной и той же дуги, а v
i
и v
j
можно считать координатными векторами.
Предположим, что в графе G имеется некоторый цикл
v
i
1
, . . . , v
i
s
, v
i
1
, (2.7)
где s > 1, вершины проходятся слева направо в последовательности
(2.7), а ориентация дуг пока что не принимается во внимание.
Теперь учтем ориентацию дуг следующим образом: если при
указанном обходе цикла (2.7) сначала встречается начальная вер-
шина дуги, а потом — конечная, то будем говорить, что эта дуга
обходится в положительном направлении, а если сначала встречает-
ся конечная вершина, а потом — начальная, то будем говорить, что
дуга обходится в отрицательном направлении. Ввиду отсутствия
кратных дуг для каждой пары (v
i
0
, v
i
00
) соседних вершин последо-
вательности определено либо положительное, либо отрицательное
направление обхода.
89
Страницы
- « первая
- ‹ предыдущая
- …
- 86
- 87
- 88
- 89
- 90
- …
- следующая ›
- последняя »
