next up previous
Next: Esercizio 5 (7*) Up: Secondo Scritto - ASD1 Previous: Esercizio 3 (***)

Esercizio 4 (15*)

Sia dato un grafo non orientato e connesso $ G$ con $ n$ nodi ed $ m$ archi. Si assuma che ad ogni arco $ e$ di $ G$ sia associato un peso $ w_e$. Si assuma per semplicità che i pesi siano degli interi non negativi. Vogliamo trovare un sottografo connesso di $ G$ per cui sia minima la somma dei pesi degli archi in esso contenuti.

(*) Si dimostri come sia sempre possibile assumere che tale sottografo sia aciclico, ossia sia un albero.
(**) Descrivere un qualsiasi algoritmo polinomiale per il problema dell'albero di copertura minimo testè introdotto. (*****) Argomentarne la correttezza. (*) Analizzarne la complessità. (***) Dare un algoritmo lineare per lo stesso problema nel caso in cui tutti i pesi siano o degli 1 o dei 2. (***) Dimostrarne la correttezza.



Romeo Rizzi 2003-04-14