WikiSort.ru - Не сортированное

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

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

Пример

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

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

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

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

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

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

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

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

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

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

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

Матрица сильной связности может быть построена из матрицы достижимости. Пусть ${\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}0&1&1&1\\0&0&0&0\\0&1&1&1\\0&1&1&1\end{pmatrix}}}$

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

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

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