Esta es una tarea de un examen antiguo que estoy haciendo para aprender:
Sea $G$ un Digrafo con pesos de arista conservativos $c: E(G) \rightarrow \mathbb{R}$. Sea $T$ un árbol generador con raíz $s$. Demuestra que lo siguiente es equivalente:
- $T$ es un árbol de camino más corto con raíz $s$ en $G$
- Para cada arista $(x,y) \in E(G)$ se cumple que: $\text{dist}_T(s,y) \leq \text{dist}_T(s,x) + c((x,y))\quad\quad\quad(I)$
Mi demostración es:
$1. \Rightarrow 2.$ es trivial. Así que vamos a demostrar la otra implicación.
Debemos demostrar: $\forall y\in V(G): \text{dist}_T(s,y) = \text{dist}_G(s,y) \quad\quad\quad(II)$. Ahora elijamos un $y$ tal.
Supongamos que $\text{dist}_G(s,y)$ es dada por un camino $P$ en $G$, es decir: $\sum_{e \in P(E)}c(e) = \text{dist}_G(s,y)$.
Ahora utilizamos un argumento inductivo sobre la longitud de los caminos $n = |V(P)|$.
Para $n=0$ es trivial que $(II)$ es verdadero ya que las distancias son $0$.
Ahora supongamos que es cierto para $|V(P)| = n$. Sea $|V(P)| = n+1$. Ahora simplemente podemos definir $P'$ como $(v_1,...,v_n)$ con $P = (v_1,...,v_{n+1})$ con $v_{n+1} = y$, por lo que simplemente "quitamos" el último vértice y también la arista correspondiente, sea $e$. Ahora podemos usar la inducción en $P'$ y $v_n$ en lugar de $y$.
Así obtenemos $\text{dist}_T(s,v_n) = \text{dist}_G(s,v_n)$. A partir de aquí, simplemente podemos usar $(I)$ y obtener:
$\text{dist}_T(s,y) \leq \text{dist}_T(s,v_n) + c(e) = \text{dist}_G(s,v_n) + c(e) = \text{dist}_G(s,y)$.
Eso es todo lo que necesitábamos.
¿Está correcto?
Me parece un poco demasiado fácil. Y no estoy utilizando que los pesos sean conservativos. Pero sin usar esto, tendríamos (si hay un ciclo negativo) un camino de longitud negativa infinita. Supongo que tengo que usar esto en la inducción, pero la inducción me parece correcta de todos modos.
