Vertici adiacenti in un grafo

Nei grafi i vertici adiacenti sono due vertici (o nodi) che sono collegati tra loro tramite lo stesso spigolo (o arco).

In altre parole, se esiste un arco che ha come estremi questi due vertici, allora si dice che i vertici sono adiacenti.

Ad esempio, in questo grafo i vertici A e C sono adiacenti perché sono direttamente collegati dal lato AC.

Anche i vertici AB sono adiacenti perché sono collegati dal lato AB in modo diretto. Viceversa, i nodi A e D non sono adiacenti perché manca un collegamento diretto tra i vertici.

L'insieme di tutti i vertici adiacenti a un dato vertice \(V\) in un grafo è chiamato neighborhood (vicinato) di \(V\).

Il numero di vertici adiacenti a un vertice $ V $, cioé la dimensione del vicinato di $ V $,  è chiamato grado del vertice $ V $.

Il concetto di vicinato aiuta a comprendere e analizzare le relazioni e le connessioni tra i vertici all'interno di un grafo.

Non occorre che due vertici siano "fisicamente" vicini tra loro nello spazio. Ciò che conta è che siano direttamente collegati da uno spigolo o da un arco.

Ad esempio, in questo grafo i vicini del vertice A sono i nodi B e C. Quindi, il grado del vertice A è 2. I vicini del vertice B, invece, sono i nodi A, C e D. Questo significa che il grafo del vertice B è 3.  Il vertice C ha per vicinato tutti i vertici del grafo perché è connesso direttamente a ciascuno di loro e il grado del vertice C è 4. E via dicendo.

I vertici adiacenti sono importanti perché definiscono la struttura del grafo e le relazioni tra i nodi.

Ad esempio, in un grafo connesso tutti i vertici sono adiacenti ad almeno un altro vertice.

Questa proprietà è fondamentale per la definizione stessa di grafo connesso: non possono esistere vertici completamente isolati, cioè senza nessun arco che li collega ad altri vertici, poiché questo violerebbe la condizione di connessione del grafo.

L'adiacenza nei grafi diretti e non diretti

Il concetto di adiacenza si applica sia ai grafi diretti che a quelli non diretti (grafi semplici).

• In un grafo semplice (non orientato) l'adiacenza è una relazione simmetrica: se il vertice \(A\) è adiacente al vertice \(B\), allora anche \(B\) è adiacente ad \(A\).
  
•  In un grafo diretto (digrafo) l'adiacenza considera la direzione degli archi. Quindi, se c'è un arco diretto da \(A\) a \(B\), allora \(A\) è adiacente a \(B\), ma non è detto che \(B\) sia adiacente ad \(A\), a meno che non ci sia un arco diretto anche da \(B\) ad \(A\). Ad esempio, in questo digrafo A è adiacente a B ma B non è adiacente ad A.
  

Quindi l'uso del termine "adiacenza" nei grafi semplici (non diretti) e nei digrafi (grafi diretti) condivide una base comune ma presenta alcune differenze cruciali dovute alla direzionalità degli archi nei digrafi.

Questa distinzione è importante per il calcolo del grado dei vertici nei digrafi, poiché si deve tenere conto sia degli archi entranti che di quelli uscenti