Teoria dei grafi: esercizi con soluzioni passo passo

1Vertici, lati e gradi

Un grafo è formato da vertici (punti) e lati (linee tra due vertici). In un grafo semplice non ci sono cappi né lati doppi.

Il grado di un vertice è il numero di lati che vi arrivano. Ogni lato ha due estremi, quindi aggiunge 1 al grado di ciascuno. Ne risulta il lemma delle strette di mano:

Due conseguenze: la somma dei gradi è sempre pari, e anche il numero di vertici di grado dispari è pari.

• Il grafo completo K_n unisce ogni coppia: n(n − 1)/2 lati.
• Il grafo bipartito completo K_m,n unisce ogni vertice di una parte a ogni vertice dell’altra: m·n lati.
• Un grafo k-regolare con n vertici ha n·k/2 lati.

La matrice di adiacenza ha un 1 in (i, j) quando i e j sono uniti. Per un grafo non orientato è simmetrica, la somma di una riga è un grado, e l’elemento (i, j) di Mᴸ conta i cammini di lunghezza L da i a j.

2Eulero e Hamilton

Un circuito euleriano usa ogni lato esattamente una volta e torna al punto di partenza. Un cammino euleriano usa ogni lato una volta ma può finire altrove. Per un grafo connesso:

• tutti i gradi pari: esiste un circuito euleriano;
• esattamente due gradi dispari: esiste un cammino euleriano, da un vertice dispari all’altro;
• più di due gradi dispari: nessuno dei due.

Un ciclo hamiltoniano visita ogni vertice esattamente una volta. Non esiste un semplice test sui gradi. In K_n ci sono (n − 1)!/2 cicli hamiltoniani distinti: si fissa la partenza, si ordinano gli altri n − 1 vertici e si divide per 2 per i due versi.

3Alberi

Un albero è un grafo connesso senza cicli. Ogni albero con n vertici ha esattamente n − 1 lati. Aggiungere un lato qualsiasi crea un ciclo; toglierne uno qualsiasi lo sconnette.

Una foresta di c alberi su n vertici ha n − c lati. Un grafo connesso con m lati mantiene un albero di copertura dopo aver tolto m − n + 1 lati.

Il lemma delle strette di mano permette di contare le foglie: Σ deg = 2(n − 1). Una forma breve è L = 2 + Σ (d − 2) sui vertici di grado d ≥ 3. Un albero con due vertici di grado 3 e il resto foglie ha 2 + 1 + 1 = 4 foglie.

4Dijkstra e alberi di copertura minimi

L’algoritmo di Dijkstra trova le distanze minime da un vertice iniziale in un grafo con pesi non negativi.

1. Assegna distanza 0 al vertice iniziale e ∞ a tutti gli altri.
2. Fissa il vertice non ancora fissato con la distanza minima; la sua distanza è ora definitiva.
3. Per ogni vertice adiacente v, aggiorna d(v) = min(d(v), d(u) + w(u, v)).
4. Ripeti finché il vertice di arrivo non è fissato.

Un albero di copertura minimo collega tutti i vertici con il peso totale più piccolo. Kruskal ordina i lati dal più leggero al più pesante e prende ciascuno a meno che chiuda un ciclo. Prim fa crescere un solo albero a partire da un vertice iniziale, aggiungendo sempre il lato più leggero che ne esce. Entrambi si fermano dopo n − 1 lati.

5Errori comuni

• Dimenticare di dividere per 2 la somma dei gradi per ottenere il numero di lati.
• Verificare l’esistenza di un circuito euleriano senza controllare che il grafo sia connesso.
• Fissare un vertice in Dijkstra prima che abbia la distanza provvisoria minima.
• Prendere gli n − 1 lati più leggeri senza controllare l’assenza di cicli.
• Contare i cicli hamiltoniani di K_n come n! invece che (n − 1)!/2.

6Come sono fatte le domande d’esame

• Facile: gradi e lati. Usi il lemma delle strette di mano, conti i lati di K_n, K_m,n, dei grafi regolari e degli alberi, leggi una matrice di adiacenza o clicchi il vertice con un grado dato.
• Medio: cammini euleriani e alberi. Decidi se un grafo ha un circuito o un cammino euleriano, conti le foglie di un albero, conti i lati da togliere per ottenere un albero di copertura o i cicli hamiltoniani in K_n.
• Difficile: cammini minimi e alberi di copertura. Esegui l’algoritmo di Dijkstra, trovi il vertice fissato in un dato passo, trovi il peso di un albero di copertura minimo, clicchi il lato che Kruskal o Prim aggiunge dopo, o conti i cammini con la matrice di adiacenza.