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

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

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

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

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

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

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

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

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

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

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

Пример

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

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

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

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

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

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

$\mathbf {R(G)} =\mathbf {E\lor A\lor A^{2}\lor A^{3}} ={\begin{pmatrix}1&1&1&1\\0&1&0&0\\0&1&1&1\\0&1&1&1\end{pmatrix}}$

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

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

$\mathbf {R(G)} =\mathbf {E+A+A^{2}+A^{3}} ={\begin{pmatrix}1&2&2&1\\0&1&0&0\\0&2&2&2\\0&1&2&2\end{pmatrix}}$

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

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

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

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

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

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

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

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

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

Пример

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

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

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

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

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

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

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

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

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

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