Pages: [1]   Go Down
Print
Author Topic: Esercizio Cammini Minimi  (Read 1506 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
EL TIBURON
Matricola
*
Offline Offline

Gender: Male
Posts: 90



« on: 07-02-2009, 15:26:01 »

Il seguente esercizio come l'avete risolto?:

(b) Si dimostri che un arco (u, v) ∈ E ` presente in G′  (grafo dei cammini minimi in G da sorgente s) se e solo se
      δ(s, u) + w(u, v) = δ(s, v).
                                       e              s
(c) Siano w1 : E −→ R+ e w2 : E −→ R+ due funzioni peso su G e siano δ1 e δ2 le relative funzioni-distanza indotte.
    Si illustri un algoritmo efficiente per la costruzione di un albero dei cammini da s in G che risultino simultaneamente
    minimi rispetto a δ1 e a δ2 .


Grazie
Logged

Eres lo que quieres ser.
Domenico Cantone
Moderator
Apprendista Forumista
*****
Offline Offline

Gender: Male
Posts: 345



« Reply #1 on: 07-02-2009, 16:51:44 »

(b) Si dimostri che un arco (u, v) ∈ E è presente in G′  (grafo dei cammini minimi in G da sorgente s) se e solo se
      δ(s, u) + w(u, v) = δ(s, v).

Se l'arco (u, v) ∈ E è presente in G′ allora esiste un cammino minimo π da s che lo contiene (per definizione).
Siano πu e πv i sottocammini di π da s a u e a v, rispettivamente. Tali cammini sono minimi.
Quindi, w(πu) =  δ(s, u) e w(πv) = δ(s, v).
Ma w(πv) = w(πu) + w(u, v), da cui δ(s, u) + w(u, v) = δ(s, v).
Viceversa ...


(c) Siano w1 : E −→ R+ e w2 : E −→ R+ due funzioni peso su G e siano δ1 e δ2 le relative funzioni-distanza indotte.
    Si illustri un algoritmo efficiente per la costruzione di un albero dei cammini da s in G che risultino simultaneamente
    minimi rispetto a δ1 e a δ2 .

- Si applichi l'algoritmo di Dijkstra al grafo G, prima con la funzione peso w1 e poi con w2, ottenendo le distanze δ1 e δ2.
- Sia E" l'insieme di tutti gli archi (u,v) di G tali che
    • δ1(s, u) + w1(u, v) = δ1(s, v)
    • δ2(s, u) + w2(u, v) = δ2(s, v)
- Si effettui una visita (ad es. in profondità) da s del grafo G"(V,E").
- L'albero generato da tale visita risulta essere un albero dei cammini minimi da s in G simultaneamente
    minimi rispetto a δ1 e a δ2 .

Infatti ...
« Last Edit: 07-02-2009, 19:07:16 by Domenico Cantone » Logged
EL TIBURON
Matricola
*
Offline Offline

Gender: Male
Posts: 90



« Reply #2 on: 07-02-2009, 19:03:47 »

grazie mille professore.
Logged

Eres lo que quieres ser.
Pages: [1]   Go Up
Print
Jump to: