Minimum spanning tree

Nota sulle fonti: l'argomento è nel programma ufficiale ma non nel materiale del corso consultato; la nota è scritta dal programma con conoscenze standard.

Dato un grafo $G = (V, E, w)$ non diretto, pesato e connesso, un minimum spanning tree (MST, albero di copertura di peso minimo) è uno spanning tree $T$ (vedi Grafi - definizioni e proprietàGrafo G=(V,E) diretto e non diretto, grafo semplice e pesato; incidenza, adiacenza, grado; cammini, cicli, sottografi, grafi connessi e componenti connesse; alberi liberi, foreste, spanning tree e spanning forest; proprietà con dimostrazioni (somma dei gradi = 2m, m <= n(n-1)/2, alberi m = n-1, connessi m >= n-1, foreste m <= n-1).Grafi - definizioni e proprietà →) che minimizza il peso totale $w(T) = \sum_{e \in T} w(e)$. Ha $n - 1$ archi. Applicazione tipica: collegare tutti i nodi di una rete (cavi, broadcast efficiente) con il costo minimo. Se i pesi sono tutti distinti l'MST è unico; altrimenti ce ne può essere più d'uno.

Proprietà del taglio

Un taglio è una partizione $V = A \cup B$ con $A, B$ non vuoti; un arco lo attraversa se ha un estremo in $A$ e uno in $B$.

Proprietà del taglio. Sia $F$ un sottoinsieme degli archi di un qualche MST e sia $(A, B)$ un taglio che nessun arco di $F$ attraversa. Se $e$ è un arco di peso minimo tra quelli che attraversano il taglio, allora $F \cup \{e\}$ è ancora contenuto in un MST.

Dimostrazione. Sia $T$ un MST che contiene $F$. Se $e \in T$ non c'è nulla da dimostrare. Altrimenti $T \cup \{e\}$ contiene un ciclo; questo attraversa il taglio in un altro arco $f \in T$ (un ciclo attraversa un taglio un numero pari di volte, quindi almeno due), con $w(f) \ge w(e)$ per la minimalità di $e$. $T' = T - \{f\} + \{e\}$ è uno spanning tree (connesso, $n-1$ archi) con $w(T') \le w(T)$, quindi è un MST; contiene $F$ perché $f \notin F$ (nessun arco di $F$ attraversa il taglio) e contiene $e$. $\square$

Entrambi gli algoritmi sono greedy: a ogni passo aggiungono un arco "sicuro" in base alla proprietà del taglio.

Algoritmo di Kruskal

Si scorrono gli archi per peso crescente e si aggiunge l'arco se non crea un ciclo con quelli già scelti, cioè se collega due componenti diverse.

Algoritmo Kruskal(G)
ordina E per peso crescente
ogni vertice forma una componente da solo
T <- insieme vuoto
for each e = (u, v) in E nell'ordine do
    if componente(u) != componente(v) then
        T <- T + {e}; fondi le due componenti
return T

Il taglio della proprietà è, a ogni passo, una componente contro il resto: l'arco minimo tra componenti diverse è sicuro. Con una struttura union-find (partizioni con find e union) l'ordinamento costa $O(m \log m) = O(m \log n)$ (perché $m \le n^2$) e le operazioni sulle componenti sono quasi costanti: totale $O(m \log n)$.

Algoritmo di Prim

Si parte da un vertice $s$ e si fa crescere un unico albero, aggiungendo sempre l'arco di peso minimo che collega l'albero a un vertice esterno. Si realizza come Dijkstra (vedi Cammini minimi e algoritmo di DijkstraGrafi pesati, lunghezza di un cammino e distanza; sottocammini di un cammino minimo; problema SSSP; algoritmo di Dijkstra con cloud e priority queue, rilassamento degli archi, esempio svolto; correttezza (due lemmi) e complessità O(min(n^2, (n+m) log n)) con lista non ordinata o heap; pesi non negativi.Cammini minimi e algoritmo di Dijkstra →) con una coda con priorità in cui la chiave di un vertice esterno $v$ è il peso del miglior arco che lo collega all'albero.

Algoritmo Prim(G, s)
forall v in V do v.D <- +infinito; v.parent <- null
s.D <- 0
Q <- coda con priorità con tutti i vertici (chiave v.D)
while Q non è vuota do
    u <- Q.removeMin()           (u entra nell'albero, insieme all'arco (u.parent, u))
    forall (u, v) in E con v in Q do
        if w(u, v) < v.D then v.D <- w(u, v); v.parent <- u; aggiorna Q

La differenza con Dijkstra è nella regola di rilassamento: qui v.D <- w(u,v), non u.D + w(u,v). Gli archi (v.parent, v) formano l'MST. Complessità: come Dijkstra, $O((n + m) \log n)$ con heap e $O(n^2)$ con lista non ordinata.

Esempio svolto

Grafo di Cammini minimi e algoritmo di DijkstraGrafi pesati, lunghezza di un cammino e distanza; sottocammini di un cammino minimo; problema SSSP; algoritmo di Dijkstra con cloud e priority queue, rilassamento degli archi, esempio svolto; correttezza (due lemmi) e complessità O(min(n^2, (n+m) log n)) con lista non ordinata o heap; pesi non negativi.Cammini minimi e algoritmo di Dijkstra →: $AB\,7$, $AC\,9$, $AF\,14$, $BC\,10$, $BD\,15$, $CD\,11$, $CF\,2$, $DE\,6$, $EF\,9$.

Kruskal. Archi ordinati: $CF\,2$, $DE\,6$, $AB\,7$, $AC\,9$, $EF\,9$, $BC\,10$, $CD\,11$, $AF\,14$, $BD\,15$. Si aggiungono $CF$ (componenti $\{C,F\}$), $DE$ ($\{D,E\}$), $AB$ ($\{A,B\}$), $AC$ (fonde in $\{A,B,C,F\}$), $EF$ (fonde tutto: $\{A,B,C,D,E,F\}$, 5 archi: fine); $BC$, $CD$, $AF$, $BD$ sarebbero scartati perché creano cicli. Peso totale $2 + 6 + 7 + 9 + 9 = 33$.

Prim da $A$. Si aggiungono nell'ordine $AB\,(7)$, $AC\,(9)$, $CF\,(2)$, $FE\,(9)$, $ED\,(6)$: stesso albero, peso $33$. (Verificato con un'implementazione in Python di entrambi.)

Attenzione: l'MST non coincide con l'albero dei cammini minimi di Dijkstra da $A$ (lì $D$ ha parent $C$ con l'arco $CD\,11$, qui l'arco è $DE\,6$): minimizzano grandezze diverse (peso totale contro distanze dalla sorgente).

Errori comuni

• Confondere MST e albero dei cammini minimi: obiettivi diversi.
• In Prim usare u.D + w(u,v) (è Dijkstra).
• In Kruskal controllare solo che l'arco non sia già in $T$ invece di verificare che non crei un ciclo.
• Applicare MST a grafi non connessi senza ottenere una foresta di copertura (un MST per componente).