În acest articol, vom discuta despre matricea de adiacență împreună cu reprezentarea acesteia.
șir de listă java
Definirea matricei de adiacență
În teoria grafurilor, o matrice de adiacență este un mod dens de a descrie structura grafului finit. Este matricea 2D care este utilizată pentru a mapa asocierea dintre nodurile graficului.
Dacă un grafic are n numărul de vârfuri, atunci matricea de adiacență a acelui grafic este n x n , iar fiecare intrare a matricei reprezintă numărul de muchii de la un vârf la altul.
O matrice de adiacență se mai numește și ca matricea de conexiuni . Uneori se mai numește și a Matricea vârfurilor .
Reprezentarea matricei de adiacență
Dacă un graf nedirecționat G constă din n vârfuri, atunci matricea de adiacență a unui graf este n x n matrice A = [aij] și este definită de -
Aij= 1 {dacă există o cale există de la Vila Vj}
Aij= 0 {În caz contrar}
Să vedem câteva dintre punctele importante cu privire la matricea de adiacență.
- Dacă există o muchie între vârful Viși Vj, unde i este un rând și j este o coloană, apoi valoarea lui aij= 1.
- Dacă nu există muchie între vârful Viși Vj, apoi valoarea lui aij= 0.
- Dacă nu există bucle proprii în graficul simplu, atunci matricea de vârfuri (sau matricea de adiacență) ar trebui să aibă 0 în diagonală.
- O matrice de adiacență este simetrică pentru un grafic nedirecționat. Se specifică că valoarea din ithrând și jthcoloana este egală cu valoarea din jthrândul ith
- Dacă matricea de adiacență este înmulțită cu ea însăși și dacă există o valoare diferită de zero este prezentă la ithrând și jthcoloană, apoi există traseul de la Vila Vjcu o lungime echivalentă cu 2. Valoarea diferită de zero din matricea de adiacență reprezintă faptul că este prezent numărul de căi distincte.
Notă: Într-o matrice de adiacență, 0 reprezintă că nu există asociere între două noduri, în timp ce 1 reprezintă că există o asociere între două noduri.
Cum se creează o matrice de adiacență?
Să presupunem că există un grafic g cu n numărul de vârfuri, atunci matricea de vârfuri (sau matricea de adiacență) este dată de -
A = aunsprezeceA12. . . . . A1nAdouăzeci și unuA22. . . . . A2n. . . . . . . . . An1An2. . . . . Ann
variabilă javascript globală
Unde aijeste egal cu numărul de muchii de la vârful i la j. După cum sa menționat mai sus, matricea de adiacență este simetrică pentru un graf nedirecționat, deci pentru un graf nedirecționat, unij= ahee.
Când graficele sunt simple și nu există greutăți pe margini sau pe margini multiple, atunci intrările matricei de adiacență vor fi 0 și 1. Dacă nu există bucle proprii, atunci intrările diagonale ale matricei de adiacență vor fi 0.
Acum, să vedem matricea de adiacență pentru un grafic nedirecționat și pentru grafice direcționate.
Matrice de adiacență pentru un grafic nedirecționat
Într-un grafic nedirecționat, muchiile nu sunt asociate cu direcțiile cu acestea. Într-un grafic nedirecționat, dacă există o muchie între vârful A și vârful B, atunci vârfurile pot fi transferate de la A la B, precum și de la B la A.
Să luăm în considerare graficul nedirecționat de mai jos și să încercăm să construim matricea de adiacență a acestuia.
În grafic, putem vedea că nu există o buclă automată, astfel încât intrările diagonale ale matricei adiacente vor fi 0. Matricea de adiacență a graficului de mai sus va fi -
numere blocate
Matricea de adiacență pentru un grafic direcționat
Într-un grafic direcționat, muchiile formează o pereche ordonată. Muchiile reprezintă o cale specifică de la un vârf A la un alt vârf B. Nodul A este numit nod inițial, în timp ce nodul B este numit nod terminal.
Să luăm în considerare graficul direcționat de mai jos și să încercăm să construim matricea de adiacență a acestuia.
În graficul de mai sus, putem vedea că nu există o buclă automată, astfel încât intrările diagonale ale matricei adiacente vor fi 0. Matricea de adiacență a graficului de mai sus va fi -
Proprietățile matricei de adiacență
Unele dintre proprietățile matricei de adiacență sunt enumerate după cum urmează:
- O matrice de adiacență este o matrice care conține rânduri și coloane utilizate pentru a reprezenta un grafic simplu etichetat cu numerele 0 și 1 în poziția (Veu, INj), în funcție de condiția dacă cei doi Vi și Vjsunt adiacente.
- Pentru un graf direcționat, dacă există o muchie între vârful i sau Vila vârful j sau Vj, apoi valoarea lui A[Vi][ÎNj] = 1, altfel valoarea va fi 0.
- Pentru un graf nedirecționat, dacă există o muchie care există între vârful i sau Vila vârful j sau Vj, apoi valoarea lui A[Vi][ÎNj] = 1 și A[Vj][ÎNi] = 1, altfel valoarea va fi 0.
Să vedem câteva întrebări ale matricei de adiacență. Întrebările de mai jos se referă la graficele ponderate nedirecționate și direcționate.
NOTĂ: Se spune că un grafic este graficul ponderat dacă fiecărei muchii i se atribuie un număr pozitiv, care se numește greutatea muchiei.
Intrebarea 1 - Care va fi matricea de adiacență pentru graficul ponderat nedirecționat de mai jos?
Soluție - În întrebarea dată, nu există o buclă automată, deci este clar că intrările diagonale ale matricei adiacente pentru graficul de mai sus vor fi 0. Graficul de mai sus este un grafic nedirecționat ponderat. Greutățile de pe marginile graficului vor fi reprezentate ca intrări ale matricei de adiacență.
Matricea de adiacență a graficului de mai sus va fi -
Intrebarea 2 - Care va fi matricea de adiacență pentru graficul ponderat direcționat de mai jos?
Soluție - În întrebarea dată, nu există o buclă automată, deci este clar că intrările diagonale ale matricei adiacente pentru graficul de mai sus vor fi 0. Graficul de mai sus este un grafic direcționat ponderat. Greutățile de pe marginile graficului vor fi reprezentate ca intrări ale matricei de adiacență.
Matricea de adiacență a graficului de mai sus va fi -
Sper că acest articol vă este benefic pentru a înțelege despre matricea de adiacență. Aici, am discutat despre matricea de adiacență împreună cu crearea și proprietățile acesteia. Am discutat și despre formarea matricei de adiacență pe grafice direcționate sau nedirecționate, indiferent dacă sunt ponderate sau nu.
comenzi linux care