Всего на сайте:
166 тыс. 848 статей

Главная | Математика

Матрицы достижимости и связности  Просмотрен 507

Пусть A(D) – матрица смежности ориентированного псевдографа D=(V,X) (или псевдографа G=(V,X)), где V={v1,…, vn}. Обозначим через Ak=[a(k)ij] k-ю степень матрицы смежности A(D).

Элемент a(k)ij матрицы Ak ориентированного псевдографа D=(V,X) (псевдографа G=(V,X)) равен числу всех путей (маршрутов) длины k из vi в vj.

Матрица достижимости ориентированного графа D − квадратная матрица T(D)=[tij] порядка n, элементы которой равны

Матрица сильной связности ориентированного графа D − квадратная матрица S(D)=[sij] порядка n, элементы которой равны

Матрица связности графа G − квадратная матрица S(G)=[sij] порядка n, элементы которой равны

Пусть G=(V,X) – граф, V={v1,…, vn}, A(G) – его матрица смежности. Тогда

S(G)=sign[E+A+A2+A3+… An-1] (E- единичная матрица порядка n).

Утверждение 3.Пусть D=(V,X) – ориентированный граф, V={v1,…, vn}, A(D) – его матрица смежности. Тогда

1) T(D)=sign[E+A+A2+A3+… An-1],

2) S(D)=T(D)&TT(D) (TT-транспонированная матрица, &- поэлементное умножение).

 

Предыдущая статья:Матрицы смежности и инцидентности Следующая статья:Расстояния в графе
page speed (0.0105 sec, direct)