Ejercicios · AyG PUJ · Orden topologico kahn¶
Nueve ejercicios para el navegador, organizados por los temas de la sesión y en el mismo orden; el último junta todo sobre un grafo grande. Ninguno usa el plan de estudios de las diapositivas, ni la instancia de Ordering Tasks que se resolvió en clase: los grafos, las entradas y los números son otros.
Recuento¶
grados¶
El grado de salida se lee de un vistazo, el de entrada hay que contarlo. Un
grafo de siete vértices donde primero se llenan a mano los siete contadores
—con aviso aparte cuando lo que se escribió es el grado de salida— y después
se ejecuta grados_de_entrada con la flecha que se está contando resaltada
en el dibujo. Entre las dos cosas, cuántas veces corre la línea de la suma.
Orden topológico¶
ordenes¶
Antes de cualquier algoritmo. Un grafo de seis vértices y seis listas: hay que marcar cuáles son órdenes topológicos, y la comprobación dice, por cada lista descartada, qué flecha quedó al revés. La segunda tarjeta pregunta cuántos órdenes distintos tiene el grafo; son más de uno y muchos menos que las \(720\) permutaciones.
El algoritmo de Kahn¶
kahn¶
El algoritmo paso a paso, con el contador de entrada de cada vértice dibujado encima: se ve bajar cuando sale un predecesor y ponerse en verde en el instante en que el vértice entra a la cola. Se arranca con el grafo más sencillo, de seis vértices y una sola fuente; los otros dos agregan una fuente de más y un vértice suelto. Antes de ejecutar se predice cuántas fuentes hay, y la tabla registra cada salida con los contadores que bajó. Las dos preguntas del final son las que sostienen la demostración: cuándo entra un vértice a la cola y por qué eso basta para que el orden sea topológico.
ciclo¶
El mismo algoritmo sobre grafos con ciclos. La cola se vacía antes de tiempo
y hay que predecir cuántos vértices alcanzan a salir; el tercer grafo no
tiene ciclos y sirve de contraste. La tabla se detiene donde se detiene el
algoritmo, y las dos últimas tarjetas preguntan quién queda por fuera —los
del ciclo y todo lo que depende de ellos— y por qué len(orden) < n es la
señal en las dos direcciones.
Un problema de juez¶
tareas¶
Ordering Tasks con otra instancia. Primero la entrada y qué espera a qué,
leído a mano; después, cuál de cuatro listas de adyacencia construye la
lectura —entre las otras tres están la de las flechas al revés y la que
olvida el - 1—; después el paso a paso de leer_grafo con el grafo
llenándose; y al final, cuál de tres líneas imprime el programa.
Errores comunes¶
errores¶
Tres versiones del algoritmo con una línea equivocada cada una, sobre un grafo con un vértice suelto y otro de dos predecesores. Ninguna falla al correr: las tres devuelven una lista, y hay que mirarla. Al señalar la falla aparece lo que devuelve esa versión y en qué se diferencia de la correcta: una deja fuera a cuatro vértices, otra saca un vértice antes que su predecesor, y la tercera pierde el vértice suelto y por eso reporta un ciclo que no existe.
Ejercicios¶
marcas¶
Para el ejercicio 1. La búsqueda en profundidad con dos marcas más: el color
de cada vértice, que pasa de blanco a gris al entrar y de gris a negro al
salir, y un reloj que anota los dos instantes. Todo ocurre sobre el dibujo:
los vértices se pintan, las marcas d/f aparecen encima y la flecha que se
está mirando queda azul, o roja cuando llega a un vértice gris, que es lo que
delata el ciclo. Tres grafos, del árbol al que tiene un ciclo, y las dos
versiones del recorrido, la recursiva y la de pila explícita, que dejan las
mismas marcas. Antes de ejecutar se predice en cuánto termina el reloj.
variantes¶
Para los ejercicios 2 y 3 de abajo. Un grafo de siete vértices y las tres versiones del algoritmo: con cola, con pila y con la fuente de número más bajo. Antes de correrlas hay que decir cuál orden devuelve cada una; los tres órdenes son distintos y los tres son topológicos, y la tabla muestra en cada paso qué fuentes había para escoger.
Todo junto, sobre un grafo grande¶
grande¶
El último y el más exigente, para cuando los anteriores ya salen solos.
Catorce módulos de un proyecto y diecinueve dependencias: demasiado para
seguir la traza de memoria, que es justo el tamaño en que el algoritmo deja
de ser un ejercicio de papel. Se predice cuántos módulos salen, se ejecuta y
se ve el frente de compilación avanzar por el dibujo, se marcan las parejas
cuyo orden el grafo deja libre —cinco, con el camino que fija a cada una de
las otras— y se explica por qué app sale de último en cualquier orden
válido. Con la dependencia de más, app → config, diez módulos se quedan
sin compilar.
Para resolver en papel¶
Estos ejercicios entran en el material del parcial. Los tres primeros se propusieron en clase.
-
Escriba
tiene_ciclo(G)usando búsqueda en profundidad, sin el algoritmo de Kahn. Sobre[[4], [3], [0], [0, 6], [], [2], []]respondeFalse; sobre[[4], [3], [0], [0, 6], [3], [2], []]respondeTrue. La marca de visitado no alcanza: llegar a un vértice ya visitado por otro camino no es un ciclo. Cada vértice pasa por tres estados: sin visitar, en proceso (su llamada no ha terminado) y terminado. Piense qué significa toparse con uno en proceso. -
En \(Kahn(G)\) se cambia la cola por una pila: las fuentes se apilan y sale la última que entró. ¿Sigue devolviendo un orden topológico? Justifíquelo con lo que sostiene el algoritmo. Ejecútelo a mano sobre el plan de estudios y compare con
[1, 5, 3, 2, 6, 0, 4]. -
Modifique \(Kahn(G)\) para que, entre todos los órdenes topológicos, devuelva el menor en orden lexicográfico: el que tiene el menor primer vértice; entre los que empatan, el menor segundo, y así. Sobre el plan de estudios debe devolver
[1, 3, 5, 2, 0, 4, 6]. Diga qué estructura reemplaza a la cola y cuánto cuesta el algoritmo con ella. La versión ingenua ya lo devuelve, porque busca desde el vértice \(0\); la pregunta es cómo sacar siempre la fuente de número más bajo sin recorrer la lista entera. -
Dibuje un grafo dirigido de cinco vértices que tenga exactamente un orden topológico, y otro de cinco vértices que tenga \(120\). Diga qué tienen las aristas en cada caso.
-
En un grafo dirigido acíclico, ¿puede haber más de una fuente? ¿Más de un sumidero (vértice con grado de salida \(0\))? ¿Puede un vértice ser las dos cosas? Dé un ejemplo de cada respuesta afirmativa.
-
Escriba \(Kahn(G)\) sobre matriz de adyacencia y diga cuánto cuesta en términos de \(V\) y \(E\). ¿Dónde se pierde la cuenta de \(\Theta(V + E)\)?
-
Un grafo dirigido tiene un solo ciclo y \(k\) vértices desde los que hay camino hasta algún vértice del ciclo, sin contar los del ciclo. ¿Cuántos vértices emite Kahn? ¿Y si los \(k\) vértices tienen camino desde el ciclo en vez de hacia él?
Para programar¶
-
UVa 10305 — Ordering Tasks. Enunciado en https://vjudge.net/problem/UVA-10305, envío en https://vjudge.net/problem/UVA-10305. El problema de la clase, tal cual: para enviar la solución y ver el veredicto.
-
UVa 11686 — Pick up sticks. Enunciado en https://vjudge.net/problem/UVA-11686, envío en https://vjudge.net/problem/UVA-11686. \(n\) palitos y \(m\) parejas \(a\) está encima de \(b\), con \(n\) y \(m\) hasta un millón; un orden para recogerlos sin levantar uno que tenga otro encima, o
IMPOSSIBLE. Es la segunda variante de la clase, conlen(orden) < ndecidiendo la palabra. Con un millón de líneas se lee todo de una vez consys.stdin.read(). -
UVa 11060 — Beverages. Enunciado en https://vjudge.net/problem/UVA-11060, envío en https://vjudge.net/problem/UVA-11060. \(N\) bebidas con nombre y \(M\) parejas \(B_1\) antes que \(B_2\); cuando dos no están relacionadas va primero la que apareció primero en la entrada. Es el ejercicio 3 con los nombres numerados por orden de aparición. La salida lleva
Case #y una línea en blanco después de cada caso; se copia del enunciado letra por letra.
De los temas anteriores¶
Los recorridos y su costo, que el algoritmo de hoy reutiliza, se practican en la página de representaciones y recorridos; los grafos implícitos, en la suya.