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

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

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

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

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

A ∘ A = { ( a , c ) : ∃ b ∈ V : ( a , b ) ,   ( b , c ) ∈ A } {displaystyle Acirc A={igl {}(a,c):exists bin V:(a,b), (b,c)in A{igr }}} .

По определению, матрица композиции отношений A ∘ A {displaystyle Acirc A} есть A 2 = ( a 2 i j ) n × n = ( ∑ k a i k a k j ) = ( ( a i 1 ∧ a 1 j ) ∨ ( a i 2 ∧ a 2 j ) ∨ … ∨ ( a i n ∧ a n j ) ) {displaystyle mathbf {A^{2}} =({a^{2}}_{ij})_{n imes 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 } — дизъюнкция.

После нахождения матриц A k {displaystyle mathbf {A} ^{k}} композиций A ∘ … ∘ A ⏟ k {displaystyle underbrace {Acirc ldots circ A} _{k}} для всех k {displaystyle k} , 1 ≤ k ≤ n − 1 {displaystyle 1leq kleq n-1} будет получена информация о всех путях длины от 1 {displaystyle 1} до n − 1 {displaystyle n-1} . Таким образом, матрица R ( G ) = E ∨ A ∨ A 2 ∨ … ∨ A n − 1 = ( a ∗ i j ) n × n = ( a i j ∨ a 2 i j ∨ … ∨ a n − 1 i j ) {displaystyle mathbf {R(G)} =mathbf {E} lor mathbf {A} lor mathbf {A^{2}} lor ldots lor mathbf {A^{n-1}} =({a^{*}}_{ij})_{n imes n}=({a}_{ij}lor {a^{2}}_{ij}lor ldots lor {a^{n-1}}_{ij})} есть искомая матрица достижимости, где E {displaystyle mathbf {E} } — единичная матрица.

E = ( 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 ) {displaystyle mathbf {E} ={egin{pmatrix}1&0&0&0&1&0&0&0&1&0&0&0&1end{pmatrix}}}

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

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

Пример

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

A = ( 0 1 1 0 0 0 0 0 0 1 0 1 0 0 1 0 ) {displaystyle mathbf {A} ={egin{pmatrix}0&1&1&0&0&0&0&1&0&1&0&1&0end{pmatrix}}}

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

A 2 = ( 0 1 0 1 0 0 0 0 0 0 1 0 0 1 0 1 ) {displaystyle mathbf {A^{2}} ={egin{pmatrix}0&1&0&1&0&0&0&0&1&0&1&0&1end{pmatrix}}} , A 3 = ( 0 0 1 0 0 0 0 0 0 1 0 1 0 0 1 0 ) {displaystyle mathbf {A^{3}} ={egin{pmatrix}0&0&1&0&0&0&0&1&0&1&0&1&0end{pmatrix}}} ,

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

R ( G ) = E ∨ A ∨ A 2 ∨ A 3 = ( 1 1 1 1 0 1 0 0 0 1 1 1 0 1 1 1 ) {displaystyle mathbf {R(G)} =mathbf {Elor Alor A^{2}lor A^{3}} ={egin{pmatrix}1&1&1&1&1&0&0&1&1&1&1&1&1end{pmatrix}}}

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

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

R ( G ) = E + A + A 2 + A 3 = ( 1 2 2 1 0 1 0 0 0 2 2 2 0 1 2 2 ) {displaystyle mathbf {R(G)} =mathbf {E+A+A^{2}+A^{3}} ={egin{pmatrix}1&2&2&1&1&0&0&2&2&2&1&2&2end{pmatrix}}}

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

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

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

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

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

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

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

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

Пример

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

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

E ∗ = ( 1 1 1 1 0 1 0 0 0 1 1 1 0 1 1 1 ) {displaystyle mathbf {E^{*}} ={egin{pmatrix}1&1&1&1&1&0&0&1&1&1&1&1&1end{pmatrix}}}

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

C = ( 1 0 0 0 0 1 0 0 0 0 1 1 0 0 1 1 ) {displaystyle mathbf {C} ={egin{pmatrix}1&0&0&0&1&0&0&0&1&1&0&1&1end{pmatrix}}}

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

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

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

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

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