In un vecchio edificio ci sono 10 computer che devono essere collegati in rete.
Dato l’elevato spessore delle pareti, non è possibile usare una rete wifi e si decide, quindi, di collegarli via cavo.
Non sono possibili tutti i collegamenti, e ogni collegamento ha un costo diverso.
Si deve aiutare a progettare la rete scegliendo i nove collegamenti necessari per fare in modo che ogni computer sia collegato alla rete (ovvero ad almeno un altro computer) e che il costo complessivo sia minimo.
Dopo che i nove collegamenti saranno stati scelti, indicare il costo totale TOTCOSTO, pari alla somma dei costi dei nove collegamenti selezionati.
Per collegare i 10 computer sono necessari 9 collegamenti.
Ordina i costi dei collegamenti in ordine crescente: 3 – 4 – 5 – 6 – 7 – 9 – 11 – 13 – 15 – 16 – 22 – 31 – 33 – 37.
Utilizzando i primi 9° collegamenti (3 – 4 – 5 – 6 – 7 – 9 – 11 – 13 – 15 – 16 – 22 – 31 – 33 – 37) si ottiene lo schema seguente
Il costo totale è minimo (80) ma il computer J non è collegato.
Tra i collegamenti disponibili per J scegli quello con il costo più basso (22).
Tra i collegamenti precedenti è possibile eliminare quello con costo 7 senza isolare alcun computer
Utilizzando i collegamenti con costo 3 – 4 – 5 – 6 – 7 – 9 – 11 – 13 – 15 – 16 – 22 – 31 – 33 – 37 si ottiene la soluzione con costo 88.
Perché il costo complessivo è minimo?