Árboles de expansión mínima: Prim
Conecta todos los nodos lo más barato posible.
Prim = Dijkstra con el PESO DE LA ARISTA en el heap, no la distancia.
Haz crecer el árbol a través del corte
- Empieza con un nodo; todo lo demás afuera
- Agrega repetidamente la arista más barata que cruza árbol ↔ afuera
- El nodo nuevo trae aristas nuevas que cruzan; repite hasta unir los V nodos
- V−1 aristas, sin ciclos, peso total mínimo
Mira crecer el árbol
Verde = en el árbol · azul punteado = candidatas del corte · naranja = arista más barata elegida.
El total sube la cantidad más chica posible en cada paso → 15.
"Mínima" vale 3×
La misma conectividad, las mismas V−1 aristas: el árbol arbitrario pesa ~3× más que el MST.
Por qué lo avaro es óptimo: la propiedad del corte
- Cualquier corte parte los nodos en dos; la arista más barata que cruza está en algún MST
- El corte de Prim = "árbol vs afuera" → cada arista que agrega es demostrablemente segura
- El mismo teorema justifica a Kruskal (con otros cortes)
- El MST NO es un árbol de caminos mínimos — no rutees sobre él
Para llevar
Un solo cambio en la llave del heap convierte caminos mínimos en conexiones más baratas.
Las matemáticas de las redes baratas: redes eléctricas, cables, tuberías, clustering, cotas para TSP.
Siguiente: Kruskal construye el mismo árbol al revés — con union-find.