ВУЗ:
Составители:
Рубрика:
⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎜
⎝
⎛
=
n
2
1
A0
A
0A
A
,
где A
i
- матрица инциденций, соответствующая компоненту i гра-
фа.
Теорема 9.1.
Ранг матрицы инциденций p - компонентного гра-
фа с n вершинами равен (n-p) при условии, что арифметические
операции производятся по модулю 2.
Доказательство
. Операции сложения строк и перестановки
столбцов не влияют на ранг матрицы. Рассмотрим подматрицу A
i
.
Переставляя столбцы, получим в левом верхнем углу на главной
диагонали единицу. Прибавляя эту строку (по mod 2) к любой
строке, которая имеет ненулевой элемент в первом столбце, полу-
чим, что все элементы первого столбца, исключая первый, равны
нулю. Вторая строка должна иметь ненулевой элемент, который
перестановкой столбцов помещаем на место (2,2) и с помощью
сложения все остальные элементы 2-го столбца обнуляем и т.д.
Прибавляя к последней строке все остальные, обнуляем ее (в каж-
дом столбце ровно 2 единицы).
Получаем матрицу с единицами на диагонали, за исключением
последнего элемента. Ее ранг равен n
i
-1. Поэтому
∑
=
−=−=
p
1i
i
pn1nrangA )(
.
Замечание
. Если G=<V,E> - орграф, то его матрица инциден-
ций определяется следующим образом:
0, если дуга не инцидентна вершине ;
1, если дуга положительно инцидентна вершине
;
34
1, если дуга отрицательно инцидентна вершин ;
2, если дуга - петля в вершине .
ji
j
е
i
ij
j
Матрица смежности вершин
i
ji
ev
ev
a
ev
ev
⎧
⎪
⎪
=
⎨
−
⎪
⎪
⎩
Определение. Матрицей смежности вершин (или просто матри-
цей смежности) называется матрица B размерности ⎢V ⎢
×
⎢V ⎢, эле-
Страницы
- « первая
- ‹ предыдущая
- …
- 32
- 33
- 34
- 35
- 36
- …
- следующая ›
- последняя »
