En la lección anterior aprendimos a movernos por la red de Rutalia al mínimo coste. Esta lección plantea un problema distinto que suena parecido y se confunde constantemente con él: no queremos ir de un sitio a otro, queremos conectarlo todo gastando lo mínimo. Rutalia va a desplegar una red de casilleros inteligentes en las 9 zonas de la ciudad, unidos por fibra óptica tendida a lo largo de las calles: ¿qué tramos cablear para que todos los casilleros queden comunicados con el menor coste total de obra? La respuesta es el árbol de expansión mínima (MST), y trae dos regalos: la segunda semilla de 01-04 —el union-find que sostiene a Kruskal— y una lección profunda sobre algoritmos voraces: aquí, a diferencia de los contraejemplos de 02-02, la avaricia es demostrablemente óptima.

1. Árboles de expansión: definición y por qué el mínimo importa
2. La propiedad de corte: por qué lo voraz aquí SÍ es óptimo
3. Kruskal: ordenar aristas y cobrar la semilla del union-find
4. Prim: hacer crecer el árbol con un heap
5. Kruskal vs Prim: tabla y criterio de elección
6. MST vs caminos mínimos: el árbol de Dijkstra NO es el MST

Un árbol de expansión (spanning tree) de un grafo conexo G = (V, E) es un subconjunto de aristas que conecta todos los vértices y no contiene ciclos. Como todo árbol, tiene exactamente n − 1 aristas: ni una más (habría ciclo) ni una menos (quedaría algo suelto). Un grafo tiene en general muchísimos árboles de expansión; el árbol de expansión mínima (MST) es el de menor suma de pesos.

¿Por qué "árbol"? Piensa en la fibra de los casilleros: si el cableado formara un ciclo, podrías quitar cualquier arista del ciclo y todo seguiría conectado — habrías pagado una zanja inútil. La solución óptima de un problema de conexión pura nunca contiene ciclos, luego es un árbol.

Para la red de casilleros reutilizamos el grafo canónico de 03-01 reinterpretando los pesos: donde antes leíamos "minutos de furgoneta", ahora leemos "coste de obra en miles de euros" (proporcional a la longitud del tramo, así que los mismos números sirven). La pregunta: ¿qué 8 tramos de los 15 se cablean?

Aplicaciones del mismo patrón, más allá de la fibra: redes eléctricas y de agua, diseño de circuitos, agrupamiento de datos (el clustering jerárquico de 05-05 tiene al MST escondido dentro), y aproximaciones al TSP (el famoso 2-aproximado se construye paseando por un MST).

En 02-02 vimos algoritmos voraces estrellarse: el "vecino más cercano" del TSP daba 43,1 km frente al óptimo de 35,22, y la mochila por valor/peso fallaba con contraejemplos de tres objetos. La pregunta honesta es: ¿por qué aquí va a funcionar elegir "la arista más barata"? La respuesta tiene nombre propio:

Propiedad de corte. Divide los vértices en dos grupos no vacíos (S, V∖S) — un corte. Entre todas las aristas que cruzan el corte, sea e la de peso mínimo (supón pesos distintos para simplificar). Entonces e pertenece a todo MST.

Demostración por intercambio (la técnica clásica para justificar voraces): supón un árbol de expansión T que no contiene a e = {u, v}. Como T conecta u con v, contiene un camino entre ambos, y ese camino cruza el corte por al menos una arista f (≠ e, y por definición de e: peso(f) > peso(e)). Quita f y añade e: el resultado T′ sigue conectando todo (e re-empalma las dos mitades que separó quitar f), sigue teniendo n−1 aristas, y pesa menos que T. Luego T no era mínimo. ∎

La moraleja general, que vale su peso en oro: lo voraz no es fiable ni sospechoso por defecto; es correcto exactamente cuando el problema tiene una estructura de intercambio que lo garantiza. El MST la tiene (los matemáticos dicen que las aristas sin ciclos forman una matroide); el TSP y la mochila 0/1, no. Dijkstra (03-03) era el otro voraz con certificado: su invariante era también un argumento de intercambio disfrazado.

Ambos algoritmos de esta lección son aplicaciones directas de la propiedad de corte; solo cambia qué cortes miran.

Estrategia de Kruskal: recorrer las aristas de más barata a más cara, aceptando cada una salvo que forme ciclo con las ya aceptadas. La propiedad de corte lo respalda: cuando una arista {u, v} es aceptada, es la más barata que cruza el corte "componente de u frente al resto" (todas las más baratas ya se procesaron y no separaban esas mitades).

¿Y cómo se detecta "forma ciclo" eficientemente? Una arista forma ciclo si sus dos extremos ya están en la misma componente. Es decir: necesitamos pertenencia a componentes con aristas que van llegando una a una — exactamente el caso que en 03-02 dijimos que BFS resuelve mal y union-find resuelve de maravilla. La semilla de 01-04, cobrada:

Traza completa sobre la red de casilleros — el "vídeo" del algoritmo:

Coste total de la obra: 37.000 €, frente a los 87.000 que costaría cablear los 15 tramos. Nótese qué rechaza Kruskal: justo las aristas "redundantes" que cerrarían anillos — incluida la avenida ALM–CEN de 12, que ni llega a examinarse.

Complejidad: ordenar domina, O(m log m) = O(m log n); las 2m operaciones de union-find cuestan O(m · α(n)) — esa α, la inversa de Ackermann que vimos en 01-04, es ≤ 4 para cualquier grafo del mundo físico. En la práctica: "ordenar + casi gratis".

Prim aplica la misma propiedad de corte con otra táctica: mantener un único árbol que crece desde un nodo inicial, añadiendo en cada paso la arista más barata que sale del árbol hacia fuera (el corte es siempre "árbol actual frente al resto"). ¿Y quién entrega "la arista más barata de la frontera"? Otra vez el heap de 01-04 — el mismo motor que Dijkstra, con una diferencia crucial en la prioridad:

Compara mentalmente con el Dijkstra de 03-03: mismo esqueleto (heap, cerrados, borrado perezoso), pero la tupla del heap lleva peso_de_la_arista en vez de distancia_acumulada. Ese único cambio transforma "estar cerca del origen" en "estar cerca del árbol". De nuevo la gran familia: cola→BFS, pila→DFS, heap por distancia→Dijkstra, heap por arista→Prim.

Complejidad con heap binario: cada arista entra a lo sumo una vez al heap ⇒ O(m log n), como Kruskal. Con matriz de adyacencia y sin heap existe una variante O(n²), que en grafos densos (m ≈ n²) es de hecho mejor.

Para la red de casilleros (dispersa: 15 aristas, 9 nodos) ambos son instantáneos e idénticos en resultado; a escala de ciudad, Kruskal suele ser el más cómodo en grafos viarios dispersos, y Prim O(n²) gana en grafos densos tipo "matriz de distancias todo-con-todo". Si los pesos son todos distintos, el MST es único y ambos devuelven exactamente el mismo árbol; con empates pueden diferir en aristas, nunca en el coste total.

Dijkstra también produce un árbol (el de padres, con n−1 aristas). Es tentador creer que ese árbol es el MST: no lo es, y confundirlos es un error de diseño caro. Optimizan cosas distintas:

• Árbol de Dijkstra desde s: minimiza la distancia de s a cada nodo. Sirve al repartidor que sale del almacén.
• MST: minimiza la suma total de las aristas elegidas. Sirve al que paga las zanjas de la fibra.

Contraejemplo mínimo, tres zonas:

• MST: {A–B, B–C}, coste total 2 (descarta la arista de 1,5).
• Árbol de Dijkstra desde A: hasta C conviene la directa (1,5 < 1+1), así que {A–B, A–C}, coste total 2,5.

Ninguno "se equivoca": en el MST, ir de A a C cuesta 2 (rodeando por B) aunque la red entera salga más barata; en el árbol de Dijkstra, C está a 1,5 pero la infraestructura total es más cara. Y en la red de Rutalia la diferencia es escandalosa: el árbol de Dijkstra desde ALM pesa 46 (usa ALM–EST 7, MER–UNI 6, RIO–PAR 8, EST–IND 9), mientras el MST pesa 37 (prefiere EST–UNI 3, UNI–HOS 5, IND–HOS 6, PAR–HOS 7). Un 24% más caro por optimizar la métrica equivocada.

• Usar el árbol de Dijkstra como red de infraestructura (o el MST como tabla de rutas): el contraejemplo de tres nodos debería bastar; en Rutalia la confusión cuesta un 24% de sobrecoste o rutas absurdas. Primero decide qué se minimiza, luego elige algoritmo.
• Detectar ciclos en Kruskal con BFS/DFS sobre las aristas aceptadas: correcto pero O(n) por arista ⇒ O(n·m) total. El union-find lo deja en α(n) por consulta; para eso lo sembramos en 01-04.
• Olvidar la compresión de caminos o la unión por rango: el union-find degenera en listas y find se vuelve O(n). Son cuatro líneas; escríbelas siempre.
• No detenerse al llegar a n−1 aristas en Kruskal: el resultado sigue siendo correcto (todo lo demás se rechazaría), pero se procesan aristas caras inútilmente. El break es gratis.
• Aplicar MST a un grafo no conexo: no existe árbol de expansión; Kruskal devuelve silenciosamente un bosque de expansión mínima. Comprueba len(mst) == n - 1 al terminar y decide qué significa el déficit en tu problema (en Rutalia: zonas sin fibra).
• Consejo: cuando un voraz te tiente, busca el argumento de intercambio ("si la solución óptima no usara mi elección, la cambio y no empeora"). Si lo encuentras, tienes algoritmo y demostración; si no aparece, sospecha — recuerda el vecino más cercano del TSP.

1. La fibra que faltaba. El ayuntamiento prohíbe abrir zanja en el tramo UNI–HOS (coste 5). Recalcula el MST con Kruskal sin esa arista. ¿Cuánto encarece la prohibición? ¿Qué arista entra en sustitución y por qué esa, a la luz de la propiedad de corte?
2. Arista segura a mano. Sin ejecutar ningún algoritmo, usa la propiedad de corte con S = {IND} para demostrar qué arista incidente a IND está en todo MST de la red de casilleros. Verifica contra la traza de Kruskal.
3. Kruskal como agrupador. Si detienes Kruskal cuando quedan exactamente 3 componentes, obtienes una partición de las zonas en 3 grupos "naturalmente cercanos" (así funciona el clustering de enlace simple, que reaparecerá en 05-05). Modifica kruskal para aceptar un parámetro k_componentes y calcula los 3 grupos de la red de casilleros.

Ejercicio 1:

Entra MER–UNI (6) en lugar de UNI–HOS (5). Explicación por corte: al eliminar UNI–HOS, en el momento en que Kruskal tiene los fragmentos {ALM,RIO,MER,CEN,HOS} y {EST,UNI}, las aristas que cruzan ese corte son MER–UNI (6), RIO–CEN… no —RIO y CEN están del mismo lado—; cruzan MER–UNI (6), UNI–CEN (8) y ALM–EST (7): la mínima disponible pasa a ser MER–UNI, y la propiedad de corte la convierte en obligatoria. El MST solo empeora en la diferencia 6 − 5 = 1.

Ejercicio 2:

Con S = {IND}, las aristas que cruzan el corte son todas las incidentes a IND: EST–IND (9) e IND–HOS (6). La mínima es IND–HOS (6), luego pertenece a todo MST — sin ejecutar nada. La traza de Kruskal lo confirma (IND–HOS aceptada; EST–IND ni se considera antes de completar el árbol). Este truco del "corte de un solo nodo" da gratis una arista segura por cada vértice: la más barata de cada nodo siempre está en el MST (con pesos distintos).

Ejercicio 3:

Cada unión reduce el número de componentes en 1 (empezamos con n = 9); por eso basta contar aceptadas. Los grupos resultantes son elocuentes: el núcleo urbano densamente conectado por un lado, y el Polígono y el Parque —las zonas periféricas de grado 2 que venimos señalando desde 03-01— como satélites. Kruskal no solo construye redes: revela estructura.

El MST responde a la pregunta de infraestructura —conectarlo todo al mínimo coste total— y su solución voraz no es un golpe de suerte: la propiedad de corte, demostrada por intercambio, certifica que la arista más barata de cualquier corte es obligatoria. Kruskal la explota ordenando aristas y vigilando ciclos con el union-find de 01-04 (segunda semilla cobrada: las dos promesas de aquella lección están saldadas); Prim la explota haciendo crecer un árbol con el mismo heap de Dijkstra pero priorizando el peso de la arista, no la distancia acumulada. Y hemos deslindado con un contraejemplo lo que el MST no es: el árbol de Dijkstra optimiza distancias desde un origen, el MST optimiza la suma — confundirlos costaría a Rutalia un 24% en zanjas. Hasta aquí, nuestras aristas medían coste de atravesarlas. La próxima lección les da un significado nuevo: capacidad — cuántos paquetes por hora caben por cada calle. Con ello entramos en los problemas de flujo máximo (03-05): cuál es el caudal máximo de reparto entre el almacén y un barrio en hora punta, y cuál es el cuello de botella que lo limita.