Vai al contenuto

2.1 Il problema dell'albero ricoprente di costo minimo

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\) è

\[ w(F)=\sum_{e \in F} w_e . \]

Il problema dell'albero ricoprente di costo minimo (MST) chiede un albero ricoprente \(\tilde{T}=(V,\tilde{F})\) di \(G\) di peso minimo:

\[ w(\tilde{F}) \le w(F) \qquad \text{per ogni albero ricoprente } (V,F) \text{ di } G . \]

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\)

Figura 1

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)

\[ \tilde{F}=\big\{\{1,3\},\{2,3\},\{3,4\},\{4,5\},\{5,6\}\big\}, \qquad w(\tilde{F})=1+3+5+2+7=18 . \]

Figura 2

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