[Algoritmi] Arco peso minimo in particolare grafo

[AndreaNobili1]

Ciao,
se io ho un grafo G: CONNESSO, NON DIRETTO, PESATO ed avente la proprietà di avere ogni arco con un peso diverso (quindi una funzione peso w: E ---> R che per ogni coppia di archi e1,e2 vale che w(e1) != w(e2) )

Se partendo da un qualsisi nodo r costruisco il suo ALBERO DEI CAMMINIMI MINIMI T.

Posso dire che in un grafo con tale proprietà (di avere ogni arco con un peso diverso dagli altri) vale che sicuramente l'arco di peso minimo appartiene sempre a qualsiasi albero dei cammini minimi T?

Secondo me si...perchè in maniera piuttosto informale posso dire che nel problema del single source shortest path in genere ho un algoritmo (tipo Dijkstra) in cui ad ogni iterazione amplio una soluzione parziale X per cui è vera la proprietà che tutti i cammini all'interno di tale soluzione parziale sono minimi e rimarrano minimi...

Per cui mi viene da pensare che in qualche modo l'arco di peso minimo (visto che è univoco) deve essere per forza incluso nella soluzione parziale ad un certo punto perchè è quello che mi "alzerà meno" il potenziale verso un altro nodo che non è ancora nella soluzione parziale (o me lo abbasserà di più nel caso di archi di peso negativo...)

E visto che tale arco è sicuramente unico (in quanto tutti gli archi hanno peso diverso) sarà sicuramente lui (e non un altro di uguale peso che non può esistere) ad essere inserito nella soluzione parziale

Ci può stare come ragionamento o no?

Qualche idea per dimostrarlo (qualora fosse effettivamente così e non stessi prendendo una cantonata) in maniera un pochino più formale?

Grazie mille
Andrea

[apatriarca]

Siccome nell'[url=http://en.wikipedia.org/wiki/Kruskal's_algorithm]algoritmo di Kruskal[/url], che permette di trovare il minimum spanning tree, unico in questo caso, vengono scelti uno dopo l'altro gli archi a partire da quello di costo minimo, allora è certo che quell'arco farà certamente parte del minimum spanning tree.

[AndreaNobili1]

"apatriarca":Siccome nell'[url=http://en.wikipedia.org/wiki/Kruskal's_algorithm]algoritmo di Kruskal[/url], che permette di trovare il minimum spanning tree, unico in questo caso, vengono scelti uno dopo l'altro gli archi a partire da quello di costo minimo, allora è certo che quell'arco farà certamente parte del minimum spanning tree.

mmm no forse non hai capito bene cosa intendevo io...non parlavo dell'MST ma dell'albero dei cammini minimi...quindi non si parla di Kruskal ma eventualmente di Dijkstra et similia...si parla del problema dei cammini minimi e non del minimo albero coprente (risolto appunto da Kruskal)

Ovviamente l'arco di costo minimo fà parte di un albero MST

La mia domanda è un'altra: preso un grafo G ed un nodo sorgente s (qualsiasi). Posso dire che l'albero dei cammini minimi a partire da s verso tutti gli altri nodi (ad esempio costruito usando Dijkstra) contiene sicuramente l'arco di peso minimo del grafo?

Facendo un po' di prove ed usando il ragionamento esposto prima mi sembrerebbe di si ma potrei aver ragionato male e comunque anche se avessi ragionato bene non credo che tale ragionamento sia sufficientemente formale

Grazie
Andrea

[apatriarca]

In tal caso allora no, non è detto. Considera per esempio il grafo con nodi \(A\), \(B\), \(C\) e \(D\) e archi \((A, B, 1000)\), \((A, C, 100)\), \((B, D, 1)\) e \((C, D, 200)\). Consideriamo quindi \(A\) come nodo di partenza. In questo caso, l'arco tra \(B\) e \(D\) non sarà contenuto nell'albero dei cammini minimi perché per passare da quell'arco è necessario passare da un arco di costo altissimo e conviene fare invece il percorso \(A \to C \to D\). Nota che se fosse come dici tu, l'albero di cammini minimi sarebbe in pratica l'MST..

[AndreaNobili1]

"apatriarca":In tal caso allora no, non è detto. Considera per esempio il grafo con nodi \(A\), \(B\), \(C\) e \(D\) e archi \((A, B, 1000)\), \((A, C, 100)\), \((B, D, 1)\) e \((C, D, 200)\). Consideriamo quindi \(A\) come nodo di partenza. In questo caso, l'arco tra \(B\) e \(D\) non sarà contenuto nell'albero dei cammini minimi perché per passare da quell'arco è necessario passare da un arco di costo altissimo e conviene fare invece il percorso \(A \to C \to D\). Nota che se fosse come dici tu, l'albero di cammini minimi sarebbe in pratica l'MST..

Cacchiarella hai proprio ragione...ed oltre a sentirmi scemo questa cosa mi fà cadere nello sconforto perchè pensavo di aver risolto un esercizio in maniera diversa ma corretta da quella proposta dal proff...

Sostanzialmente l'esercizio chiedeva di dimostrare la proprietà per cui dato un grafo G avente tutti gli archi con pesi diversi, allora un MST ed un qualsiasi albero dei cammini minimi (quindi a partire da un qualsiasi nodo r di V) hanno sempre in comune almeno un arco e

Il mio ragionamento era il seguente: L'MST è UNICO in quanto ha tutti pesi diversi. Per lo stesso motivo l'arco di peso minimo dell'MST è univocamente determinato.

Se riesco a dimostare che tale arco è presente anche in un qualsiasi T=(albero dei cammini minimi a partire da r) allora la proprietà è dimostrata

E invece no...il ragionamento corretto a quanto pare dovrebbe essere il seguente:

Prendo l'arco e=(r,x): ARCO DELL'ALBERO DEI CAMMINI MINIMI INCIDENTE IN r E DI COSTO MINIMO
Tale arco è univocamente determinato perchè per ipotesi tutti gli archi hanno pesi diversi tra loro

Adesso devo dimostrare che tale arco e=(r,x) appartiene anche all'MST...a questo punto faccio partire l'algoritmo di Prim dal nodo r ed essendo e l'arco di costo minimo incidente in r sarà sicuramente scelto e quindi apparterrebbe ad un MST (sicuramente all'MST generato usando Prim partendo da r)

Non ci avrei mai pensato...sigh...

Grazie mille della tua spiegazione

Ciao
Andrea