< Indietro | Avanti | Content >
Matrice di Adiacenza: Vertice a vertice
Il grafico di famiglia sostiene che uno dei migliori modi per rappresentarli in una matrice è contare il numero di confine tra due vertici adiacenti.
Si dice che due vertici siano adiacenti o vicini se supportano almeno un bordo comune.
Iniziamo con l’esempio
Il grafico sottostante ha tre vertici. Quindi, facciamo matrice di adiacenza di dimensione 3 per 3. Quindi mettiamo il nome dei vertici sul lato della matrice. Guarda l’immagine e iniziamo con una matrice vuota. Solo i nomi dei vertici ci sono
riempire la matrice di adiacenza, guardiamo il nome del vertice di riga e di colonna. Se questi vertici sono collegati da un bordo o più, contiamo il numero di bordi e mettiamo questo numero come elemento matrice.
Vertex
e vertex
ha un bordo comune, diciamo che Vertex
e vertex
è adiacente (vicina). Inseriamo il numero di spigoli nella cella della matrice che corrispondono a vertex
e vertex
.
Vertice
e
è adiacente da un bordo. Quindi, inseriamo il numero di bordi nella cella della matrice che corrispondono al Vertice 
e 
.
Analogamente, vertex
e
è collegata da un bordo. Quindi, inseriamo il numero di bordi nella cella della matrice che corrispondono al vertice 
e 
Non c’è nessun altro bordo sul grafico, quindi mettiamo il resto delle celle non riempite nella matrice come zero
La matrice per rappresentare una matrice il grafico in questo modo è chiamato matrice di adiacenza .
La dimensione della matrice di adiacenza è uguale al numero di vertici nel grafico. È una matrice quadrata (cioè il numero di righe è uguale al numero di colonne).
La matrice di adiacenza di un grafico è simmetrica perché non ha direzione. Due vertici condividono lo stesso bordo può essere chiamato dal primo al secondo, o dal secondo al primo. Ad esempio, Vertex 
e vertex 
ha un bordo comune, quindi element (a, b) = 1 e element (b, a) = 1.
Proviamo un altro esempio:
Puoi creare la matrice di adiacenza di questo grafico? Provalo prima di guardare la risposta qui sotto.
Il grafico ha 3 vertici, quindi creiamo una dimensione della matrice 3 per 3. Mettiamo il nome dei vertici sul lato della matrice.
Ora guarda il vertice
e vertice
. Quanti bordi supportano i due vertici? Una. Quindi inseriamo questo valore nella matrice
Guarda vertex 
e vertex 
. Quanti bordi supportano questi vertici? Nessuno. Quindi, mettiamo il valore zero nella cella corrispondente nella matrice
Successivamente, si guarda vertex 
e vertice 
. Quanti bordi supportano questi vertici? Due. Quindi inseriamo la matrice in
Poiché non c’è nessun altro bordo nel grafico, possiamo riempire la cella vuota con zeri. Quindi, abbiamo la risposta
Alcuni di voi potrebbero chiedere della parte diagonale della matrice, queste celle sono sempre zero? No, se trovi che il grafico ha un ciclo in alcuni vertici, puoi riempire l’elemento diagonale della matrice di adiacenza con il numero di loop.
Se un grafico ha un vertice che non è collegato ad altri vertici, la matrice di adiacenza corrisponde a quel singolo vertice è zero.
Si prega di fare un po ‘ di pratica per rappresentare il grafico qui sotto nella matrice di adiacenza.
(Vedi la risposta nella pagina precedente)
Data la matrice di adiacenza, puoi disegnare indietro il grafico?
Controllare esempio di applicazione della teoria dei grafi in Q-Learning Tutorial
<Back | Next/Content>