Составители:
Рубрика:
Цикл (2.7) естественно может иметь повторяющиеся вершины
(дублирование v
i
1
в конце списка (2.7) не считается); обход некото-
рых его ребер может совершаться неоднократно. Если при обходе
цикла m-е ребро графа проходится r
m
раз в положительном на-
правлении и s
m
раз — в отрицательном, то m-му ребру ставим в
соответствие число
z
m
= r
m
− s
m
. (2.8)
Остальным ребрам графа поставим в соответствие число 0.
Определение 2.3. Вектор
z = (z
1
, . . . , z
k
) (2.9)
называется вектор-циклом. Вектор-цикл, соответствующий эле-
ментарному циклу (т.е. такому, у которого в последовательности
(2.7) все вершины различны), называется элементарным вектор-
циклом.
Из определения вектор-цикла z следует, что z 6= 0.
Компоненты элементарного вектор-цикла всегда равны либо
+1, либо −1, либо 0.
Теорема 2.4. Любой вектор-цикл z является решением урав-
нения (2.6).
Д о к а з а т е л ь с т в о. Для вектор-дуг любого цикла имеем оче-
видное равенство
(v
i
2
− v
i
1
) + (v
i
3
− v
i
2
) + . . . + (v
i
1
− v
i
s
) = 0. (2.10)
Стоящие в скобках выражения представляют собой вектор-дуги с
точностью до множителя ±1. Этот множитель равен +1, если дуга
в цикле (2.7) проходится в положительном направлении (сперва
встречается ее начало, а затем — конец) и этот множитель равен
−1, в противном случае.
Итак, (2.10) представляет собой линейную комбинацию всех
вектор-дуг графа G (т.е. столбцов матрицы A) с множителями
z
1
, z
2
, . . . , z
k
соответственно.
Теорема доказана.
Следствие 2.3. Если A — матрица инциденций графа с эле-
ментарными циклами, то существуют такие неотрицательные
решения z уравнения (2.6), компоненты которых равны 0, +1, −1.
90
Страницы
- « первая
- ‹ предыдущая
- …
- 87
- 88
- 89
- 90
- 91
- …
- следующая ›
- последняя »
