Esistenza
Ogni grafo non orientato e connesso ammette almeno un MST.
Algoritmi · Grafi pesati
Minimum spanning tree
Dato un grafo non orientato, connesso e pesato, un albero ricoprente minimo collega tutti i vertici senza cicli e minimizza la somma dei pesi.
Tre vincoli, un obiettivo
T = (V, ET) deve essere ricoprente, connesso e aciclico, con |ET| = |V| − 1.
w(T) = Σe∈ET w(e) → min
“Minimum” si riferisce al peso totale, non al numero di archi: ogni albero ricoprente ne ha già esattamente |V| − 1. Se il grafo è disconnesso non esiste un singolo MST, ma una foresta ricoprente minima.
Unicità
Se tutti i pesi sono distinti l’MST è unico; pesi uguali possono produrre più soluzioni ottime.
Pesi negativi
Sono ammessi: non esiste il problema di ripetere un ciclo, perché la soluzione è un albero.
Le proprietà che rendono sicure le scelte greedy
Il più leggero che attraversa
Per ogni taglio che rispetta gli archi già scelti, un arco di peso minimo che attraversa il taglio può appartenere a un MST. È la giustificazione di Prim e Kruskal.
Il più pesante può essere escluso
In un ciclo, un arco strettamente più pesante degli altri non appartiene ad alcun MST: togliendolo il grafo resta connesso e costa meno.
Prim vs Kruskal
| Aspetto | Prim | Kruskal |
|---|---|---|
| Crescita | Un solo albero, da una sorgente | Una foresta che si fonde |
| Scelta greedy | Arco minimo tra albero e resto | Arco globale minimo che non crea ciclo |
| Struttura chiave | Coda di priorità | Disjoint Set Union |
| Preferibile | Grafi densi o rappresentazioni per adiacenza | Grafi sparsi già espressi come lista di archi |
Laboratorio: costruisci l’MST
Confronta i due algoritmi sullo stesso grafo. Gli archi verdi sono accettati, quello arancione è in esame e i rossi vengono scartati perché chiuderebbero un ciclo.
Sintassi: A-B:4, A-C:3 · da 2 a 10 vertici, massimo 24 archi.
Esempi
Archi che attraversano il taglio
Archi scelti
Vertici nell’albero
Costo corrente
0
- Archi accettati
- 0
- Archi esaminati
- 0
- Componenti
- —
- Costo totale
- 0
Perché Prim e Kruskal sono corretti
Entrambi mantengono un insieme A di archi contenuto in almeno un MST. Prim considera il taglio fra i vertici già raggiunti e gli altri; Kruskal considera un taglio che separa le due componenti dell’arco candidato. In entrambi i casi l’arco più leggero che attraversa quel taglio è sicuro. Per induzione, dopo |V| − 1 scelte A è un albero ricoprente minimo.
Studio della complessità
| Implementazione | Tempo | Spazio ausiliario | Osservazione |
|---|---|---|---|
| Prim · matrice + scansione | Θ(|V|²) | Θ(|V|) | Buono per grafi densi. |
| Prim · liste + heap binario | O(|E| log |V|) | O(|V| + |E|) | Ogni aggiornamento usa la coda di priorità. |
| Kruskal · sort + DSU | O(|E| log |E|) | O(|V| + |E|) | Il sort domina; log |E| = O(log |V|) nei grafi semplici. |
Con union by rank e path compression, le operazioni DSU costano O(α(|V|)) ammortizzato, praticamente costante. Il simulatore usa scansioni esplicite per rendere ogni candidato visibile; la tabella descrive le implementazioni efficienti.
Applicazioni e limiti
Reti fisiche
Progettazione preliminare di cavi, tubazioni o strade con costo totale minimo.
Clustering
Tagliare gli archi più pesanti dell’MST separa gruppi distanti.
Approssimazioni
L’MST compare in euristiche per TSP metrico e reti di connessione.
MST ≠ cammino minimo. Un MST minimizza il costo dell’intera rete; l’albero dei cammini minimi minimizza le distanze da una sorgente. In generale sono strutture diverse.
Errori comuni ed esercizi
- Usare Prim su archi orientati senza prima chiarire il modello: l’MST classico è definito per grafi non orientati.
- In Kruskal, accettare un arco solo perché è leggero senza verificare se unisce componenti diverse.
- Concludere che l’MST sia unico quando esistono pesi uguali.
Sul grafo classico, prevedi costo e archi prima di eseguire entrambi gli algoritmi.
Cambia la sorgente di Prim: il costo cambia? E gli archi scelti con pesi uguali?
Prova il grafo disconnesso e spiega perché il risultato è una foresta, non un MST.