Матрица достижимости

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

[править | править код]

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

[править | править код]

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

.

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

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

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

[править | править код]

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

Граф

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

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

, ,

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

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

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

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

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

[править | править код]

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

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

[править | править код]

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

[править | править код]

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

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

[править | править код]

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

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

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

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

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

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

[править | править код]

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

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

[править | править код]

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

Примечания

[править | править код]