Матрица достижимости
Матрица достижимости простого ориентированного графа — бинарная матрица замыкания по транзитивности отношения (оно задаётся матрицей смежности графа). Таким образом, в матрице достижимости хранится информация о существовании путей между вершинами орграфа.
Способы построения матрицы достижимости[править | править код]
Перемножение матриц[править | править код]
Пусть дан простой граф , матрица смежности которого есть , где . Матрица смежности даёт информацию о всех путях длины 1 (то есть дугах) в орграфе. Для поиска путей длины 2 можно найти композицию отношения с самим собой:
.
По определению, матрица композиции отношений есть , где — конъюнкция, а — дизъюнкция.
После нахождения матриц композиций для всех , будет получена информация о всех путях длины от до . Таким образом, матрица есть искомая матрица достижимости, где — единичная матрица.
Случай нескольких путей[править | править код]
Если булевы операции дизъюнкции и конъюнкции заменить обычными алгебраическими операциями сложения и умножения соответственно, нахождение матрицы достижимости сведётся к обычному пошаговому перемножению матриц с последующим сложением результатов каждого шага. Тогда получившаяся матрица будет состоять не только из 0 и 1 и будет характеризовать не только наличие путей между вершинами, но уже и количество таких путей. В таком случае можно разрешить наличие кратных рёбер в графе.
Пример[править | править код]
Рассмотрим простой связный ориентированный граф . Он имеет матрицу смежности вида:
Найдём булевы степени этой матрицы , :
, ,
Получим матрицу достижимости
Таким образом, из вершины можно добраться в любую другую.
При использовании же алгебраических операций получится матрица
Она показывает количество путей длины от 0 до 3 между вершинами орграфа.
Алгоритм Уоршелла[править | править код]
Существует другой алгоритм, позволяющий найти матрицу достижимости в точности за шагов — алгоритм Уоршелла.
Связанные понятия[править | править код]
Матрица сильной связности[править | править код]
Матрица сильной связности простого орграфа — бинарная матрица, содержащая информацию обо всех сильно связанных вершинах в орграфе. Матрица сильной связности симметрична. У сильно связного графа такая матрица заполнена единицами.
Построение матрицы сильной связности[править | править код]
Матрица сильной связности может быть построена из матрицы достижимости. Пусть — матрица достижимости орграфа . Тогда матрица сильной связности состоит из элементов .
Пример[править | править код]
Рассмотрим тот же граф, что и ранее.
Его матрица достижимости:
Из неё получаем матрицу сильной связности:
Вершины 3 и 4 сильно связаны друг с другом и сами с собой.
Матрица связности графа[править | править код]
Для обычного (не ориентированного) связного графа существует понятие матрицы связности, сходное с матрицей достижимости.
Этот раздел не завершён. |
Матрица контрдостижимости[править | править код]
Матрица контрдостижимости Q графа G может быть найдена из матрицы достижимости путем ее транспонирования.
Примечания[править | править код]
Для улучшения этой статьи по математике желательно:
|