Открыть главное меню

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

Содержание

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

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

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

 .

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

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

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

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

ПримерПравить

 
Граф  

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

 

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

 ,  ,  .

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

 

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

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

 

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

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

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

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

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

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

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

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

ПримерПравить

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

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

 

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

 

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

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

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

Матрица контрдостижимостиПравить

Матрица контрдостижимости Q графа G может быть найдена из матрицы достижимости путем ее транспонирования.

ПримечанияПравить