In questo articolo discuteremo della matrice di adiacenza insieme alla sua rappresentazione.

algoritmo di ricerca binaria

Definizione di matrice di adiacenza

Nella teoria dei grafi, una matrice di adiacenza è un modo denso di descrivere la struttura finita del grafo. È la matrice 2D utilizzata per mappare l'associazione tra i nodi del grafico.

Se un grafico ha N numero di vertici, allora la matrice di adiacenza di quel grafo è n x n e ogni voce della matrice rappresenta il numero di spigoli da un vertice all'altro.

Una matrice di adiacenza è anche chiamata come matrice di connessione . A volte è anche chiamato a Matrice dei vertici .

Rappresentazione della matrice di adiacenza

Se un grafo non orientato G consiste di n vertici, allora la matrice di adiacenza di un grafo è n x n matrice A = [aij] e definita da -

UN_ij= 1 {se esiste un percorso esiste da V_ioa V_J}

UN_ij= 0 {Altrimenti}

Vediamo alcuni dei punti importanti rispetto alla matrice di adiacenza.

• Se esiste un bordo tra il vertice V_ioe V_J, dove i è una riga e j è una colonna, quindi il valore di a_ij= 1.
• Se non c'è alcun bordo tra il vertice V_ioe V_J, allora il valore di a_ij= 0.
• Se non ci sono cicli automatici nel grafo semplice, allora la matrice dei vertici (o matrice di adiacenza) dovrebbe avere 0 nella diagonale.
• Una matrice di adiacenza è simmetrica per un grafo non orientato. Specifica che il valore nel i^thriga e j^thla colonna è uguale al valore in j^thriga i^th
• Se la matrice di adiacenza viene moltiplicata per se stessa e se è presente un valore diverso da zero è presente i^thriga e j^thcolonna, poi c'è il percorso da V_ioa V_J­­con una lunghezza equivalente a 2. Il valore diverso da zero nella matrice di adiacenza rappresenta che è presente il numero di percorsi distinti.

Nota: in una matrice di adiacenza, 0 rappresenta che non esiste alcuna associazione tra due nodi, mentre 1 rappresenta che esiste un'associazione tra due nodi.

Come creare una matrice di adiacenza?

Supponiamo che ci sia un grafico G con N numero di vertici, quindi la matrice dei vertici (o matrice di adiacenza) è data da -

A = un_undiciUN₁₂. . . . . UN_1nUN_ventunoUN₂₂. . . . . UN_2n. . . . . . . . . UN_n1UN_n2. . . . . UN_nn

Dove l'a_ijè uguale al numero di spigoli dal vertice i a j. Come accennato in precedenza, la matrice di adiacenza è simmetrica per un grafo non orientato, quindi per un grafo non orientato, a_ij= un_ehi.

Quando i grafici sono semplici e non ci sono pesi sugli spigoli o su archi multipli, gli elementi della matrice di adiacenza saranno 0 e 1. Se non ci sono auto-loop, gli elementi diagonali della matrice di adiacenza saranno 0.

restituendo un array java

Vediamo ora la matrice di adiacenza per un grafo non orientato e per i grafi diretti.

Matrice di adiacenza per un grafo non orientato

In un grafo non orientato, gli spigoli non sono associati alle direzioni con essi. In un grafo non orientato, se esiste un bordo tra il vertice A e il vertice B, allora i vertici possono essere trasferiti da A a B così come da B ad A.

Consideriamo il grafo non orientato riportato di seguito e proviamo a costruirne la matrice di adiacenza.

Nel grafico, possiamo vedere che non esiste un self-loop, quindi gli elementi diagonali della matrice adiacente saranno 0. La matrice di adiacenza del grafico sopra sarà -

Matrice di adiacenza per un grafo diretto

In un grafo diretto, gli archi formano una coppia ordinata. Gli archi rappresentano un percorso specifico da un vertice A a un altro vertice B. Il nodo A è chiamato nodo iniziale, mentre il nodo B è chiamato nodo terminale.

Consideriamo il grafo indicato di seguito e proviamo a costruirne la matrice di adiacenza.

stringa inversa java

Nel grafico sopra, possiamo vedere che non esiste un self-loop, quindi gli elementi diagonali della matrice adiacente saranno 0. La matrice di adiacenza del grafico sopra sarà -

Proprietà della matrice di adiacenza

Alcune delle proprietà della matrice di adiacenza sono elencate come segue:

• Una matrice di adiacenza è una matrice che contiene righe e colonne utilizzate per rappresentare un semplice grafico etichettato con i numeri 0 e 1 nella posizione di (V_IO, IN_J), a seconda della condizione se i due V_{io ­} e V_Jsono adiacenti.
• Per un grafo diretto, se esiste un bordo tra il vertice i o V_ioal vertice j o V_J, allora il valore di A[V_io][IN_J] = 1, altrimenti il ​​valore sarà 0.
• Per un grafo non orientato, se esiste un bordo tra il vertice i o V_ioal vertice j o V_J, allora il valore di A[V_io][IN_J] = 1 e A[V_J][IN_io] = 1, altrimenti il ​​valore sarà 0.

Vediamo alcune domande sulla matrice delle adiacenze. Le domande seguenti riguardano i grafici ponderati non orientati e diretti.

NOTA: un grafico si dice ponderato se a ciascun bordo viene assegnato un numero positivo, chiamato peso del bordo.

Domanda 1 - Quale sarà la matrice di adiacenza per il grafico ponderato non orientato riportato di seguito?

Soluzione - Nella domanda data, non esiste un self-loop, quindi è chiaro che gli elementi diagonali della matrice adiacente per il grafico sopra saranno 0. Il grafico sopra è un grafico non orientato pesato. I pesi sugli spigoli del grafico saranno rappresentati come voci della matrice di adiacenza.

attore rohit shetty

La matrice di adiacenza del grafico sopra sarà:

Domanda 2 - Quale sarà la matrice di adiacenza per il grafico ponderato indicato di seguito?

Soluzione - Nella domanda data, non esiste un self-loop, quindi è chiaro che gli elementi diagonali della matrice adiacente per il grafico sopra saranno 0. Il grafico sopra è un grafico diretto pesato. I pesi sugli spigoli del grafico saranno rappresentati come voci della matrice di adiacenza.

La matrice di adiacenza del grafico sopra sarà:

Spero che questo articolo ti sia utile per comprendere la matrice di adiacenza. Qui abbiamo discusso la matrice di adiacenza insieme alla sua creazione e proprietà. Abbiamo anche discusso la formazione della matrice di adiacenza su grafi orientati o non orientati, siano essi pesati o meno.