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

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

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

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

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

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

По определению, матрица композиции отношений ${\displaystyle A\circ A}$ есть ${\displaystyle \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 )}}$, где ${\displaystyle \land }$ — конъюнкция, а ${\displaystyle \lor }$ — дизъюнкция.

После нахождения матриц ${\displaystyle \mathbf {A} ^{k}}$ композиций ${\displaystyle \underbrace {A\circ \ldots \circ A} _{k}}$ для всех ${\displaystyle k}$, ${\displaystyle 1\leq k\leq n-1}$ будет получена информация о всех путях длины от ${\displaystyle 1}$ до ${\displaystyle n-1}$. Таким образом, матрица ${\displaystyle \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})}$ есть искомая матрица достижимости, где ${\displaystyle \mathbf {E} }$ — единичная матрица.

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

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

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

Пример

Граф ${\displaystyle G=(V,A)}$

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

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

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

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

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

${\displaystyle \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}}}$

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

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

${\displaystyle \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 между вершинами орграфа.

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

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

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

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

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

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

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

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

Пример

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

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

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

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

${\displaystyle \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 может быть найдена из матрицы достижимости путем ее транспонирования.

Примечания