Matricea de accesibilitate

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 6 aprilie 2020; verificările necesită 10 modificări .

Matricea de accesibilitate a unui graf simplu direcționat este o matrice de închidere binară în raport cu tranzitivitatea relației (este dată de matricea de adiacență a grafului). Astfel, matricea de accesibilitate stochează informații despre existența căilor între vârfurile digrafului. $G=(V,A)$ $A$

Metode pentru construirea unei matrice de accesibilitate

Înmulțirea matricelor

Să fie dat un grafic simplu a cărui matrice de adiacență este , unde . Matricea de adiacență oferă informații despre toate căile de lungime 1 (adică arce) dintr-un digraf. Pentru a căuta căi de lungime 2, se poate găsi compoziția relației cu ea însăși: $G=(V,A)$ $\mathbf {A} =(a_{ij})_{n\times n)$ $a_{ij}=1\Săgeată la stânga (i,j)\in A$ $A$

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

Prin definiție, matricea de compoziție a relațiilor este , unde este conjuncție și este disjuncție . $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 )))$ $\teren$ $\lor$

După găsirea matricelor de compoziție pentru toate , se vor obține informații pe toate căile de lungime de la până la . Astfel, matricea este matricea de accesibilitate dorită , unde este matricea de identitate. $\mathbf {A} ^{k}$ $\underbrace {A\circ \ldots \circ A} _{k)$ $k$ $1\leq k\leq n-1$ $unu$ $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}}$

Cazul căilor multiple

Dacă operațiile booleene de disjuncție și conjuncție sunt înlocuite cu operațiile algebrice obișnuite de adunare și, respectiv, de înmulțire, găsirea matricei de accesibilitate se va reduce la înmulțirea obișnuită pas cu pas a matricelor cu adăugarea ulterioară a rezultatelor fiecărei etape. Atunci matricea rezultată va consta nu numai din 0 și 1 și va caracteriza nu numai prezența căilor între vârfuri, ci și numărul de astfel de căi. În acest caz, puteți permite prezența mai multor muchii în grafic. $\lor ,\land$ $+,\ori$ $\mathbf {R(G)}$ $\mathbf {R(G)}$

Exemplu

Luați în considerare un grafic direct conexat simplu . Are o matrice de adiacență de forma: $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}}$

Găsiți puterile booleene ale acestei matrice : $\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}}$

Obțineți matricea de accesibilitate

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

Astfel, de sus poți ajunge la oricare altul. $unu$

Când folosim operații algebrice, obținem o matrice

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

Arată numărul de căi cu lungimea de la 0 la 3 între vârfurile digrafului.

Algoritmul lui Warshall

Există un alt algoritm care vă permite să găsiți matricea de accesibilitate în exact pași - algoritmul lui Warshall. $2n^{3}$

Concepte înrudite

Strongly Connected Matrix

Matricea puternic conectată a unui digraf simplu este o matrice binară care conține informații despre toate vârfurile puternic conectate din digraf. Matricea puternic conectată este simetrică . Un graf puternic conectat are o astfel de matrice plină cu unele.

Construirea unei matrice puternic conectate

O matrice puternic conectată poate fi construită dintr-o matrice de accesibilitate. Fie matricea de accesibilitate a digrafului . Atunci matricea puternic conectată este formată din elementele . $\mathbf {E} ^{*}$ $G=(V,E)$ $\mathbf {C}$ $(c_{ij})=\left((e_{ij})\land (e_{ji})\dreapta)$