Vizualizare sursă pentru „Matrice de adiacență”

În [[teoria grafurilor]] și [[informatică]], o '''matrice de adiacență''' este o [[matrice pătrată]] folosită pentru a reprezenta un [[graf]] finit. Elementele matricei indică dacă perechea de noduri corespunzătoare sunt sau nu adiacente în graf.

În cazul special al unui [[Graf|grafic finit simplu]], matricea de adiacență este o {{Ill-wd|Q1994977|3=matrice (0,1)}} cu zerouri pe diagonală. Dacă graful este neorientat, atunci matricea de adiacență este [[Matrice simetrică|simetrică]]. 
Relația dintre un graf și [[Vectori și valori proprii|valorile proprii]] și [[Vectori și valori proprii|vectorii proprii]] ale matricei sale de adiacență este studiată în {{Ill-wd|Q3180727|3=teoria spectrală a grafurilor}}.

Se face distincția între matricea de adiacență și matricea de incidență a unui graf, o altă reprezentare matricială ale cărei elemente indică dacă perechile nod–muchie sunt incidente sau nu.

== Definiție ==
Pentru un graf simplu cu mulțimea nodurilor ''V'', matricea de adiacență este o matrice pătrată {{abs|''V''}} X {{abs|''V''}} ''A'' astfel încât elementul ''A''<sub>''ij''</sub> este unu atunci când există o muchie de la nodul ''i'' la nodul ''j'', și zero atunci când nu există o astfel de muchie în graf.<ref>{{Citation|title=Algebraic Graph Theory|year=1993|last=Biggs|first=Norman|series=Cambridge Mathematical Library|at=Definition 2.1, p.&nbsp;7|edition=2nd|publisher=Cambridge University Press}}</ref> Elementele diagonale ale matricei sunt toate zero, deoarece în grafurile simple nu sunt permise muchii de la un nod la el însuși ({{Ill-wd|Q512604|3=bucle}}). De asemenea, este uneori util în teoria algebrică a grafurilor să se înlocuiască elementele nenule cu variabile algebrice.<ref>{{Citation|title=The determinant of the adjacency matrix of a graph|year=1962|last=Harary|first=Frank|author-link=Frank Harary|authorlink=Frank Harary|journal=SIAM Review|volume=4|pages=202–210|doi=10.1137/1004057|DOI=10.1137/1004057}}.</ref>

Același concept poate fi extins la [[multigraf]]uri și grafuri cu bucle, stocând numărul de muchii între două noduri în elementul corespunzător din matrice, și permițând ca elementele diagonale să fie nenule. Buclele pot fi luate în considerare fie o dată (ca o singură muchie) fie de două ori (ca două incidențe separate), atâta timp cât se urmează o convenție consistentă. Grafurile neorientate folosesc adesea această din urmă convenție de numărare a buclelor de două ori, întrucât grafurile orientate de obicei folosesc prima convenție.

=== Matricea de adiacență a unui graf bipartit ===
Matricea de adiacență {{mvar|A}} a unui [[graf bipartit]] ale cărei două părți au {{mvar|r}} și, respectiv, {{mvar|s}} noduri poate fi scrisă sub forma 
: <math>A = \begin{pmatrix} 0_{r,r} & B \\ B^T & 0_{s,s} \end{pmatrix},</math>
unde {{mvar|B}} este o matrice {{mvar|r × s}}, iar 0<sub>{{mvar|r, r}}</sub> și 0<sub>{{mvar|s, s}}</sub> reprezintă [[matrice nulă |matricea nulă]] de dimensiune {{mvar|r × r}} și, respectiv, {{mvar|s × s}}. În acest caz, matricea mai mică {{mvar|B}} reprezintă graful în mod unic, și celelalte părți ale lui {{mvar|A}} pot fi eliminate, deoarece sunt redundante. {{mvar|B}} este uneori numită matricea de biadiacență.

Formal, fie {{mvar|G}} = ({{mvar|U, V, E}}) un [[graf bipartit]] cu părțile {{mvar|U}} = {{{mvar|u}}<sub>1</sub>, … , {{mvar|u<sub>r</sub>}} } și {{mvar|V}} = {{{mvar|v}}<sub>1</sub>, … , {{mvar|v<sub>s</sub>}} }. ''Matricea de biadiacență'' este matricea 0-1 de dimensiuni {{mvar|r × s}} notată cu {{mvar|B}} , în care {{mvar|b<sub>i,j</sub>}} = 1 [[dacă și numai dacă]] ({{mvar|u<sub>i</sub>, v<sub>j</sub>}}) ∈ {{mvar|E}}. 

Dacă {{mvar|G}} este un multigraf bipartit sau un [[Glosar de teoria grafurilor|graf ponderat]] bipartit, atunci elementele {{mvar|b<sub>i,j</sub>}} sunt considerate a fi numărul de muchii între noduri sau, respectiv, ponderea muchiei ({{mvar|u<sub>i</sub>, v<sub>j</sub>}}).

=== Variante ===
O ''matrice de adiacență'' (''a'', ''b'', ''c'') ''A'' a unui graf simplu are ''A''<sub>''i'',''j''</sub> = a , dacă (''i'', ''j'') este muchie, ''b'' dacă nu este, și ''c'' pe diagonală. {{Ill-wd|Q7446630|3=Matricea de adiacență Seidel}} este o ''matrice de adiacență'' (−1, 1, 0). Această matrice este utilizată în studierea {{Ill-wd|Q692823|3=grafurilor tare regulate}} și a {{Ill-wd|Q7858715|3=doi-grafurilor}}.<ref>{{Citat revistă|nume=Seidel|prenume=J. J.|an=1968|titlu=Strongly Regular Graphs with (−1, 1, 0) Adjacency Matrix Having Eigenvalue 3|journal={{Ill-wd|Q13360000|3=Lin. Alg. Appl.}}|volum=1|număr=2|pagini=281–298|doi=10.1016/0024-3795(68)90008-6|DOI=10.1016/0024-3795(68)90008-6}}</ref>

'''Matricea de distanțe''' are în poziția (''i'', ''j'') distanța între nodurile ''v''<sub>''i''</sub> și ''v''<sub>''j''</sub>. Distanța este lungimea drumului celui mai scurt care leagă nodurile. Cu excepția cazului în care se dau explicit lungimile muchiilor, lungimea unui drum este numărul de muchii. Matricea de distanțe seamănă cu o putere mare a matricei de adiacență, dar în loc de a spune doar dacă două noduri sunt conectate (de exemplu, matricea de conectare, care conține valori booleene), dă distanța exactă dintre ele.

== Exemple ==

=== Grafuri neorientate ===
Convenția urmată aici (pentru grafurile neorientate) este că fiecare muchie adaugă 1 la celula corespunzătoare din matrice, și fiecare buclă adaugă 2. Aceasta permite ca gradul unui nod să fie ușor de găsit prin însumarea valorilor de pe rândul sau de pe coloana matricei de adiacență.
{| class="wikitable" style="text-align: center; width: 700px; height: 650px; margin-bottom: 10px; background-repeat: repeat; background-image: none; background-position: 0% 0%;"
!{{Ill-wd|Q5597093|3=Graf etichetat}}
!Matricea de adiacență
|-
|[[Fișier:6n-graph2.svg|219x219px]]
|<math />

Coordonatele sunt 1-6.
|-
|[[Fișier:Symmetric_group_4;_Cayley_graph_1,5,21_(Nauru_Petersen);_numbers.svg|250x250px]]

{{Ill-wd|Q3115524|3=Graf Nauru}}
|[[Fișier:Symmetric_group_4;_Cayley_graph_1,5,21_(adjacency_matrix).svg|250x250px]]

Coordonatele sunt de la 0 la 23.

Câmpurile albe sunt zerouri, câmpurile colorate sunt 1-uri.
|}

=== Grafuri orientate ===
În grafurile orientate, [[Graf orientat|gradul interior]] al unui nod poate fi calculat prin însumarea elementelor de pe coloana corespunzătoare, și gradul exterior poate fi calculat prin însumarea elementelor de pe rândul corespunzător.
{| class="wikitable" style="text-align: center; width: 700px; height: 400px; margin-bottom: 10px; background-repeat: repeat; background-image: none; background-position: 0% 0%;"
!Graf etichetat
!Matricea de adiacență
|-
|[[Fișier:Symmetric_group_4;_Cayley_graph_4,9;_numbers.svg|250x250px]]

{{Ill-wd|Q859174|3=Graful Cayley}} orientat al lui {{Ill-wd|Q849512|3=S}}<sub>4</sub>
|[[Fișier:Symmetric_group_4;_Cayley_graph_4,9_(adjacency_matrix).svg|250x250px]]

Coordonatele sunt 0 la 23.

Cum graficul este orientat, matricea nu este [[Matrice simetrică|simetrică]].
|}

=== Grafuri banale ===
Matricea de adiacență a unui [[graf complet]] conține numai valori 1, cu excepția diagonalei, unde sunt numai zerouri. Matricea de adiacență a unui {{Ill-wd|Q3033506|3=graf vid}} este o [[matrice nulă]].

== Proprietăți ==

=== Spectrul ===
Matricea de adiacență a unui graf neorientat simplu este [[Matrice simetrică|simetrică]], și, prin urmare, are o mulțime completă de [[Vectori și valori proprii|valori proprii reale]] și o bază ortogonală de [[Vectori și valori proprii|vectori proprii]]. Mulțimea valorilor proprii a unui graf este [[spectrul unei matrice |spectrul]] grafului.<ref>{{harvtxt|Biggs|1993}}, Chapter 2 ("The spectrum of a graph"), pp.&nbsp;7–13.</ref> Valorile proprii se notează frecvent cu <math>\lambda_1\geq \lambda_2\geq \cdots \geq \lambda_n.</math>.

Cea mai mare [[vectori și valori proprii |valoare proprie]] <math /> este limiată superior de gradul maxim. Acesta este un rezultat evident al {{Ill-wd|Q1564541|3=teoremei Perron–Frobenius}}, dar se poate demonstra cu ușurință. Fie ''v'' fi un vector propriu asociat lui <math /> și ''x'' componenta în care ''v'' are [[modul |valoare absolută]] maximă. Fără a pierde din generalitate, se presupune că ''v''<sub>''x''</sub> este pozitiv, deoarece în caz contrar, pur și simplu se ia vector propriu <math>-v</math>, asociat și el cu <math>\lambda_1</math>. Atunci
: <math>\lambda v_x=(A v)_x=\sum_{y=1}^n A_{x,y}v_y\leq \sum_{y=1}^n A_{x,y} v_x = v_x \deg(x).</math>
Pentru grafurile ''d''-regulate, ''d'' este prima valoare proprie a lui ''A'' pentru vectorul ''v'' = (1, …, 1) (este ușor de verificat că aceasta este valoare proprie și că este maximul pentru limita dată mai sus). Multiplicitatea acestei valori proprii este numărul de componente conexe din ''G'', în particular <math>\lambda_1>\lambda_2</math> pentru grafurile conexe. Se poate demonstra că pentru fiecare valoare proprie <math>\lambda_i</math>, opusul său <math>-\lambda_i=\lambda_{n+1-i}</math> este, de asemenea, o valoare proprie a lui'' A'' dacă ''G'' este un [[graf bipartit]]. În particular, −''d'' este o valoare proprie a grafurilor bipartite.

Diferența <math>\lambda_1-\lambda_2</math> se numește {{Ill-wd|Q7575194|3=decalaj spectral}} și este legată de {{Ill-wd|Q776602|3=extinderea}} lui ''G''. De asemenea, este util să se definească [[valoare (matematică) |valoarea]] <math>\lambda(G) = \max_{|\lambda_i| < d} |\lambda_i|</math>. Acest număr este mărginit de <math>\lambda(G)\geq 2\sqrt{d-1}-o(1)</math>. Limita este strictă în așa-numitele {{Ill-wd|Q3115527|3=grafuri Ramanujan}}, care au aplicații în multe domenii.

=== Izomorfism și invarianți ===
Se presupune că se dau două grafuri orientate sau neorientate ''G''<sub>1</sub> și ''G''<sub>2</sub> cu matricele de adiacență ''A''<sub>1</sub> și ''A''<sub>2</sub>. ''G''<sub>1</sub> și ''G''<sub>2</sub> sunt {{Ill-wd|Q303100|3=izomorfe}} dacă și numai dacă există o [[Matrici permutare|matrice permutare]] ''P'' astfel încât
: <math>P A_1 P^{-1} = A_2.</math>
În particular, ''A''<sub>1</sub> și ''A''<sub>2</sub> sunt [[asemănarea matricilor |asemenea]] și, prin urmare, au același {{Ill-wd|Q1163608|3=polinom minimal}}, același {{Ill-wd|Q849705|3=polinom caracteristic}}, aceleași valori proprii, același [[Determinant (matematică)|determinant]] și aceeași [[Urmă (algebră)|urmă]]. Prin urmare, acestea pot servi ca invarianți de izomorfism ai grafurilor. Totuși, două grafuri pot să aibă aceeași mulțime de valori proprii, dar să nu fie [[Izomorfism|izomorfe]].<ref>{{Ill-wd|Q5106672|3=Godsil, Chris}}; {{Ill-wd|Q3110923|3=Royle, Gordon}} ''Algebraic Graph Theory'', Springer (2001), {{ISBN|0-387-95241-1}}, p.164</ref> Se spune că acești [[Transformare liniară|operatori liniari]] sunt {{Ill-wd|Q6086323|3=isospectrali}}.

=== Puterile matricei ===
Dacă ''A'' este matricea de adiacență a unui graf orientat sau neorientat ''G'', atunci matricea ''A''<sup>''n''</sup> (adică [[Înmulțirea matricilor|produsul matricial]] a ''n'' copii ale lui ''A'') are o interpretare interesantă: elementul (''i'', ''j'') dă numărul de drumuri (orientate sau neorientate) de lungime ''n'' din nodul ''i'' la nodul ''j''. Dacă ''n'' este cel mai mic [[număr întreg]] nenegativ, astfel încât pentru orice pereche ''i'', ''j'', elementul (''i'', ''j'') din ''A''<sup>''n''</sup> este pozitiv, atunci ''n'' este distanța între nodul ''i'' și nodul ''j''. Acest lucru implică, de exemplu, că numărul de triunghiuri într-un graf neorientat ''G'' este exact [[Urmă (algebră)|urmă]] lui ''A''<sup>3</sup> împărțită la 6. Matricea de adiacență poate fi folosită și pentru a determina dacă graful este sau nu este {{Ill-wd|Q230655|3=conex}}.

== Structuri de date ==
Matricea de adiacență poate fi folosită ca [[structură de date]] pentru {{Ill-wd|Q2479726|3=reprezentarea grafurilor}} în programele pe calculator pentru manipularea grafurilor. Principala structură de date alternativă utilizată în acest scop este [[Listă de adiacență|lista de adiacență]].<ref>{{harvtxt|Goodrich|Tamassia|2015}}, p.&nbsp;361: "There are two data structures that people often use to represent graphs, the adjacency list and the adjacency matrix."</ref><ref name="clrs">{{Citation|title={{Ill-wd|Q1141518}}|year=2001|last=Cormen|last2=Leiserson|last3=Rivest|last4=Stein|first=Thomas H.|first2=Charles E.|first3=Ronald L.|first4=Clifford|author-link=Thomas H. Cormen|authorlink=Thomas H. Cormen|authorlink2=Charles E. Leiserson|authorlink3=Ronald L. Rivest|authorlink4=Clifford Stein|pages=527–531|chapter=Section 22.1: Representations of graphs|edition=Second|publisher=MIT Press and McGraw-Hill|isbn=0-262-03293-7|ISBN=0-262-03293-7}}</ref>

Pentru că fiecare element din matricea de adiacență necesită un singur bit, acesta poate fi reprezentat într-un mod foarte compact, ocupând doar {{abs|''V'' }}<sup>2</sup>/8 octeți pentru reprezentarea unui graf orientat, sau (prin utilizarea unui format  triunghiular compact și stocând doar triunghiul imferior al matricei) aproximativ {{abs|''V'' }}<sup>2</sup>/16 octeți pentru un graf neorientat. Deși sunt posibile și reprezentări mai succinte, această metodă se apropie de limita inferioară dată de [[teoria informației]] pentru numărul minim de biți necesari pentru a reprezenta toate grafurile de n noduri.<ref>{{Citation|title=On the succinct representation of graphs|year=1984|last=Turán|first=György|journal={{Ill-wd|Q5808319}}|volume=8|issue=3|pages=289–294|doi=10.1016/0166-218X(84)90126-4|DOI=10.1016/0166-218X(84)90126-4}}.</ref> Pentru stocarea grafurilor în [[Fișier text|fișiere text]], se pot folosi mai puțini biți per octet pentru a asigura că toți octeții reprezintă caractere de text, de exemplu prin utilizarea unei reprezentări [[Base64]].<ref>{{Citation|title=Description of graph6 and sparse6 encodings|last1=McKay|first1=Brendan|author-link=Brendan McKay|authorlink=Brendan McKay|url=http://cs.anu.edu.au/~bdm/data/formats.txt}}.</ref>
În afară de evitarea irosirii de spațiu, această reprezentare compactă [[Principiul de localitate (informatică)|localitatea referințelor]].
Totuși, pentru un graf rar mare, listele de adiacență necesită mai puțin spațiu de stocare, pentru că nu consumă inutil spațiu pentru a reprezenta muchii care ''nu'' există.

O formă alternativă a matricei de adiacență, care necesită însă o cantitate mai mare de spațiu, înlocuiește numerele din fiecare element al matricei cu pointeri la obiecte muchie (când sunt prezente muchiile) sau cu pointeri null (atunci când nu există nicio muchie).
Este posibilă și stocarea [[Glosar de teoria grafurilor|ponderilor muchiilor]] direct în elementele unei matrice de adiacență.

Pe lângă compromisul de spațiu, diferite structuri de date facilitează și diferite operațiuni. Găsirea tuturor nodurilor adiacente unui anumit nod într-o listă de adiacență este la fel de simplu ca și parcurgerea listei, și necesită un timp proporțional cu numărul de vecini. Cu o matrice de adiacență, trebuie parcurs însă rândul întreg, ceea ce necesită mai mult timp, proporțional cu numărul de noduri din întregul graf. Pe de altă parte, verificarea dacă există o muchie între două noduri se face imediat cu matricea de adiacență, dar la o listă de adiacență necesită un timp proporțional cu gradul minim dintre cele două noduri.<ref name="gt">{{Citation|title=Algorithm Design and Applications|year=2015|last1=Goodrich|last2=Tamassia|first1=Michael T.|first2=Roberto|author1-link=Michael T. Goodrich|author2-link=Roberto Tamassia|page=363|publisher=Wiley}}.</ref>

== Bibliografie ==
<references />

== Legături externe ==
* [http://www.x2d.org/java/projects/fluffschack.jnlp Fluffschack] &#x2014; un joc educativ Java web start care demonstrează relația dintre matricele de adiacență și grafuri.
* [http://opendatastructures.org/versions/edition-0.1e/ods-java/12_1_AdjacencyMatrix_Repres.html Open Data Structures - Secțiunea 12.1 - AdjacencyMatrix: Reprezentarea unui graf printr-o matrice]
* [http://www.cafemath.fr/mathblog/article.php?page=GoodWillHunting.php Café math: Matricele de adiacență ale grafurilor] {{Webarchive|url=https://web.archive.org/web/20190325054550/http://www.cafemath.fr/mathblog/article.php?page=GoodWillHunting.php |date=2019-03-25 }}: Aplicații ale matricelor de adiacență pentru calculul ce generează șiruri de drumuri.
[[Categorie:Matrice]]
[[Categorie:Teoria algebrică a grafurilor]]