Alberi ricoprenti di costo minimo¶

2.1 Il problema dell'albero di copertura minimo

Apri
2.2 Tagli e cicli

Apri
2.3 La proprietà di taglio e la proprietà di ciclo

Apri
2.4 L'algoritmo greedy generico

Apri
2.5 Algoritmo di Kruskal

Algoritmo di Kruskal sul grafo di riferimento

Apri
2.6 Algoritmo di Prim

Apri
2.7 Unicità dell'albero di copertura minimo

Pesi con valori di parità

Apri

Prerequisiti

Il capitolo «Grafi»: percorsi e cicli, componenti connesse, le caratterizzazioni di un albero e i cicli fondamentali.
La notazione \(O(\cdot)\) per il tempo di esecuzione di un algoritmo e l'ordinamento dei numeri \(m\) nel tempo \(O(m\log m)\).

Obiettivi

Alla fine di questo capitolo sarai in grado di:

indica il problema dell'albero ricoprente minimo e lo riconosce nelle applicazioni;
dimostrare la proprietà di taglio e la proprietà di ciclo e utilizzarle per certificare che uno albero ricoprente è ottimale;
esegue gli algoritmi di Kruskal e di Prim, dimostra che sono corretti e analizza il loro tempo di esecuzione;
decide se l'albero ricoprente minimo è unico e trova gli archi che appartengono a ogni albero ottimale.

Avanti: 2.1 Il problema dell'albero di copertura minimo

Esercizi su questo capitolo: Alberi ricoprenti