Практикум по дисциплине «Дискретная математика»


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



бет3/25
Дата10.01.2020
өлшемі0,98 Mb.
#55624
түріПрактикум
1   2   3   4   5   6   7   8   9   ...   25
Байланысты:
[ZHitnikova N.I.] Teoriya grafov. Praktikum(z-lib.org)

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


Пусть 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, элементы которой равны




Достарыңызбен бөлісу:
1   2   3   4   5   6   7   8   9   ...   25




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет