Matricea adiacentei

O matrice de adiacență este o modalitate de a reprezenta un grafic ca o matrice.

Definiție

Matricea de adiacență a unui graf cu un număr finit de vârfuri (numerotate de la 1 la ) este o matrice cu numere întregi pătrate de dimensiunea , în care valoarea elementului este egală cu numărul de muchii de la cel de-al- lea vârf al graficului la cel de-al- lea vârf. $G$ $n$ $n$ ${\mathbf A}$ $n\ ori n$ $a_{i,j}$ $i$ $j$

Uneori, mai ales în cazul unui graf nedirecționat , o buclă (o muchie de la cel de -al -lea vârf până la sine) contează ca două muchii, adică valoarea elementului diagonală în acest caz este egală cu dublul numărului de bucle din jurul al --lea vârf. $i$ $a_{i,i)$ $i$

Matricea de adiacență a unui grafic simplu (care nu conține bucle sau muchii multiple) este o matrice binară și conține zerouri pe diagonala principală .

Matricea de adiacență a unui graf bipartit

Matricea de adiacență a unui graf bipartit , ale cărui părți au și vârfuri , poate fi scrisă în următoarea formă ${\mathbf A}$ $r$ $s$

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

unde este o matrice și și sunt matrice zero . În acest caz, matricea mai mică reprezintă în mod unic graficul, iar părțile rămase ale matricei pot fi aruncate. numită uneori matricea bis-adiacenței. $\mathbf {B}$ $r\times s$ $\mathbf {0} _{r,r)$ $\mathbf {0} _{s,s}$ $r\times r$ $s\ori s$ $\mathbf {B}$ ${\mathbf A}$ $\mathbf {B}$

În mod formal, să fie un grafic bipartit cu părți și . O matrice biconjugată este o matrice 0–1 în care dacă și numai dacă . $G=(U,V,E)$ $U=\{u_{1},\dots ,u_{r}\}$ $V=\{v_{1},\dots ,v_{s}\}$ $r\times s$ $\mathbf {B}$ $b_{i,j}=1$ $(u_{i},v_{j})\in E$

Dacă este un multigraf bipartit sau un grafic ponderat, atunci elementele vor fi numărul de muchii dintre vârfuri sau, respectiv, greutățile muchiilor. $G$ $b_{i,j}$ $(u_{i},v_{j})$

Exemple

Mai jos este un exemplu de grafic nedirecționat și matricea de adiacență corespunzătoare . Acest grafic conține o buclă în jurul vârfului 1 și, în funcție de aplicațiile specifice, un element poate fi considerat egal fie cu unul (așa cum se arată mai jos), fie cu două. ${\mathbf A}$ $a_{1,1}$

Grafic	Matricea adiacentei
	${\displaystyle {\begin{pmatrix}1&1&0&0&1&0\\1&0&1&0&1&0\\0&1&0&1&0&0\\0&0&1&0&1&1\\1&1&0&1&0&0\\0&0&0&1&0&0\end)}{pma$

$a_{i,j}$ este numărul de muchii care leagă vârfurile și , iar în unele aplicații fiecare buclă (muchie pentru unele ) este numărată de două ori. $v_{i}$ $v_{j}$ $\{v_{i},v_{i}\}$ $i$

Matricea de adiacență a unui grafic gol care nu conține muchii constă din toate zerourile.

Proprietăți

Matricea de adiacență a unui grafic nedirecționat este simetrică , ceea ce înseamnă că are valori proprii reale și o bază ortogonală a vectorilor proprii. Setul de valori proprii se numește spectrul grafului și este principalul subiect de studiu în teoria grafurilor spectrale .

Două grafice și cu matrice de adiacență și sunt izomorfe dacă și numai dacă există o matrice de permutare astfel încât $G_{1}$ $G_{2}$ $\mathbf {A} _{1}$ $\mathbf {A} _{2)$ $\mathbf {P}$

\mathbf {P} \mathbf {A} _{1}\mathbf {P} ^{-1}=\mathbf {A} _{2)

De aici rezultă că matricele și sunt similare și, prin urmare, au seturi egale de valori proprii, determinanți și polinoame caracteristice. Cu toate acestea, inversul nu este întotdeauna adevărat - două grafice cu matrici de adiacență similare pot să nu fie izomorfe (acest lucru se întâmplă dacă matricea nu este permutabilă, de exemplu, matricele și sunt similare, dar graficele corespunzătoare nu sunt izomorfe). $\mathbf {A} _{1}$ $\mathbf {A} _{2)$ $\mathbf {P}$ ${\begin{pmatrix}0&1\\0&0\end{pmatrix}}$ ${\begin{pmatrix}0&2\\0&0\end{pmatrix}}$

Puterile matricei

Dacă este matricea de adiacență a graficului , atunci matricea are următoarea proprietate: elementul din rândul --lea, --a coloană este egal cu numărul de căi de la -lea vârf la --lea, constând exact din muchii. ${\mathbf A}$ $G$ $\mathbf {A} ^{m)$ $i$ $j$ $i$ $j$ $m$

Structura datelor

Matricea de adiacență și listele de adiacență sunt principalele structuri de date care sunt utilizate pentru a reprezenta grafice în programele de calculator.

Utilizarea unei matrice de adiacență este de preferat numai în cazul graficelor non-sparse cu un număr mare de muchii, deoarece necesită stocarea unui bit de date pentru fiecare element. Dacă graficul este rar, atunci cea mai mare parte a memoriei va fi irosită stocând zerouri, dar în cazul graficelor non-sparse, matricea de adiacență reprezintă graficul în memorie destul de compact, folosind aproximativ un pic de memorie, care poate fi o ordine de mărime mai bună decât listele de vecinătate. $n^{2}$

În algoritmii care lucrează cu grafice ponderate (de exemplu, în algoritmul Floyd-Warshall ), elementele matricei de adiacență, în loc de numerele 0 și 1, care indică prezența sau absența unei muchii, conțin adesea ponderile muchiilor. înșiși. În același timp, în locul muchiilor lipsă se pune o anumită valoare de limită ( sentinelă engleză ) , în funcție de problema rezolvată, de obicei 0 sau . $\infty$

Vezi și

Literatură

Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algorithms: construction and analysis = Introduction to Algorithms / Ed. I. V. Krasikova. - Ed. a II-a. - M. : Williams, 2005. - 1296 p. — ISBN 5-8459-0857-4 .

Link -uri

Graficul matricei adiacentei. Cod de program în Pascal și C++