← Volver a los ejercicios

Leer el enunciado y decidir por dónde se corta

El paso que más se salta es el segundo: decidir si lo que el enunciado quita o rompe es un vértice o una arista. Un enunciado que habla de destruir ciudades pide articulaciones; uno que habla de cortar cables o inundar carreteras pide puentes. Resolver el otro da una respuesta razonable que el juez rechaza. Aquí hay tres enunciados cortos y, en cada uno, cuatro decisiones.

Los cinco pasos

  1. Leer el grafo. Quiénes son los vértices y quiénes las aristas, y si viene dirigido o no.
  2. Decidir qué se corta. Un vértice pide el criterio de articulación; una arista, el de puente.
  3. Calcular con Tarjan. Una profundidad, d y low, en Θ(V+E).
  4. Contraer, si la pregunta no es local. Caminos, distancias o cuántos puentes se cruzan piden el árbol de puentes.
  5. Recorrer lo que quedó. Sobre el árbol, una profundidad o una amplitud más.

Enunciado

Para llevarse

Sin solución aquí. Reescriba el enunciado del dique cambiando una sola palabra, de modo que el corte pase a ser por vértice y la respuesta cambie. Después tome el del riego y agréguele una pregunta que obligue a llegar al paso 5 por un camino, no por un tamaño. Y por último: uno de los tres enunciados sigue teniendo la misma respuesta si el grafo llega con dos aristas entre el mismo par; diga cuál y por qué los otros dos no.