Esercizio 5.2.4

0 passi visti su 3

Consegna

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

Apri in Kruskal
0Ordinamento degli archiapri

[1,2][1,2] 1, [2,4][2,4] 1, [2,6][2,6] 1, [5,7][5,7] 1, [1,7][1,7] 2, [1,4][1,4] 3, [4,5][4,5] 3, [1,6][1,6] 4, [2,3][2,3] 5, [3,6][3,6] 5, [4,7][4,7] 5, [2,5][2,5] 6, [3,5][3,5] 9.

1Kruskalapri
hhArcoCostoC[i]C[i] e C[j]C[j]DecisioneWtotW_{\mathrm{tot}}CC dopo
1[1,2][1,2]11 ≠ 2preso1(1, 1, 3, 4, 5, 6, 7)
2[2,4][2,4]11 ≠ 4preso2(1, 1, 3, 1, 5, 6, 7)
3[2,6][2,6]11 ≠ 6preso3(1, 1, 3, 1, 5, 1, 7)
4[5,7][5,7]15 ≠ 7preso4(1, 1, 3, 1, 5, 1, 5)
5[1,7][1,7]21 ≠ 5preso6(1, 1, 3, 1, 1, 1, 1)
6[1,4][1,4]31 = 1scartato6(1, 1, 3, 1, 1, 1, 1)
7[4,5][4,5]31 = 1scartato6(1, 1, 3, 1, 1, 1, 1)
8[1,6][1,6]41 = 1scartato6(1, 1, 3, 1, 1, 1, 1)
9[2,3][2,3]51 ≠ 3preso11(1, 1, 1, 1, 1, 1, 1)
2Soluzioneapri

L'albero è formato da [1,2][1,2], [2,4][2,4], [2,6][2,6], [5,7][5,7], [1,7][1,7] e [2,3][2,3], con costo 11. Scegliendo [3,6][3,6] al posto di [2,3][2,3], che costa uguale, si ottiene un secondo albero ottimo.