← Volver a los ejercicios

La comparación que decide

Cada escenario es un grafo recorrido en profundidad desde el 0, con los vecinos de menor a mayor. Se da un vértice u y uno de sus hijos v en el árbol, junto con los números que el código tiene a la mano al volver de v. Hay que decidir si el hijo hace de u un punto de articulación y si la arista u–v es un puente. Cada respuesta equivocada explica qué comparación se hizo mal.

Escenario

Azul: aristas del árbol. Verde punteado: aristas de retroceso. Sobre cada vértice, su d.
¿La arista (u, v) es un puente?

Para llevarse

Sin solución aquí. Hay un escenario donde un vértice es punto de articulación y el hijo que se pregunta no es el motivo. Encuéntrelo y diga cuál hijo sí lo es. Después construya un grafo no dirigido donde una raíz de grado 3 no sea punto de articulación, y diga cuántos hijos tiene en el árbol.