Esercizio 5.2.2

0 passi visti su 3

Consegna

Dato il grafo non orientato G=(V,E)G = (V, E) con archi [1,2][1,2] 9, [1,4][1,4] 5, [2,3][2,3] 5, [2,4][2,4] 1, [2,5][2,5] 6, [3,5][3,5] 9, [4,5][4,5] 3 (Figura 5.1 della dispensa), se ne determini l'albero di copertura di costo totale minimo.

Apri in Kruskal
0Ordinamento degli archiapri

Per costo non decrescente e, a parità, per coppia di indici: [2,4][2,4] 1, [4,5][4,5] 3, [1,4][1,4] 5, [2,3][2,3] 5, [2,5][2,5] 6, [1,2][1,2] 9, [3,5][3,5] 9. All'inizio C=(1,2,3,4,5)C = (1, 2, 3, 4, 5).

1Kruskalapri
hhArcoCostoC[i]C[i] e C[j]C[j]DecisioneWtotW_{\mathrm{tot}}CC dopo
1[2,4][2,4]12 ≠ 4preso1(1, 2, 3, 2, 5)
2[4,5][4,5]32 ≠ 5preso4(1, 2, 3, 2, 2)
3[1,4][1,4]51 ≠ 2preso9(1, 1, 3, 1, 1)
4[2,3][2,3]51 ≠ 3preso14(1, 1, 1, 1, 1)

Con il quarto arco preso, cioè n−1n - 1, ci si ferma.

2Soluzioneapri

L'albero è formato da [2,4][2,4], [4,5][4,5], [1,4][1,4] e [2,3][2,3], con costo 14.