Matricea de adiacență

Un grafic, matricea sa de adiacență este

{\begin{bmatrix}0&1&1&0\\0&0&0&0\\0&1&0&1\\0&0&1&0\end{bmatrix}}

{\ displaystyle {\ begin {bmatrix} 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \ end {bmatrix}}}

{\ begin {bmatrix} 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \ end {bmatrix}}

Matricea de adiacență sau matricea de conexiune constituie o anumită structură de date utilizată în mod obișnuit în reprezentarea graficelor finite. Având în vedere orice grafic, matricea sa de adiacență este alcătuită dintr-o matrice binară pătrată care are numele vârfurilor grafului ca indici de rânduri și coloane. La loc $(i,j)$ ${\ displaystyle (i, j)}$ $(i, j)$ al matricei există un 1 dacă și numai dacă există un arc în grafic care merge de la vârf $the$ ${\ displaystyle i}$ $the$ în vârf $j,$ ${\ displaystyle j,}$ ${\ displaystyle j,}$ altfel se găsește un 0.

Aceste tipuri de matrice sunt utilizate pe scară largă în elaborarea algoritmilor care operează pe grafice finite și, în general, în reprezentarea lor pe computer . Dacă matricea de adiacență este o matrice rară , este de preferat să utilizați lista de adiacență .

Dacă există numere în loc de 1 în matrice, acestea trebuie interpretate ca greutatea atribuită fiecărei conexiuni. De exemplu, dacă setul de vârfuri ale graficului reprezintă o serie de puncte pe o hartă geografică , greutatea arcurilor poate fi interpretată ca distanța punctelor pe care le conectează. Dacă suma elementelor fiecărei coloane este egală cu 1, atunci matricea se numește matrice Markov , deoarece este aplicabilă unui proces Markov .

În cazul reprezentării graficelor nedirecționate, matricea este simetrică în raport cu diagonala principală.

Una dintre caracteristicile fundamentale ale acestei matrice este de a permite obținerea numărului de căi de lungime $n$ ${\ displaystyle n}$ $n$ dintr-un nod $the$ ${\ displaystyle i}$ $the$ la un nod $j;$ ${\ displaystyle j;}$ ${\ displaystyle j;}$ pentru a-l obține este suficient să faci puterea $n$ ${\ displaystyle n}$ $n$ -sima matricei și vedeți numărul care apare în schimb $the, j .$ ${\ displaystyle i, j.}$ ${\ displaystyle i, j.}$