← Volver a los ejercicios

Conexo, débil o fuerte

Cinco grafos, dos sin dirección y tres con ella, y la misma pregunta en las dos versiones: ¿se puede ir de cualquier vértice a cualquier otro? Con las aristas sin punta hay una respuesta; con punta hay que preguntar de ida y de vuelta, y las dos no tienen por qué coincidir.

1. El grafo

2. Clasifíquelo

Dos de las cinco opciones solo tienen sentido en grafos no dirigidos y tres solo en dirigidos. Escoger la de la columna equivocada también deja una explicación.

3. Cuántos componentes

¿Cuántos componentes conexos tiene?

4. La pregunta que no compila

¿Cuál de estas tres preguntas queda sin respuesta definida?

5. Para llevarse

Sin solución aquí. Al grafo E agréguele la menor cantidad de flechas que lo deje fuertemente conexo, y diga cuántas fueron y por qué con una menos no alcanza. Después quítele al grafo C la flecha 2 → 0 y diga qué pasa con la clasificación y con el número de componentes fuertemente conexos.