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 grafic finit simplu, matricea de adiacență este o matrice (0,1)^⁠(d) cu zerouri pe diagonală. Dacă graful este neorientat, atunci matricea de adiacență este simetrică. Relația dintre un graf și valorile proprii și vectorii proprii ale matricei sale de adiacență este studiată în teoria spectrală a grafurilor^⁠(d).

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ă | V | X | V | A astfel încât elementul A_ij 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.^[1] Elementele diagonale ale matricei sunt toate zero, deoarece în grafurile simple nu sunt permise muchii de la un nod la el însuși (bucle^⁠(d)). De asemenea, este uneori util în teoria algebrică a grafurilor să se înlocuiască elementele nenule cu variabile algebrice.^[2]

Același concept poate fi extins la multigrafuri ș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ță $A$ a unui graf bipartit ale cărei două părți au $r$ și, respectiv, $s$ noduri poate fi scrisă sub forma

A={\begin{pmatrix}0_{r,r}&B\\B^{T}&0_{s,s}\end{pmatrix}},

unde $B$ este o matrice $r \times s$ , iar 0_{$r, r$} și 0_{$s, s$} reprezintă matricea nulă de dimensiune $r \times r$ și, respectiv, $s \times s$ . În acest caz, matricea mai mică $B$ reprezintă graful în mod unic, și celelalte părți ale lui $A$ pot fi eliminate, deoarece sunt redundante. $B$ este uneori numită matricea de biadiacență.

Formal, fie $G$ = ( $U, V, E$ ) un graf bipartit cu părțile $U$ = { $u$ ₁, … , $u r$ } și $V$ = { $v$ ₁, … , $v s$ }. Matricea de biadiacență este matricea 0-1 de dimensiuni $r \times s$ notată cu $B$ , în care $b i,j$ = 1 dacă și numai dacă ( $u i, v j$ ) ∈ $E$ .

Dacă $G$ este un multigraf bipartit sau un graf ponderat bipartit, atunci elementele $b i,j$ sunt considerate a fi numărul de muchii între noduri sau, respectiv, ponderea muchiei ( $u i, v j$ ).

Variante

O matrice de adiacență (a, b, c) A a unui graf simplu are A_i,j = a , dacă (i, j) este muchie, b dacă nu este, și c pe diagonală. Matricea de adiacență Seidel^⁠(d) este o matrice de adiacență (−1, 1, 0). Această matrice este utilizată în studierea grafurilor tare regulate^⁠(d) și a doi-grafurilor^⁠(d).^[3]

Matricea de distanțe are în poziția (i, j) distanța între nodurile v_i și v_j. 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ță.

Graf etichetat^⁠(d)	Matricea de adiacență
	Coordonatele sunt 1-6.
Graf Nauru^⁠(d)	Coordonatele sunt de la 0 la 23. Câmpurile albe sunt zerouri, câmpurile colorate sunt 1-uri.

Grafuri orientate

În grafurile orientate, 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.

Graf etichetat	Matricea de adiacență
Graful Cayley^⁠(d) orientat al lui S^⁠(d)₄	Coordonatele sunt 0 la 23. Cum graficul este orientat, matricea nu este 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 graf vid^⁠(d) este o matrice nulă.

Proprietăți

Spectrul

Matricea de adiacență a unui graf neorientat simplu este simetrică, și, prin urmare, are o mulțime completă de valori proprii reale și o bază ortogonală de vectori proprii. Mulțimea valorilor proprii a unui graf este spectrul grafului.^[4] Valorile proprii se notează frecvent cu $\lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}.$ .

Cea mai mare valoare proprie este limiată superior de gradul maxim. Acesta este un rezultat evident al teoremei Perron–Frobenius^⁠(d), dar se poate demonstra cu ușurință. Fie v fi un vector propriu asociat lui și x componenta în care v are valoare absolută maximă. Fără a pierde din generalitate, se presupune că v_x este pozitiv, deoarece în caz contrar, pur și simplu se ia vector propriu $-v$ , asociat și el cu $\lambda _{1}$ . Atunci

\lambda v_{x}=(Av)_{x}=\sum _{y=1}^{n}A_{x,y}v_{y}\leq \sum _{y=1}^{n}A_{x,y}v_{x}=v_{x}\deg(x).

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 $\lambda _{1}>\lambda _{2}$ pentru grafurile conexe. Se poate demonstra că pentru fiecare valoare proprie $\lambda _{i}$ , opusul său $-\lambda _{i}=\lambda _{n+1-i}$ 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 $\lambda _{1}-\lambda _{2}$ se numește decalaj spectral^⁠(d) și este legată de extinderea^⁠(d) lui G. De asemenea, este util să se definească valoarea $\lambda (G)=\max _{|\lambda _{i}|<d}|\lambda _{i}|$ . Acest număr este mărginit de $\lambda (G)\geq 2{\sqrt {d-1}}-o(1)$ . Limita este strictă în așa-numitele grafuri Ramanujan^⁠(d), care au aplicații în multe domenii.

Izomorfism și invarianți

Se presupune că se dau două grafuri orientate sau neorientate G₁ și G₂ cu matricele de adiacență A₁ și A₂. G₁ și G₂ sunt izomorfe dacă și numai dacă există o matrice permutare P astfel încât

PA_{1}P^{-1}=A_{2}.

În particular, A₁ și A₂ sunt asemenea și, prin urmare, au același polinom minimal^⁠(d), același polinom caracteristic^⁠(d), aceleași valori proprii, același determinant și aceeași 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 izomorfe.^[5] Se spune că acești operatori liniari sunt isospectrali^⁠(d).

Puterile matricei

Dacă A este matricea de adiacență a unui graf orientat sau neorientat G, atunci matricea Aⁿ (adică 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ⁿ 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ă lui A³ împărțită la 6. Matricea de adiacență poate fi folosită și pentru a determina dacă graful este sau nu este conex^⁠(d).

Structuri de date

Matricea de adiacență poate fi folosită ca structură de date pentru reprezentarea grafurilor^⁠(d) în programele pe calculator pentru manipularea grafurilor. Principala structură de date alternativă utilizată în acest scop este lista de adiacență.^[6]^[7]

Pentru că fiecare element din matricea de adiacență necesită un singur bit, acesta poate fi reprezentat într-un mod foarte compact, ocupând doar | V |²/8 octeți pentru reprezentarea unui graf orientat, sau (prin utilizarea unui format triunghiular compact și stocând doar triunghiul imferior al matricei) aproximativ | V |²/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.^[8] Pentru stocarea grafurilor în 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.^[9] În afară de evitarea irosirii de spațiu, această reprezentare compactă 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 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.^[10]

Bibliografie

^ Biggs, Norman (1993), Algebraic Graph Theory, Cambridge Mathematical Library (ed. 2nd), Cambridge University Press, Definition 2.1, p. 7
^ Harary, Frank (1962), „The determinant of the adjacency matrix of a graph”, SIAM Review, 4: 202–210, doi:10.1137/1004057 Mai multe valori specificate pentru |author-link= și |authorlink= (ajutor); Mai multe valori specificate pentru |DOI= și |doi= (ajutor).
^ Seidel, J. J. (1968). „Strongly Regular Graphs with (−1, 1, 0) Adjacency Matrix Having Eigenvalue 3”. Lin. Alg. Appl.^⁠(d). 1 (2): 281–298. doi:10.1016/0024-3795(68)90008-6. Mai multe valori specificate pentru |DOI= și |doi= (ajutor)
^ Biggs (1993), Chapter 2 ("The spectrum of a graph"), pp. 7–13.
^ Godsil, Chris^⁠(d); Royle, Gordon^⁠(d) Algebraic Graph Theory, Springer (2001), ISBN: 0-387-95241-1, p.164
^ Goodrich & Tamassia (2015), p. 361: "There are two data structures that people often use to represent graphs, the adjacency list and the adjacency matrix."
^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), „Section 22.1: Representations of graphs”, Introduction to Algorithms^⁠(d) (ed. Second), MIT Press and McGraw-Hill, pp. 527–531, ISBN 0-262-03293-7 Mai multe valori specificate pentru |author-link= și |authorlink= (ajutor); Mai multe valori specificate pentru |ISBN= și |isbn= (ajutor)
^ Turán, György (1984), „On the succinct representation of graphs”, Discrete Applied Mathematics^⁠(d), 8 (3): 289–294, doi:10.1016/0166-218X(84)90126-4 Mai multe valori specificate pentru |DOI= și |doi= (ajutor).
^ McKay, Brendan, Description of graph6 and sparse6 encodings Mai multe valori specificate pentru |author-link= și |authorlink= (ajutor).
^ Goodrich, Michael T.; Tamassia, Roberto (2015), Algorithm Design and Applications, Wiley, p. 363 .

Legături externe

Fluffschack — un joc educativ Java web start care demonstrează relația dintre matricele de adiacență și grafuri.
Open Data Structures - Secțiunea 12.1 - AdjacencyMatrix: Reprezentarea unui graf printr-o matrice
Café math: Matricele de adiacență ale grafurilor Arhivat în 25 martie 2019, la Wayback Machine.: Aplicații ale matricelor de adiacență pentru calculul ce generează șiruri de drumuri.

[1] Biggs, Norman (1993), Algebraic Graph Theory, Cambridge Mathematical Library (ed. 2nd), Cambridge University Press, Definition 2.1, p. 7

[2] Harary, Frank (1962), „The determinant of the adjacency matrix of a graph”, SIAM Review, 4: 202–210, doi:10.1137/1004057 Mai multe valori specificate pentru |author-link= și |authorlink= (ajutor); Mai multe valori specificate pentru |DOI= și |doi= (ajutor).

[3] Seidel, J. J. (1968). „Strongly Regular Graphs with (−1, 1, 0) Adjacency Matrix Having Eigenvalue 3”. Lin. Alg. Appl.^⁠(d). 1 (2): 281–298. doi:10.1016/0024-3795(68)90008-6. Mai multe valori specificate pentru |DOI= și |doi= (ajutor)

[4] Biggs (1993), Chapter 2 ("The spectrum of a graph"), pp. 7–13.

[5] Godsil, Chris^⁠(d); Royle, Gordon^⁠(d) Algebraic Graph Theory, Springer (2001), ISBN: 0-387-95241-1, p.164

[6] Goodrich & Tamassia (2015), p. 361: "There are two data structures that people often use to represent graphs, the adjacency list and the adjacency matrix."

[clrs-7] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), „Section 22.1: Representations of graphs”, Introduction to Algorithms^⁠(d) (ed. Second), MIT Press and McGraw-Hill, pp. 527–531, ISBN 0-262-03293-7 Mai multe valori specificate pentru |author-link= și |authorlink= (ajutor); Mai multe valori specificate pentru |ISBN= și |isbn= (ajutor)

[8] Turán, György (1984), „On the succinct representation of graphs”, Discrete Applied Mathematics^⁠(d), 8 (3): 289–294, doi:10.1016/0166-218X(84)90126-4 Mai multe valori specificate pentru |DOI= și |doi= (ajutor).

[9] McKay, Brendan, Description of graph6 and sparse6 encodings Mai multe valori specificate pentru |author-link= și |authorlink= (ajutor).

[gt-10] Goodrich, Michael T.; Tamassia, Roberto (2015), Algorithm Design and Applications, Wiley, p. 363 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]