# TDA | Practica 4 ejercicio 2 ## Enunciado 2. $\star$Una arista de un grafo $G$ es puente si su remoción aumenta la cantidad de componentes conexas de $G.$ Sea $T$ un árbol DFS de un grafo conexo $G.$ a)Demostrar que $vw$ es un puente de $G$ si y solo si $vw$ no pertenece a ningún ciclo de $G.$ b) Demostrar que si $vw\in E(G)\setminus E(T)$, entonces $v$ es un ancestro de $w$ en $T$ o viceversa. c) Sea $vw\in E(G)$ una arista tal que el nivel de $v$ en $T$ es menor o igual al nivel de $w$ en $T.$ Demostrar que $vw$ es puente si y solo si $v$ es el padre de $w$ en $T$ y ninguna arista de $G\backslash\{vw\}$ une a un descendiente de $w$ (o a $w)$ con un ancestro de $v$ (o con $v).$ #### Aclaración: La 2da parte del ejercicio a, no me cierra. Preguntar a algún docente. Y también la 2da parte del ejercicio c tampoco me cierra. O sea las partes que son $\Leftarrow$) #### No pude pregunrar esto, de todas formas este ejercicio está hecho por un docente. ## Resolución ### a) - Quiero demostrar que $vw$ es un puente de $G \iff vw$ no pertenece a ningún [ciclo](https://apuntes.grunt.ar/s/vWkar1geI#Caminos-y-Ciclos) de $G$. - $\Rightarrow$) **Si $vw$ es un puente, entonces $vw$ no pertenece a ningún ciclo de $G$.** - Supongamos por el contrario que $vw$ es un puente y que $vw$ pertenece a un ciclo $G$. - Si $vw$ es parte de un ciclo, entonces existe al menos otro camino $G$ que conecta $v$ con $w$ sin utilizar la arista $vw$. - Si removemos la arista $vw$, los vertices $v$ y $w$ estarían conectados através de este otro camino. - Por lo tanto la eliminación de $vw$ no aumentaría el número de componentes conexas, contradiciendo la definición de puente. - Este absurdo muestra que si $vw$ es un puente $\Rightarrow$ no puede ser parte de ningún ciclo. - $\Leftarrow$) **Si $vw$ no pertenece a ningún ciclo de $G$, entonces $vw$ es un puente.** - Ahora supongamos que $vw$ no pertenece a ningún ciclo y que no es un puente. - Si no es un puente, la remoción (remoción significa remover) de $vw$ no debe afectar la conectividad del grafo, es decir, debe existir al menos un camino alternativo entre $v$ y $w$. - Esto implicaría que $vw$ es parte de un ciclo formado por este camino alternativo junto con $vw$, lo cual contradice nuestra suposición inicial que $vw$ no pertenece a ningún ciclo. - Esta contradicción implica que si $vw$ no pertenece a ningún ciclo, entonces debe pertenecer a un puente. Voy a desglosar un poco la demostración por si no se entiende del todo: 1. **Primera parte**: Si $vw$ es un puente, entonces $vw$ no pertenece a ningún ciclo de $G$. - Premisa: $vw$ es un puente, es decir su remoción aumenta la cantidad de componentes conexas del grafo $G$. - Suposición para la contradicción: $vw$ pertenece a un ciclo. - Consecuencia: si $vw$ **es parte de un ciclo**, entonces **si eliminamos esta arista**, los vertices $w$ y $v$ **permanecerían conectados a través de otros caminos que forman el inicio**, por lo tanto el grafo seguiría siendo conexo entre $v$ y $w$. - Contradicción: La suposición de que $vw$ es parte de un ciclo contradice la premisa de que es un puente. Pues al removerlo no debería mantener la conectividad entre $v$ y $w$ si realmente fuese un puente. 2. Segunda parte: Si $vw$ no pertenece a ningún ciclo de $G$, entonces $vw$ es un puente. - Premisa: $vw$ no pertenece a ningún ciclo - Suposición: $vw$ no es un puente. - Consecuencia de la suposición: Si $vw$ no es un puente, su eliminación no debería afectar a la conectividad, es decir que $v$ y $w$ deberían seguir conectados por otro camino **(no me gusta esto: preguntar si está bien)**. - Contradicción: Si existe otro camino conectando a $v$ y $w$ sin $vw$, entonces junto con $vw$ formarían un ciclo, lo cual contradice la premisa de que $vw$ no pertenece a ningún ciclo. ### b) - Sea $G$ un grafo conexo y $T$ un árbol DFS de G. Podemos suponer que la arista $vw$ de $G$ que no pertenece a $T$, es decir, $vw \in E(G)$ \ $E(T)$. - Como $T$ es un árbol de DFS, todo par de vértices en $G$ está conectado por un único camino en $T$. Sea $P$ el único camino en T, que conecta $v$ y $w$. - Ya que $vw$ no está en $T$, no puede ser parte del camino $P$. Esto implica que: - O bien $v$ está en el camino de la raíz de $T$ a $w$ (y entonces $v$ es un ancestro de $w$ en $T$). - O $w$ está en el cmaino de la raíz a $v$ (y entonces $w$ es un ancesetro de v en $T$). - Por lo tanto, si $vw \in$ $E(G)$ \ $E(T)$, entonces $v$ es un ancestro de $w$ en $T$ o viceversa. ### Conclusión: - Como $T$ es un árbol DFS que contiene un único camino entre cualquier par de vértices, si una arista $vw$ está en $G$ pero no en $T$, uno de sus extremos debe ser ancestro del otro en $T$. ### c) - Sea $vw\in E(G)$ una arista tal que el nivel de $v$ en $T$ es menor o igual al nivel de $w$ en $T.$ Demostrar que $vw$ es puente si y solo si $v$ es el padre de $w$ en $T$ y ninguna arista de $G\backslash\{vw\}$ une a un descendiente de $w$ (o a $w)$ con un ancestro de $v$ (o con $v).$ - $vw$ es puente $\iff$ el vertice $v$ es el padre de $w$ en $T$ y ninguna arista de $G\backslash\{vw\}$ - $\Rightarrow$) si $vw$ **es puente** $\Rightarrow$ $v$ es el padre de $w$ en $T$ y no existe tal arista en $G\backslash\{vw\}$ - Voy a ir probando esto por el absurdo, porque es la demostración que me siento más comodo: - Suposición: $vw$ es un puente de $G$ - Suposición para el absurdo: Voy a asumir que $v$ **NO** es padre de $w$ en $T$, o existe una arista en $G\backslash\{vw\}$ - si $v$ no es el padre de $w$ en $T$ entonces $vw$ no es una arista del árbol DFS, lo que implica que es una backward edge. - **Sí existe otra arista como la que describí, entonces se formaría un ciclo** o un camino alternativo que **mantendria a los vertices $v$ y $w$ como una componente conexa**, incluso tras remover la arista $vw$. - Pero esto **contradice** la afirmación de que $vw$ es un puente, ya que la definición de puente requiere que su eliminación aumente el número de componentes conexas. - $\Leftarrow$) el vertice $v$ es el padre de $w$ en $T$ y ninguna arista de $G\backslash\{vw\} \Rightarrow vw$ es un puente. - Lo mismo, utilizo el absurdo. - Supongo que $v$ es el padre de $w$ en $T$ y no existe ninguna arista en $G\backslash\{vw\}$ que conecte un descendiente $w$ con un ancestro de $v$ - Asumo que $vw$ **NO** es un puente. - Si $vw$ no es un puente, entonces su remoción no debería afectar la conectividad del grafo, lo que implica que debe habver otro camino conectado a $v$ y $w$: - Si la arista $vw$ no es un puente, entonces la eliminación de $vw$ no debe aumentar el número de componentes conexas al grafo. - Esto implica que $v$ y $w$ todavía deben permanecer en la misma componente conexa después de eliminar $vw$. - Y para que $v$ y $w$ permanezcan en al misma componente conexa sin la arista $vw$, debe existir al menos un camino alternativo que los conecte. Es independiente de la arista vw y asegura que la eliminación de $vw$ no descomponga el grafo en componentes más pequeños. -  - Ejemplo $\uparrow$ - Volviendo al ejercicio: Esto es una contradicción, dado que no hay otras aristas que conecten descendientes de $w$ con ancestros de $v$. - La unica conexión entre $v$ y $w$ es la arista $vw$. - Esto contracice la suposición de que $vw$ no es un puente. - Por lo tanto $vw$ es un puente $\iff v$ es el padre de $w$ en $T$ y no existe una arista en $G\backslash\{vw\}$ que conecte a un descendiente de $w$ con un ancestro de $v$.