Элементы теории графов и их технические приложения - 19 стр.

UptoLike

ВУЗ: 

ТвГТУ | Тверь

Составители: 

Рубрика: 

19
друга одинаковыми перестановками строк и столбцов. Это утверждение
справедливо также для мультиграфов, псевдографов и ориентированных графов.
Из предыдущего утверждения вытекает, что ранги матриц смежности
изоморфных графов равны, что позволяет ввести для абстрактного графа следующее
определение: рангом графа называется граф его матрицы смежности. Обозначать
его будем через rang G.
Пусть S – произвольная подстановка, действующая на
множестве {1,2,…,n}.
Определим бинарную nxn матрицу S, положив
S
ij
=
⎪
⎩
⎪
⎨
⎧
=
случаепротивномв
ijSесли
,0
,)( ,1
Очевидно, что в каждой строке и в каждом столбце матрицы S содержится
ровно по одной единице и det S=
±
1. С помощью прямых вычислений проверяется,
что B=SAS
-1
.
Это означает, что матрицы смежности изоморфных графов подобны, поэтому
равны характеристические полиномы этих матриц. Следовательно, корректно
определение
характеристического полинома графа как характеристического
полинома его матрицы смежности. Спектр этой матрицы, т.е. совокупность корней
характеристического полинома с учетом их кратностей, называется
спектром
графа
.
Рис. 24. Псевдограф и его матрица смежности.
Для взвешенного графа, не содержащего кратных ребер, матрицу смежности
можно определить, положив, что каждый ее ненулевой элемент равняется весу
соответствующего ребра и дуги. Обратно, каждая квадратная матрица n-го порядка
может быть представлена орграфом с n вершинами, дуги которого соединяют
смежные вершины и имеют веса, равные
соответствующим элементам матрицы.
Если матрица симметрична, то она представима неориентированным графом.
Матрица инцидентности.
Другой матрицей, связанной графом G, в котором помечены и вершины и
ребра, является матрица инцидентности. Пусть G – (n, m) – граф, множество вершин
VG={1,2,…, n} графа G, EG={e
1
, e
2
,…, e
m
} – множество его ребер.
Матрицей инцидентности помеченного графа G называется бинарная nхm –
матрица J=J(G), элементы которой определяются условиями:
J
kl
=
⎩
⎨
⎧
случаепротивномв
инцидентныереброиkвершинаесли
l
,0
, ,1

Страницы