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.

Definizione (minimum spanning tree). 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. Perché $n-1$ archi: uno spanning tree è un albero libero con $n$ vertici, quindi ha $m=n-1$ archi (proprietà P3 di 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à →); con meno archi non sarebbe connesso, con di più avrebbe un ciclo, che si potrebbe spezzare togliendo un arco e quindi abbassando il peso (se i pesi sono positivi). Un albero di copertura compare anche nell'analisi dei circuiti (Grafo di una rete ed equazioni indipendentiIl grafo di una rete tiene solo i collegamenti (nodi e lati). Scelto un albero (n−1 lati, connesso, senza maglie), ogni lato di coalbero dà una LKT indipendente e ogni lato d'albero una LKC indipendente: in totale ℓ − n + 1 LKT e n − 1 LKC, che con le ℓ equazioni dei bipoli fanno 2ℓ equazioni per 2ℓ incognite.Grafo di una rete ed equazioni indipendenti →), dove però non si cerca di minimizzare un peso ma di scegliere le equazioni indipendenti. Se i pesi sono tutti distinti l'MST è unico; altrimenti ce ne può essere più d'uno.

Esempio. Nel grafo $AB\,7$, $AC\,9$, $AF\,14$, $BC\,10$, $BD\,15$, $CD\,11$, $CF\,2$, $DE\,6$, $EF\,9$ l'MST ha $n-1=5$ archi e peso $33$.

Proprietà del taglio

Un taglio è una partizione $V = A \cup B$ (Operazioni tra insiemiUnione, intersezione, differenza, complementare e prodotto cartesiano, con le leggi di De Morgan e il legame con la logica.Operazioni tra insiemi →: unione disgiunta, $A\cap B=\emptyset$) 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.

Esempio. Con il taglio $\{A\}$ contro il resto gli archi che lo attraversano pesano $7,9,14$: l'arco $AB\,(7)$ appartiene a un MST. Un secondo taglio, con $F=\{AB\}$ già scelto e $A'=\{A,B\}$, $B'=\{C,D,E,F\}$: gli archi che attraversano sono $AC\,9$, $AF\,14$, $BC\,10$, $BD\,15$; il minimo è $AC\,9$, quindi $F\cup\{AC\}$ è ancora contenuto in un MST.

Dimostrazione (per scambio; usa le tecniche di Tecniche di dimostrazioneDimostrazione diretta, per contronominale e per assurdo di un teorema del tipo ipotesi implica tesi.Tecniche di dimostrazione →). Sia $T$ un MST che contiene $F$. Se $e \in T$ non c'è nulla da dimostrare. Altrimenti $T \cup \{e\}$ contiene un ciclo (aggiungere un arco a un albero ne crea esattamente uno: gli estremi di $e$ erano già collegati da un cammino in $T$); 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

Definizione (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.

Esempio. Nello stesso grafo Kruskal sceglie $CF\,2$, $DE\,6$, $AB\,7$, $AC\,9$, $EF\,9$: peso $2+6+7+9+9=33$.

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)$. Passaggi: l'ordinamento ottimo per confronti costa $\Theta(m\log m)$ (Algoritmi di ordinamentoSelection sort e insertion sort (quadratici, con invarianti), merge sort (divide et impera, Theta(n log n)), quick sort (caso pessimo quadratico, medio n log n), heap sort (in loco, Theta(n log n)), ordinamento senza confronti per chiavi intere in un intervallo piccolo, limite inferiore Omega(n log n) per gli algoritmi basati su confronti.Algoritmi di ordinamento →); da $m\le n^2$ segue $\log_2 m\le 2\log_2 n$ (Esponenziale e logaritmoLa funzione esponenziale a^x (base positiva diversa da 1) e la sua inversa, il logaritmo in base a, con grafici e proprietà.Esponenziale e logaritmo →: $\log n^2=2\log n$), quindi $m\log m=O(m\log n)$. Le componenti sono una partizione di $V$ (Operazioni tra insiemiUnione, intersezione, differenza, complementare e prodotto cartesiano, con le leggi di De Morgan e il legame con la logica.Operazioni tra insiemi →): find(u) dà il rappresentante della componente di $u$, union fonde due componenti; i due estremi sono nella stessa componente se e solo se find(u) = find(v). L'idea è la stessa dell'etichetta v.ID = k della componente connessa in Visite di grafi - BFS e DFSVisite in ampiezza (BFS) e in profondità (DFS) come design pattern; etichette discovery, cross e back edge; BFS tree e distanze; complessità Theta(n+m) con liste di adiacenza; applicazioni (connettività, componenti, spanning tree, cammini minimi non pesati, cicli, vertici a distanza al più d); esempio svolto su un grafo di 7 vertici.Visite di grafi - BFS e DFS →, ma aggiornabile in modo efficiente. È un algoritmo greedy: a ogni passo prende la scelta localmente migliore (l'arco più leggero utile), e la proprietà del taglio garantisce che non ci si pente.

Algoritmo di Prim

Definizione (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.

Esempio. Da $A$ Prim aggiunge $AB\,7$, $AC\,9$, $CF\,2$, $FE\,9$, $ED\,6$: peso $33$, come con Kruskal. L'albero cresce da un solo vertice, mentre Kruskal fa crescere una foresta di più alberi che si fondono; l'invariante di Prim è che l'insieme degli archi scelti forma un albero che contiene $s$, e il taglio della proprietà è "albero contro resto".

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 (ordinando i pesi uguali in ordine alfabetico). 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$.

Gli archi successivi $BC\,(10)$, $CD\,(11)$, $AF\,(14)$, $BD\,(15)$ avrebbero entrambi gli estremi nella stessa componente: aggiungerli chiuderebbe un ciclo.

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.) Chiavi D dei vertici fuori dall'albero, in ordine $(B,C,D,E,F)$:

Il peso è la somma delle chiavi al momento dell'ingresso: $7+9+2+9+6=33$. Si noti che le chiavi non sommano le distanze dalla sorgente (come in Dijkstra) ma tengono il solo peso dell'arco che collega il vertice all'albero.

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