Ejercicios · AyG PUJ · Árboles de cubrimiento mínimo¶
Cinco ejercicios para el navegador, uno por tema de la sesión y en el mismo orden. Dos de ellos corren el código Python de la sesión línea por línea.
Ninguno usa los grafos de las diapositivas ni los de sus ejercicios propuestos: otros vértices, otros pesos y otras raíces.
Conectar al menor costo¶
Armar un árbol a mano¶
Dos grafos con pesos, uno de cinco barrios y otro de ocho. Los tendidos se escogen con un clic y el que cierra un ciclo queda rechazado, diciendo qué barrios ya estaban juntos.
Al completar la selección aparece el peso que quedó frente al mínimo, y cuántos árboles de cubrimiento tenía el grafo.
La propiedad de corte¶
La arista ligera de un corte¶
Cuatro rondas sobre un mismo grafo de ocho vértices, cambiando S en cada una. Se escoge la arista ligera del corte y al contestar el dibujo pinta cuáles cruzan.
Las opciones separan tres confusiones: una arista barata que no cruza, una que cruza y no es la más barata, y la más barata del grafo entero. La última ronda tiene un empate.
El algoritmo de Kruskal¶
Kruskal línea por línea¶
kruskal paso a paso sobre dos grafos, con la lista ordenada a la vista, el arreglo p de
los conjuntos disjuntos y los pedazos de cada momento.
Antes de arrancar se predice cuántas aristas se descartan y en qué puesto se completa el árbol. Las que entran quedan verdes y las descartadas, grises punteadas.
El algoritmo de Prim¶
Prim línea por línea¶
prim paso a paso desde la raíz que se escoja, con la tabla de clave y padre, los
vértices del árbol marcados y el borde resaltado. Antes se predice el orden de entrada.
Una tarjeta aparte corre el mismo grafo con prim_cola y muestra las parejas que salen de la
cola y se descartan por viejas.
Cuál de los dos¶
Decidir sin correr el algoritmo¶
Diez preguntas sin traza: sumar una constante a los pesos, duplicarlos, pesos negativos, pesos repetidos, un grafo que no es conexo, aristas que ya llegan ordenadas, denso contra ralo, el árbol de cubrimiento máximo y el camino más corto entre dos vértices.
Cada opción responde con su propia explicación.
Para resolver en papel¶
-
En el grafo de ocho vértices de la actividad de Kruskal, escriba la lista ordenada y marque las tres que se descartan. Para cada arista que entra, diga de qué corte es la ligera.
-
Corra Prim sobre el grafo en anillo desde la raíz 3 y escriba la tabla de
claveypadredespués de cada extracción. Compruebe que el peso es el mismo que desde la raíz 0. -
UVa 11631, Dark roads: https://vjudge.net/problem/UVA-11631. La respuesta es la suma de todos los pesos menos el peso del árbol mínimo. En el grafo de ocho vértices de la actividad de Kruskal las trece calles suman 91 y el árbol pesa 31: diga cuánto se ahorra por noche y cuántas calles quedan apagadas. La página pide cuenta para ver el enunciado y para enviar.
-
Demuestre que una arista que pesa más que todas las demás de algún ciclo no está en ningún árbol de cubrimiento mínimo. Sirve el intercambio del teorema 23.1: tome un árbol que la contenga y construya uno más barato.