← Volver a los ejercicios

Cuáles listas son órdenes topológicos

Un orden topológico pone cada vértice antes de todos los que le siguen por una flecha. La búsqueda en profundidad entrega uno, pero hay otras formas de ordenar los vértices con los mismos tiempos y no todas sirven. Cada grafo trae la tabla de d y f de una búsqueda ya hecha y varias propuestas; hay que marcar las que son órdenes topológicos y después leer por qué falla cada una de las otras.

1. El grafo y los tiempos de la búsqueda

Grafo:

Sobre cada vértice, d/f de una búsqueda que arranca en el vértice de número más bajo y recorre las listas en su orden.

2. Marque los órdenes topológicos

3. Para llevarse

Sin solución aquí. En el grafo de la casa, el orden por d creciente sí sirve. Agregue una flecha de plomería a eléctrica y diga qué le pasa a ese orden y por qué el de f decreciente sigue valiendo. Después escriba, para el grafo del compilador, otro orden de Kahn distinto de los que aparecen y compruebe sus seis flechas.