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

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

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

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

Пусть дан простой граф $G=(V, E)$, матрица смежности которого есть $\mathbf E = (e_{ij})_{n \times n}$, где $e_{ij} = 1 \Leftrightarrow (i, j) \in E$. Матрица смежности даёт информацию о всех путях длины 1 (то есть, рёбрах) в ографе. Для поиска путей длины 2 можно найти композицию отношения $E$ с самим собой:

$E \circ E = \bigl \{ (a, c): \exists b \in V: (a, b),\ (b, c) \in E \bigr \}$.

По определению, матрица композиции отношений $E \circ E$ есть $\mathbf{E^2} = ({e^2}_{ij})_{n \times n}=\Bigl (\sum_k e_{ik} e_{kj} \Bigr )=\Bigl ( (e_{i1} \land e_{1j}) \lor (e_{i2} \land e_{2j} ) \lor \ldots \lor (e_{in} \land e_{nj}) \Bigr )$, где $\land$ — конъюнкция, а $\lor$ — дизъюнкция.

После нахождения матриц $\mathbf E^k$ композиций $\underbrace {E \circ \ldots \circ E}_k$ для всех $k$, $1 \leq k \leq n$ будет получена информация о всех путях длины от $1$ до $n$. Таким образом, матрица $\mathbf {E^*} = \mathbf E \lor \mathbf{E^2} \lor \ldots \lor \mathbf{E^n} = ({e^*}_{ij})_{n \times n} = ({e}_{ij} \lor {e^2}_{ij} \lor \ldots \lor {e^n}_{ij})$ есть искомая матрица достижимости.

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

Если булевы операции $\lor, \land$ дизъюнкции и конъюнкции заменить обычными алгебраическими операциями $+, \times$ сложения и умножения соответственно, нахождение матрицы достижимости $\mathbf{E^*}$ сведётся к обычному пошаговому перемножению матриц с последующим сложением результатов каждого шага. Тогда получившаяся матрица $\mathbf{E^*}$ будет состоять не только из 0 и 1 и будет характеризовать не только наличие путей между вершинами, но уже и количество таких путей. В таком случае можно разрешить наличие кратных рёбер в графе.

Пример

Граф $G=(V, E)$

Рассмотрим простой связный ориентированный граф $G=(V=\{1, 2, 3, 4\}, E=\{(1, 2), (1, 3), (3, 2), (3, 4), (4, 3)\})$. Он имеет матрицу смежности $\mathbf E$ вида:

$\mathbf E = \begin{pmatrix} 0&1&1&0 \\ 0&0&0&0 \\ 0&1&0&1 \\ 0&0&1&0 \end{pmatrix}$

Найдём булевы степени этой матрицы $\mathbf{E^2}$, $\mathbf{E^3}$, $\mathbf{E^4}$:

$\mathbf{E^2} = \begin{pmatrix} 0&1&0&1 \\ 0&0&0&0 \\ 0&0&1&0 \\ 0&1&0&1 \end{pmatrix}$, $\mathbf{E^3} = \begin{pmatrix} 0&0&1&0 \\ 0&0&0&0 \\ 0&1&0&1 \\ 0&0&1&0 \end{pmatrix}$, $\mathbf{E^4} = \begin{pmatrix} 0&1&0&1 \\ 0&0&0&0 \\ 0&0&1&0 \\ 0&1&0&1 \end{pmatrix}$.

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

$\mathbf{E^*} = \mathbf{E \lor E^2 \lor E^3 \lor E^4} = \begin{pmatrix} 0&1&1&1 \\ 0&0&0&0 \\ 0&1&1&1 \\ 0&1&1&1 \end{pmatrix}$

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

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

$\mathbf{E^*} = \begin{pmatrix} 0&3&2&2 \\ 0&0&0&0 \\ 0&2&2&2 \\ 0&2&2&2 \end{pmatrix}$

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

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

Основная статья: Алгоритм Уоршелла

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

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

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

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

Матрица сильной связности может быть построена из матрицы достижимости. Пусть $\mathbf E^*$ — матрица достижимости орграфа $G=(V, E)$. Тогда матрица сильной связности $\mathbf C$ состоит из элементов $(c_{ij}) = \left ( (e_{ij}) \land (e_{ji}) \right )$.

Пример

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

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

$\mathbf{E^*} = \begin{pmatrix} 0&1&1&1 \\ 0&0&0&0 \\ 0&1&1&1 \\ 0&1&1&1 \end{pmatrix}$

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

$\mathbf{C} = \begin{pmatrix} 0&0&0&0 \\ 0&0&0&0 \\ 0&0&1&1 \\ 0&0&1&1 \end{pmatrix}$

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

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

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

Этот раздел не завершён. Вы поможете проекту, исправив и дополнив его.

Для улучшения этой статьи по математике желательно?: Проставить интервики в рамках проекта Интервики. Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное.