Пусть G = (V, E) граф (орграф) с n вершинами и q ребрами, т.е. V = {v₁, v₂, …, v_n}, E = {e₁, e₂, …, e_q}.

Следующая теорема позволяет по матрице смежности A(G) исследовать маршруты данного графа (орграфа) G.

Теорема. Если A = A(G) — матрица смежности графа (орграфа) G, то a_ij элемент матрицы А^k есть число маршрутов из v_i в v_j длины k.

Следствие. В n вершинном графе (орграфе) G тогда и только тогда существует маршрут из v_i в v_j (i ≠ j), когда (i, j)-й элемент матрицы A + A² + … + A^{n — 1} не равен нулю.

Следствие. В n вершинном графе (орграфе) G тогда и только тогда существует цикл; содержащий вершину a_i, когда (i, i)-й элемент матрицы A + A² + … +A^{n — 1} + Aⁿ не равен нулю.

Образуем из матрицы B = E + A + A² + … +A^{n — 1} + Aⁿ матрицу C = (c_ij) порядка n по следующему правилу:

cij = {	1, если bij ≠ 0
	0, если bij = 0

где b_ij элементы матрицы B.

Матрица C называется матрицей связности, если G — неориентированный граф, и матрицей достижимости, если G — орграф. В графе G тогда и только тогда существует маршрут из v_i в v_j (i ≠ j) когда c_ij = 1. Таким образом, в матрице C содержится информация о существовании связей между различными элементами графа посредством маршрутов. Если G — связный неориентированный граф, то все элементы матрицы связности C равны единице. В общем случае матрица связности неориентированного графа является матрицей отношения эквивалентности, соответствующего разбиению множества вершин графа на компоненты связности.

Пусть C^t транспонированная матрица С. В случае неориентированного графа C = C^t, и является матрицей связности. В случае ориентированного графа C^t называется матрицей контрдостижимости, т.к. если (i, j)-й элемент матрицы C показывает наличие пути из v_i в v_j, то (i, j)-й элемент матрицы C^t показывает наличие обратного пути из v_j в v_i.

Матрицы достижимости и контрдостижимости можно использовать для нахождения сильных компонент орграфа. Рассмотрим матрицу S = C * C^t, где операция * означает поэлементное произведение матриц C и C^t. Элемент s_ij матрицы S равен 1 тогда и только тогда, когда вершины v_i и v_j взаимно достижимы, т. е. v_j достижима из v_i и v_i достижима из v_j. Следовательно, сильная компонента, содержащая вершину v_i, состоит из элементов v_j, для которых s_ij = 1.

Пример. Найти компоненту сильной связности орграфа G, изображенного на рисунке ниже, содержащую вершину 2.

Решение. Матрицы достижимости C и контрдостижимости C^t орграфа, изображенного на предыдущем рисунке, имеют вид:

Из второй строки матрицы S находим, что сильная компонента, содержащая вершину 2, состоит из вершин {1, 2, 3}.