# TDA | Practica 4 Ejercicio 5 ## Consigna - Un arbol generador $T$ de un grafo $G$ es $v$-geodesico si la distancia entre $v$ y $w$ en $T$ es igual a la distancia entre $v$ y $w$ en $G$ para todo $w\in V( G)$. - **Demostrar que todo arbol BFS de $G$ enraizado en $v$ es $v$-geodesico.** - Dar un contra-ejemplo para la vuelta, i. e. , mostrar un arbol generador $v$-geodésico de un grafo $G$ que no pueda ser obtenido cuando BFS se ejecuta en $G$ desde $v.$ ## Resolución ### Una forma más adecuada de probar esto es por inducción. - Todo arbol de $G$ enraizado en $v$ es $v$-geodesico - Todo arbol $G$ enraizado en $v \equiv$ $A$ - $v$-geodesico $\equiv$ $B$ - $A \Rightarrow B \ \land \ A \nLeftarrow \ B$ - Sabemos que BFS explora los vertices más superficiales antes de pasar al siguiente, garantizando que se encuentran las rutas más cortas desde el vertice de inicio. O sea que **por definición BFS va a encontrar la ruta mas corta entre vertices**. - **Definición Geodésico**: Un camino geodésico en un grafo es el camino más corto entre dos vértices. Este concepto es fundamental al considerar árboles generadores, pues ellos buscan mantener la mínima distancia entre los vértices. - Para cada vertice $w$, BFS lo visita por primera vez a través del camino más corto posible desde $v$ pues: - Todos los vértices con distancia $k$ desde $v$, son explorados antes de visitar cualquier vértice de nivel $k+1$. - Y esto garantiza que siempre la primera vez que un vertice $w$ sea visitado por BFS, es a través del camino más corto desde $v$. - Cualquier otro camino más largo hubiese implicado visitar algún vértice en un nivel más profundo antes de visitar todos los vértices en los niveles anteriores. - Construcción: - Empezá en el vértice $v$ y asumo que todos los otros vertices están por defecto marcados como no visitados excepto $v$. - Inicializo una cola e inserto $v$. - Mientras que la cola no esté vacía: - Extraé el primer vértice de la cola (lo llamamos $u$). - Y para cada vecino $w$ de $u$ que no haya sido visitado: - marcá $w$ como visitado, - Añadilo a la cola, - Conectá $u$ con $w$ en el arbol BFS (mediante una arista). - Cada vez que $w$ es visitado y añadido a $T$, el camino desde $v$ a $w$ en $T$ es establecido por la primera ruta encontrada por BFS. - Entonces como BFS explora todos los v ecinos de un vértice antes de pasar a los vértices en el siguiente nivel de profunidad, entonces nos asegura que $w$ se visita por la ruta más corta posible desde $v$. - Cualquier camino alternativo a $w$ desde $v$ que pase por vertices no visitados va a tener que ser más largo. - Ejemplo contextual: -  - Por lo tanto todos los caminos en el árbol BFS $T$ esde $v$ hasta cualquier otro ertice $w$, son las distancias más cortas en el grafo $G$, y esto justamente cumple la definición de $v$-geodesico. #### Ahora $A \nLeftarrow \ B$ - Contraejemplo: - Un contraEjemplo sería cualquier grafo v-geodesico que no sea un arbol $G$ enraizado en $v$ -