Matrice de adiacență

De la Wikipedia, enciclopedia liberă
Jump to navigation Jump to search

Î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 matriceală ale cărei elemente indică dacă perechile nod–muchie sunt incidente sau nu.

Definiție[modificare | modificare sursă]

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 Aij 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[modificare | modificare sursă]

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

unde B este o matrice r × s, iar 0r,r și 0s,s reprezintă matricea zero de dimensiune r × r și, respectiv, s × 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 = {u1, …, ur} și V = {v1, …, vs}. Matricea de biadiacență este matricea 0-1 de dimensiuni r × s notată cu B , în care bi,j = 1 dacă și numai dacă (ui, vj) ∈ E.

Dacă G este un multigraf bipartit sau un graf ponderat bipartit, atunci elementele bi,j sunt considerate a fi numărul de muchii între noduri sau, respectiv, ponderea muchiei (ui, vj).

Variante[modificare | modificare sursă]

O matrice de adiacență (a, b, cA a unui graf simplu are Ai,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 vi și vj. 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[modificare | modificare sursă]

Grafuri neorientate[modificare | modificare sursă]

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ță
6n-graph2.svg

Coordonatele sunt 1-6.

Symmetric group 4; Cayley graph 1,5,21 (Nauru Petersen); numbers.svg

Graf Nauru⁠(d)

Symmetric group 4; Cayley graph 1,5,21 (adjacency matrix).svg

Coordonatele sunt de la 0 la 23.

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

Grafuri orientate[modificare | modificare sursă]

Î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ță
Symmetric group 4; Cayley graph 4,9; numbers.svg

Graful Cayley⁠(d) orientat al lui S⁠(d)4

Symmetric group 4; Cayley graph 4,9 (adjacency matrix).svg

Coordonatele sunt 0 la 23.

Cum graficul este orientat, matricea nu este simetrică.

Grafuri banale[modificare | modificare sursă]

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ă⁠(d).

Proprietăți[modificare | modificare sursă]

Spectrul[modificare | modificare sursă]

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 .

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ă vx este pozitiv, deoarece în caz contrar, pur și simplu se ia vector propriu , asociat și el cu . Atunci

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

Izomorfism și invarianți[modificare | modificare sursă]

Se presupune că se dau două grafuri orientate sau neorientate G1 și G2 cu matricele de adiacență A1 și A2. G1 și G2 sunt izomorfe⁠(d) dacă și numai dacă există o matrice permutare P astfel încât

În special, A1 și A2 sunt similare⁠(d) ș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. Cu toate acestea, 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[modificare | modificare sursă]

Dacă A este matricea de adiacență a unui graf orientat sau neorientat G, atunci matricea An (adică produsul matriceal⁠(d) 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 An 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 A3 î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[modificare | modificare sursă]

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  |2/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  |2/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 Base 64⁠(d).[9] În afară de evitarea irosirii de spațiu, această reprezentare compactă localitatea referințelor. Cu toate acestea, 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[modificare | modificare sursă]

  1. ^ Biggs, Norman (), Algebraic Graph Theory, Cambridge Mathematical Library (ed. 2nd), Cambridge University Press, Definition 2.1, p. 7 
  2. ^ Harary, Frank (), „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. (). „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."
  7. ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (), „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 (), „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).
  10. ^ Goodrich, Michael T.; Tamassia, Roberto (), Algorithm Design and Applications, Wiley, p. 363 .

Legături externe[modificare | modificare sursă]