Матрица достижимости простого ориентированого графа G = (V,E) — бинарная матрица замыкания по транзитивности отношения E (оно задаётся матрицей смежности графа). Таким образом, в матрице достижимости хранится информация о существовании путей между вершинами орграфа.
Способы построения матрицы достижимости
Перемножение матриц
Пусть дан простой граф G = (V,E), матрица смежности которого есть 
, где 
. Матрица смежности даёт информацию о всех путяхдлины 1 (то есть, рёбрах) в ографе. Для поиска путей длины 2 можно найти композицию отношения E с самим собой:
.
По определению, матрица композиции отношений 
есть 
, где 
— конъюнкция, а 
— дизъюнкция.
После нахождения матриц 
композиций 
для всех k, 
будет получена информация о всех путях длины от 1 до n. Таким образом, матрица 
есть искомая матрица достижимости.
Матрица сильной связности
Матрица сильной связности простого орграфа — бинарная матрица, содержащая информацию обо всех сильно связанных вершинах в орграфе. Матрица сильной связности симметрична. У сильно связного графа такая матрица заполнена единицами.
Построение матрицы сильной связности
Матрица сильной связности может быть построена из матрицы достижимости. Пусть 
— матрица достижимости орграфа G = (V,E). Тогда матрица сильной связности 
состоит из элементов 
.
