Nåbarhetsmatris

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 6 april 2020; kontroller kräver 10 redigeringar .

Nåbarhetsmatrisen för en enkel riktad graf är en binär stängningsmatris med avseende på relationens transitivitet (den ges av grafens närliggande matris). Således lagrar nåbarhetsmatrisen information om förekomsten av vägar mellan digrafens hörn. $G=(V,A)$ $A$

Metoder för att konstruera en nåbarhetsmatris

Matrismultiplikation

Låt en enkel graf ges vars närliggande matris är , där . Adjacency-matrisen ger information om alla banor med längd 1 (det vill säga bågar) i en digraf. För att söka efter vägar av längd 2 kan man hitta sammansättningen av relationen med sig själv: $G=(V,A)$ ${\displaystyle \mathbf {A} =(a_{ij})_{n\ gånger n))$ $a_{ij}=1\Leftrightarrow (i,j)\in A$ $A$

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

Per definition är relationssammansättningsmatrisen , där är konjunktion och är disjunktion . $A\circ A$ ${\displaystyle \mathbf {A^{2}} =({a^{2}}_{ij})_{n\times n}={\Bigl (}\summa _{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 )))$ $\landa$ $\lor$

Efter att ha hittat sammansättningsmatriserna för alla kommer information att erhållas om alla längdvägar från till . Alltså är matrisen den önskade nåbarhetsmatrisen . Var är identitetsmatrisen. ${\displaystyle \mathbf {A} ^{k))$ ${\displaystyle \underbrace {A\circ \ldots \circ A} _{k))$ $k$ $1\leq k\leq n-1$ $ett$ $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}}$

Fallet med flera sökvägar

Om de booleska operationerna för disjunktion och konjunktion ersätts av de vanliga algebraiska operationerna addition respektive multiplikation, kommer att hitta nåbarhetsmatrisen att reduceras till den vanliga steg-för-steg multiplikationen av matriser med efterföljande addition av resultaten från varje steg. Då kommer den resulterande matrisen inte bara att bestå av 0 och 1 och kommer att karakterisera inte bara närvaron av vägar mellan hörnen utan också antalet sådana vägar. I det här fallet kan du tillåta närvaron av flera kanter i grafen. $\lor ,\land$ $+,\ gånger$ $\mathbf {R(G)}$ $\mathbf {R(G)}$

Exempel

Betrakta en enkel kopplad riktad graf . Den har en närliggande matris av formen: $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}}$

Hitta de booleska potenserna för denna matris , : $\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}}$

Skaffa nåbarhetsmatrisen

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

Således, från toppen kan du komma till vilken annan som helst. $ett$

När vi använder algebraiska operationer får vi en matris

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

Den visar antalet banor med längden 0 till 3 mellan hörnen på digrafen.

Warshalls algoritm

Det finns en annan algoritm som låter dig hitta nåbarhetsmatrisen i exakta steg – Warshalls algoritm. $2n^{3}$

Relaterade begrepp

Starkt ansluten matris

Den starkt anslutna matrisen för en enkel digraf är en binär matris som innehåller information om alla starkt anslutna hörn i digrafen. Den starkt sammankopplade matrisen är symmetrisk . En starkt sammankopplad graf har en sådan matris fylld med ettor.

Konstruktion av en starkt sammankopplad matris

En starkt sammankopplad matris kan konstrueras från en nåbarhetsmatris. Låt vara nåbarhetsmatrisen för digrafen . Då består den starkt sammankopplade matrisen av elementen . $\mathbf {E} ^{*}$ $G=(V,E)$ $\mathbf {C}$ $(c_{ij})=\left((e_{ij})\land (e_{ji})\right)$