Лекции 14. Основные понятия теории графов. Некоторые виды графов (4 часа)

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

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

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

Утверждение. Пусть G=(V,X) – граф, V={v₁,…, v_n}, A(G) – его матрица смежности. Тогда
S(G)=sign[E+A+A²+A³+… A^n-1] (E- единичная матрица порядка n).
(Следует из предыдущего).
Утверждение. Пусть 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-транспонированная матрица, - поэлементное умножение).
   

Алгоритм выделения компонент сильной связности.
1. Присваиваем p=1, S₁=S(D).
2. Включаем в множество вершин V_p компоненты сильной связности D_p=(V_p,X_p) вершины, соответствующие единицам первой строки матрицы S_p. В качестве матрицы A(D_p) возьмем подматрицу матрицы A(D), состоящую из элементов матрицы A, находящихся на пересечении строк и столбцов, соответствующих вершинам из V_p.
3. Вычеркиваем из S_p строки и столбцы, соответствующие вершинам из V_p. Если не остается ни одной строки (и столбца), то p- кол-во компонент сильной связности. В противном случае обозначим оставшуюся после вычеркивания срок и столбцов матрицу S_p+1, присваиваем p:=p+1 и переходим к п. 2.
Пример.

,


,
,


,

T(D)=sign[E+A+A²+A³+A⁴]= ,

S(D)=TT^T= .