Cammini minimi e minimi alberi ricoprenti

[giuliomontenero]

Avrei bisogno del vostro aiuto per risolvere questo problema:
Fornire un grafo in cui un minimo albero ricoprente e albero dei cammini minimi (a partire da un certo vertice) coincidono. Fornire inoltre un grafo in cui minimo albero ricoprente e albero dei cammini minimi sono diversi.
Grazie mille in anticipo

[AndreaNobili1]

Il secondo è molto molto facile...direi banale...basta che prendi un grafo, ci butti dentro dei pesi a caso (magari alcuni coincidenti ed altri no) ed al 99% otterrai un grafo il cui MST (Minimum Spanning Tree) differisce dall'albero dei cammini minimi (trovare l'MST poi è molto semplice usando l'algoritmo di Kruskal o quello di Primm)

Per quanto riguarda il secondo caso, anche quà è abbastanza semplice.

Credo invece che l'MST coincide sempre con l'albero dei cammini minimi quando il grafo ha tutti archi di peso uguale (credo che questa proprietà valga in generale, ora non ho tempo per mettermi a cercare di dimostrarla però...)

Prendi il grafo G:

V= {A, B, C, D}

E= {(A,B); (A,D); (B,C); (B,D)} tutti di peso 1

T_cm = {(A,B); (A,D); (B,C)}

T_mst = {(A,B); (A,D); (B,C)}

Ciao
Andrea