Árboles de cubrimiento mínimo · AyG C18¶
Un grafo conexo y con pesos admite muchas formas de quedar conectado gastando menos aristas de las que tiene. La más barata de todas es un árbol, y hay dos algoritmos voraces que la encuentran sin equivocarse nunca: el de Kruskal, que va mirando las aristas en orden de precio, y el de Prim, que hace crecer un solo árbol desde donde uno quiera. Los dos se apoyan en el mismo resultado, la propiedad de corte, que es lo que garantiza que una arista aceptada no haya que devolverla después.
Esta nota desarrolla el problema, la propiedad de corte con su demostración, los dos algoritmos sobre un mismo grafo de siete vértices y lo que cuesta cada uno. El grafo de trabajo es además el caso de ejemplo del problema de juez que cierra la sesión, de modo que la traza que se hace a mano sirve para comprobar el programa.
De dónde venimos¶
La estructura de conjuntos disjuntos ya quedó vista. Lo que se usa aquí son sus tres operaciones:
| operación | qué hace | cuánto cuesta |
|---|---|---|
make_set(x) |
arma el conjunto \(\{x\}\), con \(x\) de raíz | \(\Theta(1)\) |
find_set(x) |
devuelve la raíz del conjunto donde está \(x\) | \(O(\alpha(n))\) |
union(x, y) |
cuelga un conjunto del otro | \(O(\alpha(n))\) |
La unión por rango cuelga el árbol bajo del alto, con lo que ninguno crece más de lo necesario, y la compresión de caminos aprovecha cada búsqueda para dejar apuntando a la raíz todo lo que encontró de paso. Con las dos, el costo amortizado de una operación es \(O(\alpha(n))\), donde \(\alpha\) es la inversa de la función de Ackermann, que para cualquier \(n\) que quepa en un computador no pasa de \(4\).
Las tres operaciones, en tres elementos¶
Con make_set(1), make_set(2) y make_set(3) quedan tres árboles de un solo
nodo, cada uno apuntándose a sí mismo y con rango \(0\). union(1, 2) encuentra
las raíces \(1\) y \(2\), que vienen iguales de rango, así que cuelga la segunda de
la primera y el rango de \(1\) sube a \(1\). union(2, 3) pide unir \(2\) con \(3\),
pero lo que se cuelga es la raíz de \(2\), que ya es \(1\): el \(3\) queda bajo el \(1\)
y no bajo el \(2\). Al final find_set devuelve \(1\) para los tres, y por eso los
tres están en el mismo conjunto.
El bosque, con un ejemplo¶
Cada elemento guarda a quién apunta, y la raíz es quien se apunta a sí mismo. Sobre los nueve elementos del ejemplo del curso, después de las uniones \((5,1)\), \((1,3)\), \((7,2)\), \((4,8)\), \((6,9)\), \((3,2)\) y \((8,9)\), el bosque queda en dos árboles:
| raíz | cuelgan de ella | más abajo | rango |
|---|---|---|---|
| 5 | 1, 3, 7 | 2, bajo el 7 | 2 |
| 4 | 8, 6 | 9, bajo el 6 | 2 |
Las siete llamadas, una por una:
| llamado | raíces | rangos | qué cambia | |
|---|---|---|---|---|
| 1 | union(5, 1) |
5, 1 | 0 = 0 | p[1] = 5 y el rango de 5 sube a 1 |
| 2 | union(1, 3) |
5, 3 | 1 > 0 | p[3] = 5 y el rango se queda |
| 3 | union(7, 2) |
7, 2 | 0 = 0 | p[2] = 7 y el rango de 7 sube a 1 |
| 4 | union(4, 8) |
4, 8 | 0 = 0 | p[8] = 4 y el rango de 4 sube a 1 |
| 5 | union(6, 9) |
6, 9 | 0 = 0 | p[9] = 6 y el rango de 6 sube a 1 |
| 6 | union(3, 2) |
5, 7 | 1 = 1 | p[7] = 5 y el rango de 5 sube a 2 |
| 7 | union(8, 9) |
4, 6 | 1 = 1 | p[6] = 4 y el rango de 4 sube a 2 |
Dos cosas se leen en las columnas del medio. Lo que se cuelga son las raíces y no los argumentos: la sexta línea pide unir 3 con 2, y lo que se mueve es el 7 debajo del 5. Y el rango sube en un solo caso, cuando los dos llegan iguales; la segunda línea dice por qué, porque ahí el 3 se cuelga de un árbol que ya era más alto, así que la altura no cambió y el rango tampoco.
Preguntar si \(2\) y \(3\) están en el mismo conjunto es subir desde cada uno hasta su raíz y comparar: los dos llegan a \(5\), así que sí. El rango es una cota de la altura y no el tamaño, y por eso el de \(5\) es \(2\) aunque de él cuelguen cuatro elementos.
Al llamar find_set(9) el recorrido pasa por \(6\) y llega a \(4\), y al volver
reengancha a \(9\) directamente bajo \(4\). El árbol pierde un nivel sin que nadie
lo haya pedido, y la siguiente consulta sobre \(9\) cuesta un solo salto. Esa es
la compresión de caminos: no se hace en una pasada aparte, se hace mientras se
busca.
Lo único que hace falta recordar es que dos elementos están en el mismo
conjunto si find_set les devuelve la misma raíz. Esa es, palabra por
palabra, la pregunta de si dos ciudades ya quedaron conectadas. El detalle de
la estructura, con su ejemplo paso a paso, está en la
nota de conjuntos disjuntos del semestre anterior.
Para qué más sirven¶
La pregunta que los conjuntos disjuntos contestan barato es si dos elementos ya se alcanzan, sobre una red a la que le van llegando enlaces. Con un recorrido cada pregunta cuesta \(O(V + E)\) y hay que volver a recorrer en cuanto entre un enlace nuevo; aquí la pregunta cuesta \(O(\alpha(n))\) y el enlace nuevo es una unión.
De ahí salen tres usos que no tienen que ver con árboles de cubrimiento. En segmentación de imágenes hay un elemento por píxel, se unen los vecinos de color parecido y cada conjunto queda una región. En percolación se unen las celdas abiertas de un material poroso y la pregunta es si el borde de arriba quedó en el mismo conjunto que el de abajo. Y un laberinto se genera tumbando paredes mientras los dos lados estén en conjuntos distintos, que es Kruskal con pesos al azar.
El problema¶
Conectar al menor costo¶
Una empresa tiene que dejar comunicados siete barrios con fibra. No todos los pares se pueden tender, y cada tendido posible tiene su costo. Basta con que cada barrio alcance a los demás, sea directo o pasando por otros.
Antes de cualquier algoritmo valen dos preguntas: ¿cuántos tendidos va a tener la respuesta, y puede sobrar alguno?
Por qué la respuesta es un árbol¶
Si la selección deja un ciclo, se puede quitar cualquier arista de ese ciclo y todo sigue conectado, porque sus dos extremos se alcanzan por el otro lado del ciclo. Como las aristas cuestan, la solución óptima no tiene ciclos. Y tiene que tocar todos los vértices. Un grafo conexo y acíclico es un árbol, así que la respuesta es un árbol de cubrimiento y tiene exactamente \(|V| - 1\) aristas.
De ahí la definición, que es la del capítulo 23 de CLRS, página 624.
Definición. Sea \(G = (V, E)\) un grafo no dirigido y conexo con pesos \(w : E \to \mathbb{R}\). Un árbol de cubrimiento mínimo es un subconjunto \(E' \subseteq E\) tal que \((V, E')\) es un árbol y
es el menor posible entre todos los árboles de cubrimiento de \(G\).
Nada en la definición pide que los pesos sean positivos, y eso va a importar más adelante.
El grafo de la sesión¶
Siete vértices y once aristas:
| arista | peso | arista | peso | arista | peso | ||
|---|---|---|---|---|---|---|---|
| \((0,1)\) | 7 | \((1,4)\) | 7 | \((4,5)\) | 8 | ||
| \((0,3)\) | 5 | \((2,4)\) | 5 | \((4,6)\) | 9 | ||
| \((1,2)\) | 8 | \((3,4)\) | 15 | \((5,6)\) | 11 | ||
| \((1,3)\) | 9 | \((3,5)\) | 6 |
Las once suman \(90\). El árbol de cubrimiento mínimo pesa \(39\) y lo forman \((0,3)\), \((2,4)\), \((3,5)\), \((0,1)\), \((1,4)\) y \((4,6)\). Conviene escoger seis tendidos a mano antes de seguir leyendo, y volver a esa suma al final.
Probar todos no sirve¶
Este grafo tiene \(141\) árboles de cubrimiento. Probados los \(141\), el de peso \(39\) aparece una sola vez, el siguiente pesa \(40\) y el más caro \(59\). O sea que acertar por tanteo no es tan difícil aquí, y por eso el grafo es chico.
La cuenta se desborda enseguida. En un grafo completo de \(n\) vértices hay \(n^{n-2}\) árboles de cubrimiento, que es la fórmula de Cayley:
| vértices | árboles de cubrimiento del grafo completo |
|---|---|
| 7 | \(16\,807\) |
| 10 | \(10^{8}\) |
| 20 | \(2{,}6 \times 10^{23}\) |
Desde veinte vértices enumerar queda descartado. Lo que sigue es un algoritmo que escoge aristas de una en una y un teorema que garantiza que ninguna de esas decisiones hay que deshacerla.
Dónde aparece¶
Las redes que se construyen una vez son el caso directo: acueductos, fibra, tendido eléctrico, las pistas de una placa de circuito impreso. El peso es lo que cuesta poner ese tramo. El primer algoritmo conocido, el de Otakar Borůvka en 1926, salió justamente de ahí: la empresa que estaba llevando luz eléctrica a los pueblos de Moravia le pidió la forma más barata de cablearlos.
El otro grupo de aplicaciones no tiene nada que ver con cables. El agrupamiento por enlace simple es el árbol de cubrimiento mínimo sobre las distancias entre los puntos: quitarle las \(k-1\) aristas más caras parte el árbol en \(k\) pedazos, y esos pedazos son los grupos. Con esa misma idea se segmentan imágenes, tomando un vértice por píxel y el contraste como peso.
Y sirve para acotar un problema que no se sabe resolver rápido. Recorrer el árbol mínimo de ida y vuelta da un circuito que pasa por todas las ciudades y cuesta a lo sumo el doble del mejor circuito posible, que es la aproximación clásica para el problema del vendedor viajero.
La propiedad de corte¶
Cuatro palabras¶
- Un corte \((S, V \setminus S)\) es una partición de los vértices en dos montones, ninguno vacío.
- Una arista cruza el corte si tiene una punta en \(S\) y la otra en \(V \setminus S\).
- El corte respeta a un conjunto de aristas \(A\) si ninguna arista de \(A\) lo cruza.
- Una arista ligera del corte es una de peso mínimo entre las que cruzan.
Con \(S = \{0,1,3\}\) cruzan cuatro aristas, \((1,2)\) con \(8\), \((1,4)\) con \(7\), \((3,4)\) con \(15\) y \((3,5)\) con \(6\), de modo que la ligera es \((3,5)\). Con \(S = \{0\}\) cruzan dos, \((0,1)\) con \(7\) y \((0,3)\) con \(5\), y la ligera es \((0,3)\). La arista ligera es del corte y no del grafo: cambiar la partición cambia la respuesta.
Falta una palabra más. Una arista \(e \notin A\) es segura para \(A\) si \(A \cup \{e\}\) todavía cabe dentro de algún árbol de cubrimiento mínimo. Un algoritmo que solo agregue aristas seguras termina en un árbol mínimo sin tener que retroceder nunca. La dificultad está en reconocer una arista segura sin conocer la respuesta, y el teorema que sigue da el criterio.
El teorema¶
Teorema (propiedad de corte; CLRS, teorema 23.1, página 626). Sea \(A\) un subconjunto de algún árbol de cubrimiento mínimo \(T\), sea \((S, V \setminus S)\) un corte que respeta a \(A\) y sea \(e\) una arista ligera de ese corte. Entonces \(e\) es segura para \(A\).
Demostración. Se procede de forma directa, construyendo a partir de \(T\) otro árbol de cubrimiento mínimo que contenga a \(A \cup \{e\}\). Si \(e \in T\) no hay nada que hacer, así que se supone \(e = (u,v) \notin T\).
Como \(T\) es un árbol, entre \(u\) y \(v\) hay un único camino, y agregarle \(e\) lo cierra en un ciclo. Ese camino arranca en \(S\), porque \(u \in S\), y termina afuera, porque \(v \notin S\), de modo que en algún paso salta de un lado al otro. Sea \(e' = (x,y)\) esa arista. Cruza el corte, y como el corte respeta a \(A\), no está en \(A\). Como \(e\) es ligera del corte y \(e'\) también lo cruza,
Sea \(T' = T \cup \{e\} \setminus \{e'\}\). Quitarle a un ciclo una arista deja todo conectado, así que \(T'\) sigue siendo un árbol de cubrimiento; contiene a \(A\), porque lo único que salió fue \(e'\), que no estaba en \(A\); y pesa
Conclusión. Como \(T\) era mínimo, \(w(T')\) no puede ser menor que \(w(T)\), de manera que los dos pesan lo mismo y \(T'\) también es un árbol de cubrimiento mínimo. Ese \(T'\) contiene a \(A \cup \{e\}\), que es exactamente lo que significa que \(e\) sea segura para \(A\). \(\blacksquare\)
El argumento es un intercambio: si la arista ligera no estaba en el árbol, había una arista del mismo corte que no es más barata y que se puede cambiar por ella sin empeorar el total. De ahí sale todo lo demás.
Cuándo el árbol es único¶
Corolario. Si los pesos de \(G\) son todos distintos entre sí, el árbol de cubrimiento mínimo es único.
Demostración. Se procede por contradicción. Supóngase que hay dos árboles mínimos distintos \(T_1\) y \(T_2\), y sea \(e\) la arista más liviana de la diferencia simétrica \(T_1 \triangle T_2\), que está bien definida porque los pesos son distintos. Sin pérdida de generalidad, \(e \in T_1 \setminus T_2\).
Agregarle \(e\) a \(T_2\) cierra un ciclo, y ese ciclo tiene al menos una arista \(e' \in T_2 \setminus T_1\), porque si todas sus aristas estuvieran en \(T_1\), \(T_1\) tendría un ciclo. Por cómo se escogió \(e\), \(w(e) < w(e')\). Entonces \(T_2 \cup \{e\} \setminus \{e'\}\) es un árbol de cubrimiento de peso estrictamente menor que \(w(T_2)\), lo que contradice que \(T_2\) fuera mínimo. Por lo tanto no hay dos árboles mínimos distintos. \(\blacksquare\)
Los once pesos del grafo de la sesión no son todos distintos, hay dos cincos, dos sietes, dos ochos y dos nueves, así que el corolario no aplica. Aun así el árbol de \(39\) resulta único, cosa que se comprobó enumerando los \(141\): el corolario da una condición suficiente, no necesaria.
Con pesos repetidos lo que sí se conserva es el peso total. Dos corridas distintas pueden devolver árboles distintos, los dos mínimos y los dos del mismo peso, que es lo que suele pedir un juez en línea.
Cuándo una arista está en todos¶
Una arista \(e\) pertenece a todo árbol de cubrimiento mínimo si y solo si existe un corte que ella cruza y en el que es estrictamente más liviana que cualquier otra que lo cruce. La ida sale de la propiedad de corte: si ninguna otra arista del corte puede sustituirla, cruzar ese corte obliga a incluirla. Si el peso mínimo del corte lo alcanzan dos aristas, la obligación desaparece y hay un árbol mínimo con una y otro con la otra.
El algoritmo de Kruskal¶
La idea¶
Se ordenan las aristas por peso y se recorren de la más barata a la más cara. Si los dos extremos están en pedazos distintos, la arista entra; si ya estaban juntos, cerraría un ciclo y se descarta.
Que la arista que entra sea segura es la propiedad de corte aplicada a un corte que no hay que dibujar. Sea \(S\) el pedazo que contiene a \(u\) en el momento de mirar \((u,v)\). Ninguna arista ya aceptada cruza ese corte, porque todas viven dentro de un pedazo, así que el corte respeta a lo que se lleva. Y \((u,v)\) es ligera de ese corte: si alguna arista del corte pesara menos, se habría mirado antes, y como une \(S\) con afuera, se habría aceptado, de modo que \(u\) y \(v\) ya estarían en el mismo pedazo.
El código¶
def kruskal(V, aristas):
ordenadas = sorted(aristas, key=lambda e: e[2])
p = {}
rango = {}
for v in V:
make_set(p, rango, v)
mst = []
peso = 0
i = 0
while i < len(ordenadas) and len(mst) < len(V) - 1:
u, v, w = ordenadas[i]
if find_set(p, u) != find_set(p, v):
union(p, rango, u, v)
mst.append((u, v, w))
peso = peso + w
i = i + 1
return mst, peso
La condición len(mst) < len(V) - 1 es la que para apenas el árbol queda
completo. Sin ella el resultado sería el mismo, porque todas las aristas que
faltan cerrarían ciclo, pero habría que mirarlas.
La traza¶
Las once aristas en orden ascendente son
Hay cuatro pesos repetidos, y entre iguales el orden lo decide la lista de
entrada, porque el sorted de Python es estable: como las aristas están
escritas por vértice de origen, \((0,3,5)\) queda antes que \((2,4,5)\) y
\((0,1,7)\) antes que \((1,4,7)\). Ese desempate no cambia la respuesta. Los
dieciséis órdenes posibles dan este mismo árbol, y lo único que cambia es si
se miran ocho aristas o nueve.
Antes de leer la tabla vale predecir cuáles entran y en cuál se completa el árbol.
| arista | lo que compara find_set |
decisión | pedazos después | |
|---|---|---|---|---|
| 1 | \((0,3,5)\) | \(\{0\} \neq \{3\}\) | entra | \(\{0,3\},\{1\},\{2\},\{4\},\{5\},\{6\}\) |
| 2 | \((2,4,5)\) | \(\{2\} \neq \{4\}\) | entra | \(\{0,3\},\{1\},\{2,4\},\{5\},\{6\}\) |
| 3 | \((3,5,6)\) | \(\{0,3\} \neq \{5\}\) | entra | \(\{0,3,5\},\{1\},\{2,4\},\{6\}\) |
| 4 | \((0,1,7)\) | \(\{0,3,5\} \neq \{1\}\) | entra | \(\{0,1,3,5\},\{2,4\},\{6\}\) |
| 5 | \((1,4,7)\) | \(\{0,1,3,5\} \neq \{2,4\}\) | entra | \(\{0,1,2,3,4,5\},\{6\}\) |
| 6 | \((1,2,8)\) | el mismo pedazo | descartar | sin cambio |
| 7 | \((4,5,8)\) | el mismo pedazo | descartar | sin cambio |
| 8 | \((1,3,9)\) | el mismo pedazo | descartar | sin cambio |
| 9 | \((4,6,9)\) | \(\{0,\ldots,5\} \neq \{6\}\) | entra | \(\{0,1,2,3,4,5,6\}\) |
En la novena ya hay seis aristas, que son \(|V| - 1\), y el ciclo no vuelve a entrar: \((5,6,11)\) y \((3,4,15)\) no se alcanzan a mirar. El peso es \(5+5+6+7+7+9 = 39\).
El corte detrás de cada arista aceptada¶
El cuarto paso sirve de ejemplo. Al llegar a \((0,1)\) ya entraron \((0,3)\), \((2,4)\) y \((3,5)\), de modo que el pedazo de \(0\) es \(S = \{0,3,5\}\). Cruzan ese corte cinco aristas:
| arista | peso |
|---|---|
| \((0,1)\) | 7 |
| \((4,5)\) | 8 |
| \((1,3)\) | 9 |
| \((5,6)\) | 11 |
| \((3,4)\) | 15 |
La más barata es \((0,1)\), y no podía ser otra: una arista del corte que pesara
menos de \(7\) ya se habría mirado y habría pegado los dos pedazos. Las tres
aristas aceptadas están dentro de \(S\) o dentro de \(V \setminus S\), así que el
corte las respeta. Las cinco filas de la tabla que dicen entra repiten este
mismo argumento con otro corte.
Lo que cuesta¶
Ordenar las aristas es \(O(|E| \log |E|)\). Después hay \(2|E|\) llamados a
find_set y hasta \(|V| - 1\) a union, que juntos cuestan
\(O(|E| \cdot \alpha(|V|))\), prácticamente lineal. El ordenamiento domina y el
algoritmo queda en \(O(|E| \log |E|)\), que también se escribe
\(O(|E| \log |V|)\) porque \(|E| \leq |V|^2\) y entonces
\(\log |E| \leq 2 \log |V|\).
Si las aristas llegaran ya ordenadas, o si los pesos fueran enteros chicos y se pudieran repartir en cubetas, lo que queda es casi lineal.
El algoritmo de Prim¶
La idea¶
Se arranca de una raíz y se mantiene \(V_T\), el conjunto de vértices que ya entraron al árbol. En cada paso se agrega la arista más barata que va de \(V_T\) a algún vértice de afuera.
Aquí el corte no hay que buscarlo: es siempre \((V_T, V \setminus V_T)\), el borde del árbol. Las aristas aceptadas viven dentro de \(V_T\), así que el corte las respeta, y la más barata que cruza es ligera por definición. Es la misma propiedad de corte, aplicada siempre al mismo corte en lugar de a uno distinto cada vez.
Para no recorrer todas las aristas del borde en cada paso se guardan dos cosas
por cada vértice de afuera: clave[v], el peso de la arista más barata que lo
conecta con el árbol, y padre[v], el vértice del árbol de donde sale esa
arista. Al entrar \(u\) al árbol, sus vecinos revisan si \(u\) les mejora la clave.
El código con búsqueda lineal¶
def extraer_minimo(clave, en_mst):
minimo = None ; mejor = INFTY
for v in clave:
if not en_mst[v] and clave[v] < mejor:
mejor = clave[v] ; minimo = v
return minimo
def prim(grafo, raiz):
clave = {} ; padre = {} ; en_mst = {}
for v in grafo:
clave[v] = INFTY ; padre[v] = None ; en_mst[v] = False
clave[raiz] = 0
peso = 0
restantes = len(grafo)
while restantes > 0:
u = extraer_minimo(clave, en_mst)
if u is None:
restantes = 0
else:
en_mst[u] = True
if padre[u] is not None:
peso = peso + clave[u]
for (v, w) in grafo[u]:
if not en_mst[v] and w < clave[v]:
clave[v] = w ; padre[v] = u
restantes = restantes - 1
return padre, peso
El if u is None es el caso del grafo que no es conexo: cuando ya no queda
ningún vértice de afuera con clave finita, no hay más que alcanzar y el ciclo
termina con menos de \(|V| - 1\) aristas.
La traza desde la raíz 0¶
Cada fila trae las claves de los vértices que están afuera, con el mínimo en negrita y la casilla vacía para el que ya entró.
| iter | 0 | 1 | 2 | 3 | 4 | 5 | 6 | extrae | arista |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | \(\infty\) | \(\infty\) | \(\infty\) | \(\infty\) | \(\infty\) | \(\infty\) | 0 | |
| 1 | 7 | \(\infty\) | 5 | \(\infty\) | \(\infty\) | \(\infty\) | 3 | \((0,3,5)\) | |
| 2 | 7 | \(\infty\) | 15 | 6 | \(\infty\) | 5 | \((3,5,6)\) | ||
| 3 | 7 | \(\infty\) | 8 | 11 | 1 | \((0,1,7)\) | |||
| 4 | 8 | 7 | 11 | 4 | \((1,4,7)\) | ||||
| 5 | 5 | 9 | 2 | \((4,2,5)\) | |||||
| 6 | 9 | 6 | \((4,6,9)\) |
El vértice \(4\) es el que más se mueve: su clave baja de \(15\) a \(8\) y después a \(7\), y con ella su padre pasa de \(3\) a \(5\) y a \(1\). Cuando por fin le llega el turno, la arista que entra es la última que lo mejoró. Las seis aristas suman \(39\), las mismas de Kruskal.
Desde otra raíz¶
Con raíz \(2\) el orden de extracción es \(2, 4, 1, 0, 3, 5, 6\) y las aristas entran en otro orden, pero son las mismas seis y el peso vuelve a ser \(39\).
| iter | 0 | 1 | 2 | 3 | 4 | 5 | 6 | extrae | arista |
|---|---|---|---|---|---|---|---|---|---|
| 0 | \(\infty\) | \(\infty\) | 0 | \(\infty\) | \(\infty\) | \(\infty\) | \(\infty\) | 2 | |
| 1 | \(\infty\) | 8 | \(\infty\) | 5 | \(\infty\) | \(\infty\) | 4 | \((2,4,5)\) | |
| 2 | \(\infty\) | 7 | 15 | 8 | 9 | 1 | \((4,1,7)\) | ||
| 3 | 7 | 9 | 8 | 9 | 0 | \((1,0,7)\) | |||
| 4 | 5 | 8 | 9 | 3 | \((0,3,5)\) | ||||
| 5 | 6 | 9 | 5 | \((3,5,6)\) | |||||
| 6 | 9 | 6 | \((4,6,9)\) |
Que coincidan no es casualidad de estos datos: el árbol mínimo de este grafo resultó ser único, así que la raíz solo cambia el orden en que se descubre.
Prim con cola de prioridad¶
extraer_minimo recorre todas las claves en cada vuelta, y esa pasada es lo
que deja la versión anterior en \(O(|V|^2)\). Con una cola de prioridad el mínimo
sale en \(O(\log |V|)\), y el algoritmo queda idéntico al de Dijkstra salvo por
una línea.
def prim_cola(grafo, raiz):
clave = {} ; padre = {} ; en_mst = {}
for v in grafo:
clave[v] = INFTY ; padre[v] = None ; en_mst[v] = False
clave[raiz] = 0
cola = list() ; heappush(cola, (clave[raiz], raiz))
peso = 0
while len(cola) != 0:
cu, u = heappop(cola)
# si u ya entro al arbol, la pareja es vieja y se descarta
if not en_mst[u]:
en_mst[u] = True
peso = peso + cu
for (v, w) in grafo[u]:
if not en_mst[v] and w < clave[v]:
clave[v] = w ; padre[v] = u
heappush(cola, (clave[v], v))
return padre, peso
En Dijkstra la comparación es \(d_u + w(u,v) < \mathit{dist}[v]\), el costo de llegar a \(v\) pasando por \(u\). Aquí es \(w < \mathit{clave}[v]\) a secas, porque lo que se mide es el precio de engancharlo al árbol, no el de llegar hasta él desde la raíz. Todo lo demás es igual, incluida la forma de descartar las parejas viejas.
La cola guarda parejas viejas¶
Cuando a un vértice le mejora la clave, la pareja anterior se queda en la cola, porque no hay forma de sacar un elemento de la mitad de un montón. Sale más tarde, cuando el vértice ya entró al árbol, y ahí se descarta. Sobre el grafo de la sesión, desde la raíz \(0\):
| sale | qué pasa | la cola queda | |
|---|---|---|---|
| 1 | \((0,0)\) | entra, mete \((5,3)\) y \((7,1)\) | \((5,3),(7,1)\) |
| 2 | \((5,3)\) | entra, mete \((6,5)\) y \((15,4)\) | \((6,5),(7,1),(15,4)\) |
| 3 | \((6,5)\) | entra, mete \((8,4)\) y \((11,6)\) | \((7,1),(8,4),(11,6),(15,4)\) |
| 4 | \((7,1)\) | entra, mete \((7,4)\) y \((8,2)\) | \((7,4),(8,2),(8,4),(11,6),(15,4)\) |
| 5 | \((7,4)\) | entra, mete \((5,2)\) y \((9,6)\) | \((5,2),(8,2),(8,4),(9,6),(11,6),(15,4)\) |
| 6 | \((5,2)\) | entra, no mejora a nadie | \((8,2),(8,4),(9,6),(11,6),(15,4)\) |
| 7 | \((8,2)\) | vieja, se descarta | \((8,4),(9,6),(11,6),(15,4)\) |
| 8 | \((8,4)\) | vieja, se descarta | \((9,6),(11,6),(15,4)\) |
| 9 | \((9,6)\) | entra, no mejora a nadie | \((11,6),(15,4)\) |
| 10 | \((11,6)\) | vieja, se descarta | \((15,4)\) |
| 11 | \((15,4)\) | vieja, se descarta | vacía |
De las once parejas que salieron, cuatro no valían. Por eso la cola puede llegar a tener \(|E|\) parejas y no \(|V|\), y por eso el costo se escribe \(O(|E| \log |E|)\), que es lo mismo que \(O(|E| \log |V|)\).
Lo que cuesta¶
| versión de Prim | costo |
|---|---|
| búsqueda lineal del mínimo | \(O(\lvert V\rvert^2)\) |
| cola de prioridad binaria | \(O(\lvert E\rvert \log \lvert V\rvert)\) |
| montón de Fibonacci | \(O(\lvert E\rvert + \lvert V\rvert \log \lvert V\rvert)\) |
El montón de Fibonacci mejora la cota pero tiene constantes grandes, y en la práctica no se usa.
Kruskal o Prim¶
| Kruskal | Prim | |
|---|---|---|
| qué recorre | las aristas, ordenadas | el borde del árbol |
| estructura | conjuntos disjuntos | cola de prioridad |
| cómo llega el grafo | lista de aristas | listas de adyacencia |
| costo | \(O(\lvert E\rvert \log \lvert E\rvert)\) | \(O(\lvert E\rvert \log \lvert V\rvert)\), o \(O(\lvert V\rvert^2)\) |
| le conviene | grafos ralos | grafos densos |
Dibujados paso a paso sobre el mismo grafo, los dos se distinguen de una mirada: lo que Kruskal lleva aceptado son varios pedazos sueltos que solo al final se pegan, mientras que lo de Prim es siempre una sola pieza que se estira. Esa es la diferencia entre descubrir un corte nuevo cada vez y mantenerlo fijo en el borde del árbol.
En un grafo denso, con \(|E|\) cerca de \(|V|^2\), la búsqueda lineal de Prim cuesta \(|V|^2\) sin logaritmo ni estructura de por medio, mientras que ordenar \(|V|^2\) aristas sale más caro. En un grafo ralo pasa lo contrario, y además Kruskal no necesita tener el grafo armado: le basta la lista de aristas tal como viene de la entrada, que es como suelen llegar los problemas de juez.
Eso explica dónde corre cada uno. Kruskal es el que está dentro del agrupamiento por enlace simple y de la segmentación de imágenes: ahí el dato son las diferencias entre pares y lo que se busca son los pedazos que quedan al dejar de unir, que es justo lo que Kruskal tiene a medio camino. Prim sirve cuando el peso no está escrito sino que se calcula al momento, como la distancia entre \(n\) puntos del plano: con búsqueda lineal cuesta \(|V|^2\) sin guardar una sola arista, mientras que Kruskal tendría que generar y ordenar las \(n(n-1)/2\). Y el árbol de Prim crece desde un punto, que es el orden en que un tendido se instala en terreno.
Lo que no cambia el árbol¶
Sumarle una constante \(c\) a todos los pesos no cambia el árbol mínimo, porque todo árbol de cubrimiento tiene exactamente \(|V| - 1\) aristas y entonces a todos les sube lo mismo, \((|V|-1)c\). Multiplicar todos los pesos por una constante positiva tampoco lo cambia. Y los pesos negativos no lo rompen: la propiedad de corte compara pesos, nunca los suma, así que no supone signos. Esa es una diferencia de fondo con Dijkstra.
Para el árbol de cubrimiento máximo sirve el mismo código con las aristas ordenadas al revés, o con los pesos negados.
Lo que el árbol mínimo sí garantiza¶
Entre cada pareja de vértices, el camino que los une dentro del árbol mínimo tiene la propiedad de que su arista más pesada es la menor posible: ningún otro camino del grafo entre esos dos vértices consigue una arista máxima más pequeña. Sobre el grafo de la sesión eso se comprueba en las \(21\) parejas. De \(0\) a \(6\), por ejemplo, el camino del árbol pasa por \((0,1)\), \((1,4)\) y \((4,6)\), con pesos \(7\), \(7\) y \(9\), y ningún camino del grafo llega a \(6\) sin pasar por una arista de peso \(9\) o más.
Esa propiedad es lo que hace al árbol mínimo útil en problemas de cuello de botella, del tipo qué tan pesado es el camión más pesado que puede ir de aquí a allá.
El árbol de caminos más cortos es otro¶
Lo que el árbol mínimo no da son las distancias. El ejemplo más pequeño es un triángulo: \(a - b\) con peso \(4\), \(b - c\) con peso \(3\) y \(a - c\) con peso \(6\).
- El árbol mínimo es \(\{(a,b), (b,c)\}\) y pesa \(7\).
- El árbol de caminos más cortos desde \(a\) es \(\{(a,b), (a,c)\}\) y pesa \(10\).
Al mirar \(c\), Prim compara el \(3\) que cuesta engancharlo desde \(b\); Dijkstra compara \(4+3\) contra el \(6\) de la arista directa y se queda con el \(6\). En el árbol mínimo, ir de \(a\) a \(c\) cuesta \(7\), que es más que la arista que se descartó. Los dos algoritmos se parecen en el código y resuelven problemas distintos.
Errores comunes¶
- Creer que el árbol es único. Con pesos repetidos puede haber varios, todos del mismo peso total.
- No ver que el grafo no es conexo. Los dos algoritmos terminan con menos de \(|V| - 1\) aristas. Eso se detecta y se reporta, en vez de imprimir la suma de los pedazos.
- Usar Dijkstra por error. Minimiza la suma del camino desde la raíz, no el precio de cada arista que entra.
- Olvidar que el peso total puede desbordar. Con \(200\,000\) aristas de pesos de hasta \(2^{31}\), la suma no cabe en un entero de 32 bits.
- Ordenar y después no parar. Kruskal puede seguir mirando aristas después de completar el árbol. No cambia el resultado, pero en un problema con \(|E|\) grande es trabajo regalado.
El código de la clase¶
union_find.py trae make_set, find_set y union
con las dos heurísticas, y el ejemplo de nueve elementos con el estado de p y
rango después de cada unión.
kruskal.py tiene el algoritmo de Kruskal sobre una lista
de aristas, con el grafo de la sesión en el main.
prim.py tiene las dos versiones de Prim, la de búsqueda
lineal y la de cola de prioridad, sobre listas de adyacencia.
20262-agra-darkroads.py y
20262-agra-darkroads.cpp son la solución
del problema de juez de la sesión.
Ejercicios¶
A mano¶
- Baje el peso de \((3,4)\) de \(15\) a \(4\) y vuelva a correr Kruskal. ¿Cambia el árbol? ¿Cuál arista sale?
- Suba el peso de \((2,4)\) de \(5\) a \(7\), con lo que empata con \((0,1)\) y \((1,4)\). Muestre dos árboles distintos del mismo peso.
- Corra Prim desde la raíz \(6\) y compare las seis aristas con las de la traza desde \(0\).
- ¿Cuáles aristas del grafo de la sesión están en todo árbol mínimo? Justifique cada una exhibiendo un corte.
- Agréguele a
kruskalla detección de grafo que no es conexo.
Las tres primeras son las de la sesión. Para la primera, al bajar \((3,4)\) a \(4\) esa arista pasa a ser la segunda de la lista ordenada y entra; la que sale es la que cerraba el ciclo que se forma, y el peso baja. Para la cuarta, una arista está en todos los árboles mínimos cuando es la única más liviana de algún corte, y el corte más fácil de exhibir es el que separa a uno de sus extremos del resto.
En parejas¶
Construya un grafo de seis vértices donde Kruskal y Prim desde la raíz \(0\) acepten las aristas en órdenes distintos y terminen en el mismo árbol, y otro donde terminen en árboles distintos del mismo peso. Intercambie con la pareja de al lado y verifique el del otro con el algoritmo que no usó.
UVa 11631, Dark roads¶
Alumbrar un metro de calle cuesta un dólar por noche. El gobierno quiere apagar calles para gastar menos, con la condición de que entre dos cruces cualesquiera siga quedando un camino iluminado. Se pide cuánto es lo máximo que puede ahorrar por noche.
Cada caso empieza con dos enteros, el número de cruces \(m\) y el número de calles \(n\), con \(1 \leq m \leq 200\,000\) y \(m - 1 \leq n \leq 200\,000\), y siguen \(n\) tripletas \(x\), \(y\), \(z\): una calle entre \(x\) y \(y\) de \(z\) metros, con los cruces numerados desde \(0\). La entrada termina con \(m = n = 0\). El grafo de cada caso es conexo y el total de metros cabe en \(2^{31}\).
Enunciado y envío: https://vjudge.net/problem/UVA-11631. La página pide cuenta.
El caso de ejemplo del enunciado es el grafo de esta sesión, con sus once calles sumando \(90\) metros. El árbol mínimo pesa \(39\), así que la respuesta es \(90 - 39 = 51\): lo que se ahorra es todo lo que no entra al árbol.
La entrada del caso de ejemplo¶
Antes del código conviene ver la entrada al lado del dibujo. El caso del enunciado es este:
7 11
0 1 7
0 3 5
1 2 8
1 3 9
1 4 7
2 4 5
3 4 15
3 5 6
4 5 8
4 6 9
5 6 11
0 0
| la línea | qué dice | en el dibujo |
|---|---|---|
7 11 |
siete cruces y once calles | el tamaño del grafo |
0 1 7 |
calle entre el cruce 0 y el 1, de siete metros | la arista \((0,1)\) con peso \(7\) |
3 4 15 |
calle entre el 3 y el 4, de quince metros | la arista \((3,4)\), la más larga |
0 0 |
no viene otro caso | fin de la entrada |
Las once tripletas son las once aristas del grafo de la sesión, en el mismo
orden en que aparecen en la tabla de pesos. Los cruces vienen numerados desde
\(0\), de modo que el grafo tiene vértices \(0\) a \(m-1\) y no hace falta restarle
uno a nada. Antes de la línea 0 0 puede venir otro caso completo, con su
propia primera línea y sus propias calles.
La salida es una línea por caso. Para este, las once calles suman \(90\) metros, el árbol de cubrimiento mínimo pesa \(39\), y lo que se puede apagar es \(90 - 39 = 51\).
Cómo leer la entrada¶
int m, n;
scanf("%d %d", &m, &n);
while (m != 0) {
vector<pair<int, pair<int, int> > > aristas(n);
long long total = 0;
for (int i = 0; i < n; i++) {
int x, y, z;
scanf("%d %d %d", &x, &y, &z);
aristas[i] = make_pair(z, make_pair(x, y));
total = total + z;
}
/* aqui se corre Kruskal y se imprime total - peso del MST */
scanf("%d %d", &m, &n);
}
Guardar la arista como la pareja (peso, (x, y)) deja que sort la ordene por
peso sin escribir un comparador, porque las parejas se comparan primero por su
primera componente. total tiene que ser long long.
La solución¶
Las dos hacen lo mismo: suman todos los pesos, corren Kruskal con conjuntos disjuntos y restan. Medidas sobre un caso generado de \(200\,000\) cruces y \(200\,000\) calles, lo más grande que admite el enunciado, con la mejor de tres corridas:
| un caso | cinco casos | |
|---|---|---|
| Python | 1,06 s | 3,14 s |
| C++ | 0,12 s | 0,61 s |
Sobre un solo caso la diferencia es de nueve veces, no de las veinte que se
midieron en el problema de la sesión anterior. La razón es que aquí el trabajo pesado es
ordenar \(200\,000\) aristas, y el sort de Python corre en C; lo que queda en
el intérprete es un recorrido de las aristas con dos find_set por arista.
UVa 10034, Freckles¶
Hay \(n \leq 100\) pecas en la espalda de alguien, cada una con sus coordenadas \((x, y)\) reales, y se quieren unir con trazos rectos gastando la menor cantidad de tinta, de modo que de cualquier peca se pueda llegar a cualquier otra. Se pide la longitud total con dos decimales. La entrada trae primero el número de casos y una línea en blanco entre uno y otro.
Enunciado y envío: https://vjudge.net/problem/UVA-10034. La página pide cuenta.
Es un árbol de cubrimiento mínimo sobre un grafo completo que no viene dado: la arista entre dos pecas existe siempre y su peso es la distancia euclidiana. Con \(n \leq 100\) son a lo sumo \(4\,950\) aristas, que caben de sobra; también sirve Prim con búsqueda lineal, que en un grafo denso como este es la opción natural. La trampa está en la entrada, con sus líneas en blanco y sus números reales.
UVa 11228, Transportation system¶
Hay \(n \leq 1000\) ciudades con coordenadas enteras. Dos ciudades están en el mismo estado si la distancia entre ellas es a lo sumo \(r\), y esa relación se propaga: si \(A\) está con \(B\) y \(B\) con \(C\), las tres están en el mismo estado. Dentro de un estado se construyen carreteras y entre estados vías férreas, y se quiere lo mínimo de cada cosa para que todas las ciudades queden conectadas. Se pide, por caso, el número de estados y los dos totales redondeados.
Enunciado y envío: https://vjudge.net/problem/UVA-11228. La página pide cuenta.
Es el mismo Kruskal, con las aristas del árbol repartidas en dos sumas según su longitud pase o no de \(r\), y el número de estados sale de contar cuántas aristas del árbol son largas: si el árbol tiene \(n-1\) aristas y \(k\) de ellas son vías férreas, los estados son \(k+1\). Con \(n = 1000\) son casi medio millón de aristas, así que conviene ordenarlas una sola vez.
Referencias¶
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. Introduction to Algorithms, 3rd ed. MIT Press, 2009. Capítulo 23, páginas 624 a 642.
- Borůvka, O. O jistém problému minimálním. Práce Moravské přírodovědecké společnosti, 3, 1926, páginas 37 a 58.
- Kruskal, J. B. On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society, 7(1), 1956, páginas 48 a 50.
- Prim, R. C. Shortest connection networks and some generalizations. Bell System Technical Journal, 36(6), 1957, páginas 1389 a 1401.
- Halim, S., Halim, F., Effendy, S. Competitive Programming 4. Lulu, 2020. Capítulo 4.