Sia dato un grafo non orientato e connesso
con nodi ed archi.
Si assuma che ad ogni arco di sia associato
un peso .
Si assuma per semplicità che i pesi siano degli interi
non negativi.
Vogliamo trovare un sottografo connesso di
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.