АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

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

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

Элемент a ^{( k )} _ij матрицы A^k ориентированного псевдографа D =(V, X) (псевдографа G =(V, X)) равен числу всех путей (маршрутов) длины k из v_i в v_j.

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

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

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

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

1) T (D)=sign[ E + A + A ²+ A ³+… A ^n-1],

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

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

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

Дата добавления: 2015-09-27 | Просмотры: 576 | Нарушение авторских прав