Albero di copertura a costo minimo Flashcards
Descrivi il problema MST.
Dato un grafo non orientato, è il problema della determinazione di un albero di copertura tale che sia minimo il costo di T. Il costo di T sarà la somma del costo di tutti i suoi archi.
Come funziona un algoritmo greedy per MST?
Costruisce l’albero incrementalmente, mantenendo ad ogni passo due insiemi di archi, l’insieme degli archi inseriti e quello degli archi rimossi. Questi vengono aggiornati attraverso operazioni di inserzione e rimozione.
Cos’è un albero di copertura di costo minimo?
E’ un sottografo connesso, privo di cicli, di costo minimo.
Cosa è un taglio?
E’ la partizione in 2 insiemi dell’insieme di tutti i nodi.
Cos’è l’insieme degli archi in un taglio?
E’ l’insieme degli archi del grafo che collegano un nodo che è da una parte del taglio, e un nodo che è dall’altra parte.
Descrivi la proprietà di ottimalità per cicli
Un grafo è un albero di copertura di costo minimo se il costo di ogni arco non appartenente all’albero è maggiore o uguale al costo di ciascun arco del ciclo che si viene a creare aggiungendo (i, j) all’albero.
Descrivi la proprietà di ottimalità per tagli
Un grafo è un albero di copertura di costo minimo se il costo di ciascun arco appartenente all’albero è minore o uguale al costo di ciascun arco del taglio che si viene a creare rimuovendolo dall’albero.
Descrivi l’algoritmo di Kruskal
Si ordinano gli archi per costo non decrescente (crescente)
Si esaminano gli archi in quell’ordine.
Se l’arco non forma un ciclo con S, si aggiunge ad
S, altrimenti si aggiunge ad R.
Descrivi l’algoritmo di Prim
Ad ogni iterazione si costruisce e si aggiorna un taglio tale che una parte del taglio è un albero di copertura a costo minimo. Ogni iterazione si inserisce un arco in modo da mantenere la proprietà di ottimalità per tagli, infatti si sceglie l’arco di costo minimo tra quelli del taglio.
