Teoria dei grafi — vertici, archi e concetti di base

La teoria dei grafi studia i grafi, cioè strutture formate da vertici e archi. Un vertice è un oggetto, e un arco mostra una relazione tra due oggetti.

Se stai cercando le basi della teoria dei grafi, parti da questa idea: un grafo è un modo semplice per modellare le connessioni. Persone in una rete sociale, città collegate da strade e pagine web collegate tra loro possono essere tutte rappresentate con grafi.

Cosa significa un grafo in matematica

In un grafo non orientato, un arco indica che due vertici sono collegati, e il collegamento non ha direzione. Se $A$ è collegato a $B$, allora anche $B$ è collegato a $A$.

In un grafo orientato, invece, gli archi hanno una direzione, quindi $A \to B$ e $B \to A$ sono affermazioni diverse. Molti esempi introduttivi usano grafi semplici non orientati, cioè senza cappi e senza archi ripetuti tra la stessa coppia di vertici.

Questa condizione è importante perché spesso le definizioni vengono introdotte prima nel caso semplice e non orientato. Se cambia il tipo di grafo, può cambiare anche il significato dei termini.

Termini di base della teoria dei grafi da conoscere per primi

Vertici e archi

Un vertice è l’elemento che vuoi seguire. Un arco è la connessione che vuoi seguire.

Se un grafo modella città e strade, le città sono i vertici e le strade sono gli archi.

Grado

In un grafo non orientato, il grado di un vertice è il numero di archi che incidono su di esso.

Se una città ha strade verso altre tre città, il suo grado è $3$.

Cammino

Un cammino è una sequenza di vertici in cui ogni coppia consecutiva è collegata da un arco.

Se esiste un cammino da un vertice a un altro, puoi passare dall’uno all’altro seguendo gli archi.

Ciclo

Un ciclo è un cammino che inizia e finisce nello stesso vertice. Nella definizione di base più comune, nessun altro vertice si ripete.

Un ciclo mostra che nel grafo c’è un percorso chiuso.

Grafo connesso e componenti connesse

Un grafo non orientato è connesso se ogni vertice può essere raggiunto da ogni altro vertice tramite qualche cammino.

Se questo non accade, il grafo si divide in componenti connesse. Ogni componente è una parte connessa del grafo.

Esempio svolto: un piccolo grafo

Supponiamo che un grafo abbia i vertici $A$, $B$, $C$, $D$ ed $E$, con archi

$$AB,\ AC,\ BC,\ CD$$

Questo dà un triangolo su $A$, $B$ e $C$, un arco in più da $C$ a $D$ e un vertice isolato $E$.

Ora le idee principali sono facili da vedere.

I gradi sono

$$\deg(A)=2,\ \deg(B)=2,\ \deg(C)=3,\ \deg(D)=1,\ \deg(E)=0$$

C’è un cammino da $A$ a $D$:

$$A-C-D$$

C’è un ciclo:

$$A-B-C-A$$

Il grafo non è connesso perché $E$ non può essere raggiunto dagli altri vertici. Quindi il grafo ha due componenti connesse: una che contiene $A,B,C,D$ e una che contiene solo $E$.

Questo unico esempio mostra come grado, cammino, ciclo, vertici isolati e componenti connesse si combinano tra loro.

Un controllo rapido: somma dei gradi

Per ogni grafo non orientato finito,

$$\sum \deg(v) = 2|E|$$

Questo vale perché ogni arco tocca esattamente due estremi, quindi ogni arco aggiunge $1$ a due conteggi di grado.

Nell’esempio sopra, la somma dei gradi è

$$2+2+3+1+0=8$$

e il numero di archi è $4$, quindi

$$2|E| = 2 \cdot 4 = 8$$

Questo è un controllo utile quando conti i gradi a mano. Se i numeri non coincidono, c’è qualcosa che non va.

Errori comuni nella teoria dei grafi

Confondere vertici e archi

I vertici sono gli oggetti. Gli archi sono le relazioni tra di essi.

Dimenticare che tipo di grafo si ha

Un’affermazione vera per un grafo semplice non orientato potrebbe dover essere modificata per un grafo orientato o per un grafo che ammette cappi.

Trattare un cammino come un ciclo

Un cammino non deve tornare al punto di partenza. Un ciclo sì.

Ignorare i vertici isolati

Un vertice di grado $0$ fa comunque parte del grafo. Può cambiare il fatto che il grafo sia connesso.

Dove si usano le basi della teoria dei grafi

Queste idee compaiono nelle reti di computer, nella pianificazione dei percorsi, nella schedulazione, nei sistemi di raccomandazione e nelle reti sociali. Il contesto cambia, ma le stesse domande continuano a comparire: cosa è connesso, cosa può essere raggiunto e dove ci sono cicli?

Per questo la teoria dei grafi compare presto sia nella matematica discreta sia nell’informatica.

Prova con un grafo simile

Disegna quattro vertici $P$, $Q$, $R$ e $S$. Aggiungi gli archi $PQ$, $QR$, $RS$ e $SP$.

Poi rispondi a tre domande: qual è il grado di ogni vertice, il grafo è connesso e il grafo contiene un ciclo?