2.1 Il problema dell'albero ricoprente di costo minimo¶
Parte 2 · Alberi e cammini · Capitolo 2 · Capitolo 2: Alberi ricoprenti · Dispensa, volume 2 (PDF) · Slide · Esercizi: Alberi ricoprenti · App: Alberi ricoprenti minimi: Kruskal e Prim
Definizione 2.1: problema dell'albero ricoprente di costo minimo
Sia \(G=(V,E)\) un grafo non orientato connesso con \(n=|V|\) vertici e \(m=|E|\) spigoli, e sia associato a ogni spigolo \(e \in E\) un peso \(w_e \in \R\). Il peso di un insieme di spigoli \(F \subseteq E\) è
Il problema dell'albero ricoprente di costo minimo (MST) chiede un albero ricoprente \(\tilde{T}=(V,\tilde{F})\) di \(G\) di peso minimo:
Un albero ricoprente di peso minimo è un albero ricoprente di costo minimo. Scriviamo \(w_{uv}\) per il peso dello spigolo \(\{u,v\}\), e identifichiamo un albero ricoprente con il suo insieme di spigoli.
-
Un grafo connesso ha almeno un albero ricoprente, e ne ha un numero finito: un albero ricoprente di costo minimo esiste sempre. Ogni albero ricoprente ha \(n-1\) spigoli.
-
I pesi possono essere negativi. Aggiungere la stessa costante a ogni peso aggiunge \((n-1)\) volte quella costante al peso di ogni albero ricoprente, quindi gli alberi ricoprenti di costo minimo non cambiano.
-
Un albero ricoprente di costo massimo è un albero ricoprente di costo minimo per i pesi \(-w_e\).
Esempio 2.1: il grafo di riferimento pesato
Prendiamo il grafo non orientato soggiacente al grafo di riferimento del capitolo «Grafi», con \(n=6\) vertici, \(m=9\) spigoli e i pesi
| spigolo | \(\{1,2\}\) | \(\{1,3\}\) | \(\{2,3\}\) | \(\{2,4\}\) | \(\{3,4\}\) | \(\{3,5\}\) | \(\{4,5\}\) | \(\{4,6\}\) | \(\{5,6\}\) |
|---|---|---|---|---|---|---|---|---|---|
| \(w_e\) | \(4\) | \(1\) | \(3\) | \(6\) | \(5\) | \(8\) | \(2\) | \(9\) | \(7\) |
Chiamiamo questo grafo grafo di riferimento pesato: tutti gli esempi del capitolo lo usano. I pesi sono gli interi distinti \(1,2,\dots,9\).
Esempio 2.2: l'albero ricoprente di costo minimo del grafo di riferimento
Il grafo di riferimento pesato ha \(55\) alberi ricoprenti. Enumerandoli tutti, il peso minimo è \(18\), raggiunto soltanto dall'albero (in blu nella figura)
L'albero ricoprente \(\{1,2\},\{1,3\},\{2,4\},\{3,5\},\{4,6\}\) trovato dalla visita in ampiezza nel capitolo «Grafi» pesa \(4+1+6+8+9=28\), e un albero ricoprente di costo massimo pesa \(34\).
- Enumerare gli alberi ricoprenti è praticabile solo su grafi piccolissimi: il grafo di riferimento, con \(6\) vertici e \(9\) spigoli, ne ha già \(55\). Gli algoritmi di questo capitolo trovano un albero ricoprente di costo minimo in tempo polinomiale.
2.1.1 Applicazioni¶
-
Progettazione di reti. I vertici sono siti (uffici, case, stabilimenti) e \(w_{uv}\) è il costo di un collegamento diretto (un cavo, un tubo, una strada); la rete più economica che collega tutti i siti è un albero ricoprente di costo minimo.
-
Clustering. Togliendo i \(k-1\) spigoli più pesanti di un albero ricoprente di costo minimo, i vertici si dividono in \(k\) gruppi di punti vicini (clustering a collegamento singolo).
-
Sottoproblema. Gli alberi ricoprenti di costo minimo danno lower bound per il problema del commesso viaggiatore e un punto di partenza per algoritmi euristici di progettazione di reti.
Un albero ricoprente di costo minimo collega tutti i vertici di un grafo pesato connesso con \(n-1\) spigoli di peso totale minimo; sul grafo di riferimento pesato è unico e pesa \(18\).
Avanti: 2.2 Tagli e cicli