Minimo albero ricoprente (minimum spanning tree)

Supponiamo di voler creare una rete che interconnetta un insieme di posizioni $V=\{v_1,..,v_n\}$ in modo che per ogni coppia di posizioni esista un percorso che li collega

Alcune coppie di posizioni possono essere collegate direttamente

Stabilire un collegamento diretto tra una coppia di posizioni ha un costo che dipende da vari parametri

<aside> 💡 L’obiettivo è di utilizzare esattamente $n-1$ di questi collegamenti diretti tra coppie di posizioni in modo da connettere l’intera rete e da minimizzare la somma dei costi degli $n-1$ collegamenti stabiliti

</aside>

MST

Input:

• grafo non direzionato connesso $G=(V,E)$
• per ogni arco $e$, $c_e$ = costo dell’arco $e$ ($c_e$ numero reale)

<aside> 💡 Sia dato un grafo non direzionato connesso $G=(V,E)$, uno spanning tree (albero ricoprente) di $G$ è un sottoinsieme di archi $T \subseteq E$ tale che $|T|=n-1$ e gli archi in $T$ non formano cicli

</aside>

In altre parole $T$ forma un albero che ha come nodi tutti i nodi di $G$

Sia dato un grafo non direzionato connesso $G=(V,E)$ tale che ad ogni arco $e$ di $G$ è associato un costo $c_e$, per ogni albero ricoprente $T$ di $G$ definiamo il costo di $T$ come $\Sigma_{e \in T}c_e$

<aside> 💡 Sia dato un grafo non direzionato connesso $G=(V,E)$ con costi $c_e$ degli archi a valori reali, un minimum spanning tree (minimo albero ricoprente) è un sottoinsieme di archi $T\subseteq E$ tale che $T$ è un albero ricoprente di costo minimo

</aside>

Il problema di trovare un minimo albero ricoprente non può essere risolto con un algoritmo di forza bruta

Teorema di Cayley

Ci sono $n^{n-2}$ alberi ricoprenti del grafo completo $K_n$

Algoritmi greedy per MST

• Krusal:
  • comincia con $T= \emptyset$
  • considera gli archi in ordine non decrescente di costo
  • inserisce un arco in $T$ se e solo se il suo inserimento non determina la creazione di un ciclo in $T$
• inverti-cancella:
  • comincia con $T=E$
  • considera gli archi in ordine non crescente dei costi
  • cancella $e$ da $T$ se e solo se la sua cancellazione non rende $T$ disconnesso
• Prim:
  • comincia con un certo nodo $s$ e costruisce un albero $T$ avente $s$ come radice
  • ad ogni passo aggiunge a $T$ l’arco di peso più basso tra quelli che hanno esattamente una delle due estremità in $T$ (se un arco avesse entrambe le estremità in $T$, la sua introduzione in $T$ creerebbe un ciclo)