Matice dosažitelnosti

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 6. dubna 2020; kontroly vyžadují 10 úprav .

Matice dosažitelnosti jednoduchého orientovaného grafu je binární uzavírací maticí s ohledem na tranzitivitu vztahu (je dána maticí sousednosti grafu). Matice dosažitelnosti tedy uchovává informace o existenci cest mezi vrcholy digrafu. $G=(V,A)$ $A$

Metody pro konstrukci matice dosažitelnosti

Maticové násobení

Nechť je dán jednoduchý graf , jehož matice sousednosti je , kde . Matice sousedství poskytuje informace o všech drahách délky 1 (tj. oblouky) v digrafu. Chcete-li hledat cesty délky 2, můžete najít složení vztahu se sebou samým: $G=(V,A)$ $\mathbf {A} =(a_{ij})_{n\times n}$ $a_{ij}=1\Leftrightarrow (i,j)\in A$ $A$

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

Podle definice je matice složení vztahu , kde je konjunkce a je disjunkce . $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 )))$ $\přistát$ $\lor$

Po nalezení matice složení pro všechny budou získány informace o všech cestách délky od do . Matice je tedy požadovaná matice dosažitelnosti . Kde je matice identity. $\mathbf {A} ^{k}$ ${\displaystyle \underbrace {A\circ \ldots \circ A} _{k))$ $k$ $1\leq k\leq n-1$ $jeden$ $n-1$ $\mathbf {R(G)} =\mathbf {E} \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}}$

Případ více cest

Pokud jsou booleovské operace disjunkce a konjunkce nahrazeny obvyklými algebraickými operacemi sčítání a násobení, hledání matice dosažitelnosti se zredukuje na obvyklé postupné násobení matic s následným sčítáním výsledků každého kroku. Výsledná matice se pak bude skládat nejen z 0 a 1 a bude charakterizovat nejen přítomnost cest mezi vrcholy, ale i počet takových cest. V tomto případě můžete povolit přítomnost více hran v grafu. $\lor ,\země$ $+,\krát$ $\mathbf {R(G)}$ $\mathbf {R(G)}$

Příklad

Uvažujme jednoduchý souvislý orientovaný graf . Má matici sousedství ve tvaru: $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}}$

Najděte booleovské mocniny této matice , : $\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}}$

Získejte matici dosažitelnosti

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

Z vrcholu se tak můžete dostat na kteroukoli jinou. $jeden$

Při použití algebraických operací dostaneme matici

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

Ukazuje počet cest délky 0 až 3 mezi vrcholy digrafu.

Warshallův algoritmus

Existuje další algoritmus, který vám umožňuje najít matici dosažitelnosti v přesných krocích – Warshallův algoritmus. $2n^{3}$

Související pojmy

Silně propojená matice

Silně souvislá matice jednoduchého digrafu je binární matice obsahující informace o všech silně souvislých vrcholech v digrafu. Silně propojená matice je symetrická . Silně propojený graf má takovou matici vyplněnou jedničkami.

Konstrukce silně propojené matice

Z matice dosažitelnosti lze sestavit silně propojenou matici. Nechť je matice dosažitelnosti digrafu . Potom se silně propojená matice skládá z prvků . $\mathbf {E} ^{*}$ $G=(V,E)$ $\mathbf {C}$ $(c_{ij})=\left((e_{ij})\land (e_{ji})\vpravo)$