Albero di copertura minimo

P

Dato un grafo non orientato connesso G=(V,E)G=(V,E) con un costo cijc_{ij} su ogni arco, si cerca l'albero di copertura (tutti i nodi, n−1n-1 archi, nessun ciclo) di costo totale minimo, per esempio la rete di cavi più economica che collega nn paesi. E(S)E(S) è l'insieme degli archi con entrambi gli estremi in SS.

min⁡ ∑[i,j]∈Ecijxijs.a. ∑[i,j]∈Exij=n−1∑[i,j]∈E(S)xij≤∣S∣−1∀ S⊆V, S≠∅xij∈{0,1}∀ [i,j]∈E\begin{aligned} \min\ & \sum_{[i,j]\in E}c_{ij}x_{ij}\\ \text{s.a.}\ & \sum_{[i,j]\in E}x_{ij}=n-1\\ & \sum_{[i,j]\in E(S)}x_{ij}\le |S|-1 && \forall\,S\subseteq V,\ S\neq\emptyset\\ & x_{ij}\in\{0,1\} && \forall\,[i,j]\in E \end{aligned}

Perché è facile

Il modello ha 2n−12^n-1 vincoli contro i cicli, eppure il problema si risolve in tempo polinomiale. Per il Teorema 4.3.1 l'arco più economico di un taglio sta nell'MST, quindi il greedy di Kruskal è esatto e costa O(mlog⁡n+n2)O(m\log n+n^2).

Da ricordare

  • Con costi tutti diversi, un arco sta nell'MST se e solo se è il più economico di qualche taglio δ(S)\delta(S) (Teorema 4.3.1).
  • Con archi di costo uguale si possono ottenere MST diversi, tutti dello stesso costo.
  • L'MST in generale è diverso dall'albero dei cammini minimi.

Algoritmi

Fonti: dispensa §4.3, Teorema 4.3.1, §4.3.2, appunti Lezione 9, §6-7, appunti Lezione 10, §6.