PUERTA | PUERTA CS 2021 | Conjunto 1 | Pregunta 51

Un punto de articulación en un grafo conectado es un vértice tal que al eliminar el vértice y sus bordes incidentes, el grafo se desconecta en dos o más componentes conectados.

Sea T un árbol DFS obtenido al hacer DFS en un grafo G no dirigido conexo.

¿Cuál de las siguientes opciones es/son correctas?
(A) La raíz de T nunca puede ser un punto de articulación en G.
(B) La raíz de T es un punto de articulación en G si y solo si tiene 2 o más hijos.
(C) Una hoja de T puede ser un punto de articulación en G.
(D) Si u es un punto de articulación en G tal que x es un ancestro de u en T y y es un descendiente de u en T, entonces todos los caminos desde x a y en G debe pasar por u.

Respuesta: (B) (D)
Explicación: ¿Cómo encontrar todos los puntos de articulación? 
Enfoque basado en DFS : 
Podemos probar las siguientes propiedades: 
 

• La raíz de un árbol DFS es un punto de articulación si y solo si tiene al menos dos hijos. 
   
• Las hojas de un árbol DFS nunca son puntos de articulación.
   

D no es cierto porque no es necesario tener un camino solo a través del punto de articulación. También puede haber un camino directo de x a y en un gráfico G.

Cuestionario de esta pregunta