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

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

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

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

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

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

По определению, матрица композиции отношений $A\circ A$ есть ${𝐀}^{\mathrm{𝟐}}=({a^2}_{ij}{)}_{n\times n}=(\sum _k{a}_{ik}{a}_{kj})=((a_{i1}\wedge a_{1j})\vee (a_{i2}\wedge a_{2j})\vee \dots \vee (a_{in}\wedge a_{nj}))$, где $\wedge$ — конъюнкция, а $\vee$ — дизъюнкция.

После нахождения матриц ${𝐀}^k$ композиций $\underset{k}{\underbrace{A\circ \dots \circ A}}$ для всех $k$, $1\le k\le n-1$ будет получена информация о всех путях длины от $1$ до $n-1$. Таким образом, матрица $𝐑\mathbf{(}𝐆\mathbf{)}=𝐄\vee 𝐀\vee {𝐀}^{\mathrm{𝟐}}\vee \dots \vee {𝐀}^{𝐧\mathbf{-}\mathrm{𝟏}}=({a^{*}}_{ij}{)}_{n\times n}=(a_{ij}\vee {a^2}_{ij}\vee \dots \vee {a^{n-1}}_{ij})$ есть искомая матрица достижимости, где $𝐄$ — единичная матрица.

$𝐄=\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1\end{array}\right)$

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

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

Пример

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

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

$𝐀=\left(\begin{array}{cccc}0& 1& 1& 0\\ 0& 0& 0& 0\\ 0& 1& 0& 1\\ 0& 0& 1& 0\end{array}\right)$

Найдём булевы степени этой матрицы ${𝐀}^{\mathrm{𝟐}}$, ${𝐀}^{\mathrm{𝟑}}$:

${𝐀}^{\mathrm{𝟐}}=\left(\begin{array}{cccc}0& 1& 0& 1\\ 0& 0& 0& 0\\ 0& 0& 1& 0\\ 0& 1& 0& 1\end{array}\right)$, ${𝐀}^{\mathrm{𝟑}}=\left(\begin{array}{cccc}0& 0& 1& 0\\ 0& 0& 0& 0\\ 0& 1& 0& 1\\ 0& 0& 1& 0\end{array}\right)$,

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

$𝐑\mathbf{(}𝐆\mathbf{)}=𝐄\mathbf{\vee }𝐀\mathbf{\vee }{𝐀}^{\mathrm{𝟐}}\mathbf{\vee }{𝐀}^{\mathrm{𝟑}}=\left(\begin{array}{cccc}1& 1& 1& 1\\ 0& 1& 0& 0\\ 0& 1& 1& 1\\ 0& 1& 1& 1\end{array}\right)$

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

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

$𝐑\mathbf{(}𝐆\mathbf{)}=𝐄\mathbf{+}𝐀\mathbf{+}{𝐀}^{\mathrm{𝟐}}\mathbf{+}{𝐀}^{\mathrm{𝟑}}=\left(\begin{array}{cccc}1& 2& 2& 1\\ 0& 1& 0& 0\\ 0& 2& 2& 2\\ 0& 1& 2& 2\end{array}\right)$

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

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

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

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

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

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

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

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

Пример

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

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

${𝐄}^{\mathbf{*}}=\left(\begin{array}{cccc}1& 1& 1& 1\\ 0& 1& 0& 0\\ 0& 1& 1& 1\\ 0& 1& 1& 1\end{array}\right)$

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

$𝐂=\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 1\\ 0& 0& 1& 1\end{array}\right)$

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

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

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

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

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