← Volver a los ejercicios

Cuáles listas sirven

Antes de cualquier algoritmo: dado el grafo, decidir a mano cuáles de seis listas son órdenes topológicos. La regla es una sola, que cada flecha vaya de un vértice a otro que aparece después, y aquí se aplica seis veces por lista.

1. El grafo

Seis vértices y seis flechas: 0 → 3, 1 → 3, 1 → 4, 3 → 2, 3 → 5, 4 → 5.

Entrada: este grafo y una lista con los seis vértices.  Salida: si la lista es un orden topológico, es decir, si cada una de las seis flechas va de un vértice a otro que aparece después en la lista.

2. Marque las que son órdenes topológicos

3. Cuántos hay

¿Cuántos órdenes topológicos distintos tiene este grafo?

4. Para llevarse

Sin solución aquí. Agregue al grafo una sola flecha que lo deje con exactamente un orden topológico, y otra distinta que lo deje sin ninguno. Diga en cada caso por qué.