Supongamos que G es un grafo no dirigido. Cómo puedo encontrar de forma eficiente todas las aristas de G que forman parte de un camino simple entre los vértices A y B dados?
Respuesta
¿Demasiados anuncios?
Sea $a,b \in V(G)$ y $e \in E(G)$ . Entonces $e$ está en algún camino desde $a$ a $b$ en $G$ sólo si $a$ , $b$ y $e$ están en el mismo componente en $G$ y $e$ está en un componente biconexo que se encuentra en el único camino desde el componente biconexo que contiene a $a$ al componente biconexo que contiene $b$ en el árbol de bloques para $G$ .
Prueba : Supongamos que $a$ , $b$ y $e$ están en el mismo componente en $G$ y $e$ está en un componente biconexo $B_e$ que está en el único camino desde el componente biconexo $B_a$ que contiene $a$ al componente biconexo $B_b$ que contiene $b$ en el árbol de bloques para $G$ . Si $B_a \neq B_e$ encontrar un camino $P_a$ en $G$ internamente disjuntos de $B_e$ de $a$ a un vértice $a'$ en $B_e$ . Si $B_a = B_e$ , dejemos que $a' = a$ y $P_a = a$ . Del mismo modo, si $B_b \neq B_e$ encontrar un camino $P_b$ en $G$ internamente disjuntos de $B_e$ de $b$ a un vértice $b'$ en $B_e$ . Si $B_b = B_e$ , dejemos que $b' = b$ y $P_b = b$ . Ahora bien $e = a'b'$ entonces $P_a \cup e \cup P_b$ es una ruta desde $a$ a $b$ en $G$ . Si $e$ es incidente con $a'$ o $b'$ entonces por el teorema de Menger encontrar dos caminos disjuntos en $B_e$ de los extremos de $e$ a cualquiera de $a'$ o $b'$ no es incidente con $e$ entonces uno de estos caminos junto con $e$ , $P_a$ y $P_b$ es una ruta desde $a$ a $b$ que contiene $e$ . Por último, si ninguno de los dos $a'$ ni $b'$ son extremos de $e$ por el Teorema de Menger, hay dos caminos disjuntos en $B_e$ de $a'$ y $b'$ a los extremos de $e$ y estas dos vías junto con $e$ , $P_a$ y $P_b$ es una ruta desde $a$ a $b$ que contiene $e$ .
Por el contrario, si $e$ no está en el mismo componente que $a$ y $b$ está claro que no hay camino desde $a$ a $b$ que contiene $e$ y si $B_e$ no está en la ruta del árbol de bloques para $G$ de $B_a$ a $B_b$ no puede haber un camino desde $a$ a $e$ que sea disjunta de un camino desde $b$ a $e$ y, por tanto, no puede haber un camino desde $a$ a $b$ que contiene $e$ . $\Box$
Véase, por ejemplo, este para las definiciones, y también un algoritmo que determina los componentes biconexos en tiempo lineal. Usando este resultado y ese algoritmo, debería ser posible encontrar todas esas aristas en tiempo lineal.
