# TDA | Practica 4 ejercicio 16 ## Enunciado 16. Un grafo $G$ es un cactus cuando cada una de sus aristas pertenece a un único ciclo $a)$ Sea $T$ un árbol DFS de un grafo $G$ y sea $T(v,w)$ el unico camino entre $v$ y $w$ en $T$ para todo $v,w\in V(G).$ Demostrar que $G$ es un cactus si y solo si para toda arista $vw\in E(G)\setminus E(T)$ ocurre que $T(v,w)+vw$ es el único ciclo que contiene a las aristas en $T(v,w).$ $b)$ Demostrar que los grafos cactus tienen $O(n)$ aristas. $c)$ Diseñar un algoritmo de tiempo $O(n)$ para determinar si un grafo es un cactus. En caso afirmativo, el algoritmo debe retornar todos los ciclos del grafo. En caso negativo, el algortimo debe retornar dos ciclos que compartan una arista. $d) \text{ Dise\~{n} ar un algoritmo de tiempo }O( n) \text{ para encontrar un \'{a} rbol generador m\'{ı } nimo de un}$ grafo cactus. Justificar que el algoritmo es correcto utilizando resultados conocidos. $e)$ Proponer una formula para contar la cantidad de árboles generadores mínimos de un grafo cactus que pueda ser computada en $O(n)$ operaciones de suma y multiplicación. Demostrar que la fórmula es correcta. ## Resolución ### a) - "$G$ es un cactus" $\equiv A$ - "Para toda arista $vw \in E(G) \setminus E(T)$ ocurre que $T(v,w)+vw$ es el único ciclo que contiene a las aristas $T(v,w)$" $\equiv B$ - quiero demostrar que: $A \iff B$ - Divido la demostración en partes: - $\Rightarrow)$ Quiero probar que $A \Rightarrow$ $B$, asumo $A$ verdadero - $\Leftarrow$) Quiero probar que $B \Rightarrow$ $A$, asumo $B$ verdadero - $\Rightarrow)$ $G$ es un cactus, entonces Para toda arista $vw \in E(G) \setminus E(T)$ ocurre que $T(v,w)+vw$ es el único ciclo que contiene a las aristas $T(v,w)$ - Recordemos la definición de cactus: cuando cada una de sus aristas pertenece a un único ciclo. - Entonces nosotros sabemos que $vw$ va a pertenecer a un ciclo. - Nos dicen que $vw$ que pertenece a las aristas del Grafo, pero que no pertenece a las aristas del arbol DFS. - y que $T(v,w) + vw$ representa el ciclo formado por el camino unico $T(v,w)$ en el arbol DFS y que la arista $vw$ no está en el arbol, pero si en el grafo original. - Tomando de nuevo la demostración, el unico ciclo que puede formarse con $vw$ es el camino único $T(v,w)$ en $T$ y la arista $vw$. - Entonces el ciclo que forma $T(v,w)+vw$ es el único ciclo que va a contener la arista $vw$ y todas las aristas en $T(v,w)$ que no están en ningún otro lado. - $\Leftarrow$) Para toda arista $vw \in E(G) \setminus E(T)$ ocurre que $T(v,w)+vw$ es el único ciclo que contiene a las aristas $T(v,w)$ Entonces $G$ es un cactus. - Podemos suponer que $G$ no es un cactus, es decir que: - Existe al menos una arista en $G$ que pertenece a más de un ciclo simple. - entonces esto nos diría que $vw, T(v,w)$ sería al menos parte de dos ciclos diferentes. - Pero la proposición $B$ nos dice que solo puede aparecer en el ciclo $T(v,w)+vw$. - Y entonces la existencia de una arista en más de un ciclo contradice la suposición de que $T(v,w)+vw$ es el UNICO ciclo que contiene esas aristas. - Por lo tanto por el absurdo $G$, debe ser un cactus. $\square$