Saavutettavuusmatriisi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 6. huhtikuuta 2020 tarkistetusta versiosta . tarkastukset vaativat 10 muokkausta .

Yksinkertaisen suunnatun graafin saavutettavuusmatriisi on binäärinen sulkeumamatriisi suhteessa transitiivisuuteen (sen antaa graafin viereisyysmatriisi ) . Siten saavutettavuusmatriisi tallentaa tietoa digraafin kärkien välisten polkujen olemassaolosta. $G=(V,A)$ $A$

Menetelmät saavutettavuusmatriisin rakentamiseen

Matriisi kertominen

Annetaan yksinkertainen graafi , jonka vierekkäisyysmatriisi on , missä . Viereisyysmatriisi antaa tietoa kaikista digrafin pituisista poluista (eli kaarista). Etsiäksesi polkuja, joiden pituus on 2, voidaan löytää itsesuhteen koostumus : $G=(V,A)$ ${\displaystyle \mathbf {A} =(a_{ij})_{n\times n))$ $a_{ij}=1\nuoli vasen oikealle (i,j)\in A$ $A$

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

Määritelmän mukaan suhdekoostumusmatriisi on , missä on konjunktio ja disjunktio . $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 )))$ $\maa$ $\lor$

Kun kaikille on löydetty koostumusmatriisit , saadaan tietoa kaikista poluista, joiden pituus on välillä - . Siten matriisi on haluttu saavutettavuusmatriisi , missä on identiteettimatriisi. ${\displaystyle \mathbf {A} ^{k))$ ${\displaystyle \underbrace {A\circ \ldots \circ A} _{k))$ $k$ $1\leq k\leq n-1$ $yksi$ $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}}$

Useiden polkujen tapaus

Jos Boolen disjunktio- ja konjunktiooperaatiot korvataan tavanomaisilla algebrallisilla yhteen- ja kertolaskuoperaatioilla, saavutettavuusmatriisin löytäminen vähennetään matriisien tavanomaiseen vaiheittaiseen kertolaskuun, jonka jälkeen kunkin vaiheen tulokset lisätään. Tällöin tuloksena oleva matriisi ei koostu vain 0:sta ja 1:stä, ja se ei karakterisoi vain kärkien välisten polkujen olemassaoloa, vaan myös tällaisten polkujen määrää . Tässä tapauksessa voit sallia useiden reunojen läsnäolon kaaviossa. $\lor ,\maa$ $+,\ kertaa$ $\mathbf {R(G)}$ $\mathbf {R(G)}$

Esimerkki

Tarkastellaan yksinkertaista yhdistettyä suunnattua graafia . Siinä on vierekkäisyysmatriisi, jonka muoto on: $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}}$

Etsi tämän matriisin Boolen potenssit , : $\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}}$

Hanki saavutettavuusmatriisi

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

Siten ylhäältä pääsee mihin tahansa muuhun. $yksi$

Algebrallisia operaatioita käytettäessä saamme matriisin

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

Se näyttää pituisten 0-3 polkujen lukumäärän digraafin kärkien välillä.

Warshallin algoritmi

On olemassa toinen algoritmi, jonka avulla voit löytää saavutettavuusmatriisin täsmälleen vaiheittain - Warshallin algoritmi. $2n^{3}$

Aiheeseen liittyvät käsitteet

Strongly Connected Matrix

Yksinkertaisen digraafin vahvasti kytketty matriisi on binäärimatriisi, joka sisältää tiedot kaikista vahvasti yhteenliitetyistä digraafin pisteistä. Vahvasti yhdistetty matriisi on symmetrinen . Vahvasti kytketyssä graafissa on sellainen matriisi, joka on täytetty ykkösillä.

Vahvasti kytketyn matriisin rakentaminen

Saavutettavuusmatriisista voidaan rakentaa vahvasti yhdistetty matriisi. Antaa olla digrafin saavutettavuusmatriisi . Tällöin vahvasti yhdistetty matriisi koostuu elementeistä . $\mathbf {E} ^{*}$ $G=(V,E)$ $\mathbf {C}$ $(c_{ij})=\vasen((e_{ij})\land (e_{ji})\oikea)$