Saltar a contenido

Clase 8. Orden topológico

Semana del 21 de septiembre de 2026.

Poner en fila los vértices de un grafo dirigido sin violar ninguna flecha. Un plan de estudios con prerrequisitos es el primer ejemplo; de ahí salen la definición, el algoritmo de Kahn con su cola de fuentes, la prueba de que el orden que devuelve sirve, y la señal con la que el mismo algoritmo avisa que el grafo tiene un ciclo. Cierra con un problema de juez y tres ejercicios propuestos para el parcial.

  • Orden topológico


    El plan de estudios, la definición, el lema de la fuente, Kahn en su versión ingenua y con la cola, la traza a mano, las demostraciones de correctitud y de costo, la detección de ciclos y Ordering Tasks.

    Entrar

  • Diapositivas


    Las 71 láminas con las anotaciones de la sesión y una página de tablero, con la ejecución del algoritmo paso a paso sobre el plan de estudios: una lámina por vértice que sale, con los colores y los contadores.

    Abrir

Ejercicios

Nueve interactivos, por los temas de la sesión y en su mismo orden: contar los grados de entrada, decidir a mano cuáles listas son órdenes topológicos, el algoritmo de Kahn con los contadores a la vista, la cola que se vacía antes de tiempo cuando hay ciclos, la entrada del juez convertida en grafo, tres versiones con una línea equivocada, los colores y los tiempos de la búsqueda en profundidad, y las variantes con cola, pila y fuente menor. Cierra uno más largo, con catorce módulos y sus dependencias, para aplicar todo lo anterior sobre un grafo que ya no cabe en la cabeza. Después, siete en papel y tres para el juez.

Todos están en la página de ejercicios.

Antes de entrar

Conviene tener a mano los recorridos y su costo: el algoritmo de hoy cuesta lo mismo y por la misma cuenta.