cammini di peso minimo 1

[CuriousCI]

Sia $G$ un grafo non diretto, e sia $w : E(G) \to \mathbb{R}^+$ che associa ad ogni arco un peso. Sia $P$ un cammino di peso minimo tra due vertici $x, y \in V(G)$

Definiamo $w' : E(G) \to \mathbb{R}^+ : (u, v) \to w(u, v) + 1$

$P$ è ancora un cammino di peso minimo per $w'$? Giustificare la risposta.

[interestingmaneuver]

No, dipende dalla lunghezza (cioè, il numero di archi) del cammino minimo. Riporto un controesempio:

   1        1          1
x ---> (a) ----> (b) ------> (c)
|                             | 1
|                             v
---------------------------> (y)
             5            

Il cammino minimo ha lunghezza 4. Quel cammino non è più minimo aumentando i pesi:

   2        2          2
x ---> (a) ----> (b) ------> (c)
|                             | 2
|                             v
---------------------------> (y)
             6            

Da questo possiamo derivare anche uno spunto per trovare i cammini superminimi (cioè, peso minimo e lunghezza minima) con Dijkstra.

[interestingmaneuver]

Con il senno del n.2, riporto anche qui una prova formale:

Con abuso di notazione, definisco $w$ e $w'$ anche per i cammini:
$$w'(P) = \sum_{(u,v) \in P} w(u,v) + 1$$

Si vede subito che $w'(P) = w(P) + |P|$. Allora può esistere $P'$ per cui $w(P') + |P'| < w(P) + |P|$, basta appunto scegliere, anche con la stessa somma dei pesi secondo $w$, un cammino più corto.