Матрица достижимости простого ориентированого графа  — бинарная матрица замыкания по транзитивности отношения (оно задаётся матрицей смежности графа). Таким образом, в матрице достижимости хранится информация о существовании путей между вершинами орграфа.

Способы построения матрицы достижимости

Перемножение матриц

Пусть дан простой граф , матрица смежности которого есть , где . Матрица смежности даёт информацию о всех путях длины 1 (то есть, рёбрах) в ографе. Для поиска путей длины 2 можно найти композицию отношения с самим собой:

.

По определению, матрица композиции отношений есть , где  — конъюнкция, а  — дизъюнкция.

После нахождения матриц композиций для всех , будет получена информация о всех путях длины от до . Таким образом, матрица есть искомая матрица достижимости.

Случай нескольких путей

Если булевы операции дизъюнкции и конъюнкции заменить обычными алгебраическими операциями сложения и умножения соответственно, нахождение матрицы достижимости сведётся к обычному пошаговому перемножению матриц с последующим сложением результатов каждого шага. Тогда получившаяся матрица будет состоять не только из 0 и 1 и будет характеризовать не только наличие путей между вершинами, но уже и количество таких путей. В таком случае можно разрешить наличие кратных рёбер в графе.

Пример

Рассмотрим простой связный ориентированный граф . Он имеет матрицу смежности вида:

Найдём булевы степени этой матрицы , , :

, , .

Получим матрицу достижимости

Таким образом, из вершины можно добраться в любую другую.

При использовании же алгебраических операций получится матрица

Она показывает количество путей длины от 1 до 4 между вершинами орграфа.

Алгоритм Уоршелла

Существует другой алгоритм, позволяющий найти матрицу достижимости в точности за шагов — алгоритм Уоршелла.

Связанные понятия

Матрица сильной связности

Матрица сильной связности простого орграфа — бинарная матрица, содержащая информацию обо всех сильно связанных вершинах в орграфе. Матрица сильной связности симметрична. У сильно связного графа такая матрица заполнена единицами.

Построение матрицы сильной связности

Матрица сильной связности может быть построена из матрицы достижимости. Пусть  — матрица достижимости орграфа . Тогда матрица сильной связности состоит из элементов .

Пример

Рассмотрим тот же граф, что и ранее.

Его матрица достижимости:

Из неё получаем матрицу сильной связности:

Вершины 3 и 4 сильно связаны друг с другом и сами с собой.

Матрица связности графа

Для обычного (не ориентированного) связного графа существует понятие матрицы связности, сходное с матрицей достижимости.