Calculadora de Árbol de Expansión Mínimo

Bienvenido a la Calculadora de Árbol de Expansión Mínimo, una herramienta interactiva para computar el MST de un grafo ponderado utilizando el algoritmo de Kruskal o el de Prim. Ya sea que estés estudiando teoría de grafos, diseñando infraestructura de red u optimizando la asignación de recursos, esta calculadora proporciona una exploración visual y paso a paso de dos algoritmos fundamentales en la optimización combinatoria.

¿Qué es un Árbol de Expansión Mínimo (MST)?

Un Árbol de Expansión Mínimo de un grafo conectado, no dirigido y ponderado es un subconjunto de aristas que:

• Conecta todos los vértices juntos (expansión)
• No contiene ciclos (árbol)
• Tiene el peso total de aristas mínimo posible

Para un grafo con V vértices, un MST siempre tiene exactamente V - 1 aristas. Si el grafo está desconectado, el resultado es un Bosque de Expansión Mínimo: una colección de MSTs para cada componente conectado.

Algoritmo de Kruskal

El algoritmo de Kruskal es un algoritmo voraz basado en aristas que construye el MST procesando las aristas en orden de peso creciente. Utiliza una estructura de datos Union-Find (Unión-Búsqueda) para detectar ciclos de manera eficiente.

Pseudocódigo de Kruskal

Algoritmo de Prim

El algoritmo de Prim es un algoritmo voraz basado en vértices que hace crecer el MST desde un vértice inicial. En cada paso, añade la arista más barata que conecta un vértice del árbol con un vértice fuera del árbol.

Pseudocódigo de Prim

Kruskal vs Prim: ¿Cuándo usar cuál?

Cómo usar esta calculadora

1. Define las aristas de tu grafo: Ingresa las aristas en el formato nodo1, nodo2, peso, una por línea. El MST opera en grafos no dirigidos, por lo que cada arista funciona en ambas direcciones.
2. Elige un algoritmo: Selecciona Kruskal para grafos dispersos o Prim para grafos densos. Ambos producen un MST óptimo.
3. Establece el nodo de inicio (solo Prim): Opcionalmente especifica dónde comienza el algoritmo de Prim. Esto afecta el orden de selección de las aristas pero no el peso total del MST.
4. Computar MST: Haz clic en "Buscar MST" para ejecutar el algoritmo. Explora la visualización interactiva, la tabla de aristas y la traza paso a paso.
5. Recorre los pasos: Usa los botones Siguiente/Anterior para ver el algoritmo ejecutarse paso a paso, con resaltado en el canvas en tiempo real.

Entendiendo los resultados

Tabla de Aristas del MST

Muestra cada arista seleccionada para el MST, en el orden en que fueron añadidas, junto con los pesos individuales y el peso total del MST.

Visualización del Grafo

El canvas interactivo muestra tu grafo con elementos codificados por colores:

• Nodos y aristas verdes = Parte del MST
• Resaltados naranjas = Actualmente bajo examen
• Elementos grises = Aún no forman parte del MST

Traza paso a paso

Muestra cada decisión del algoritmo: qué arista se examina, si fue aceptada o rechazada (y por qué), y el estado actual de la construcción del MST.

Aplicaciones del MST en el mundo real

Diseño de Redes

La aplicación más clásica. Al conectar nodos (ciudades, servidores, dispositivos eléctricos) con una longitud total mínima de cable, fibra o tubería, el MST proporciona la solución óptima. Las empresas de telecomunicaciones utilizan algoritmos basados en MST para minimizar los costos de infraestructura.

Análisis de Conglomerados

En aprendizaje automático y ciencia de datos, la agrupación basada en MST (como el clustering de enlace simple) agrupa puntos de datos eliminando las aristas más largas del MST. Esto produce grupos naturales sin necesidad de especificar previamente el número de grupos.

Segmentación de Imágenes

Los algoritmos de visión artificial utilizan MST para segmentar imágenes en regiones significativas. Los píxeles son nodos, los pesos de las aristas representan la diferencia en color/intensidad, y cortar aristas del MST separa objetos distintos.

Algoritmos de Aproximación

El MST proporciona una aproximación de factor 2 para el Problema del Viajante (TSP) métrico. El peso del MST es un límite inferior del recorrido óptimo del TSP, y duplicar las aristas del MST da un recorrido dentro del doble de lo óptimo.

Diseño de Circuitos

El diseño de chips VLSI utiliza MST (a través de variantes del árbol de Steiner) para minimizar la longitud total de los cables que conectan los componentes en una placa de circuito, reduciendo el retraso de la señal y el costo de fabricación.

Propiedades clave del MST

• Propiedad del Corte: Para cualquier corte del grafo, la arista de peso mínimo que cruza el corte está en el MST.
• Propiedad del Ciclo: Para cualquier ciclo en el grafo, la arista de peso máximo en el ciclo NO está en el MST (asumiendo pesos únicos).
• Unicidad: Si todos los pesos de las aristas son distintos, el MST es único. Con pesos duplicados, puede haber múltiples MSTs válidos con el mismo peso total.
• Subgrafo: El MST es un subgrafo con V-1 aristas y sin ciclos.

Preguntas Frecuentes

¿Qué es un Árbol de Expansión Mínimo (MST)?

Un Árbol de Expansión Mínimo es un subconjunto de aristas de un grafo conectado, no dirigido y ponderado que conecta todos los vértices con el peso total de aristas mínimo posible, sin formar ciclos. Un MST tiene exactamente V-1 aristas para un grafo con V vértices.

¿Cuál es la diferencia entre el algoritmo de Kruskal y el de Prim?

El algoritmo de Kruskal se basa en las aristas: ordena todas las aristas por peso y añade vorazmente aquellas que no crean ciclos, utilizando una estructura de datos Union-Find. El algoritmo de Prim se basa en los vértices: hace crecer el MST desde un nodo inicial añadiendo siempre la arista más barata que conecte el árbol con un nuevo vértice, utilizando una cola de prioridad. Ambos producen MSTs óptimos pero pueden diferir en el orden de selección de las aristas.

¿Cuándo debo usar el algoritmo de Kruskal frente al de Prim?

Kruskal es generalmente mejor para grafos dispersos (pocas aristas en relación a los nodos) con una complejidad temporal O(E log E). Prim es mejor para grafos densos con una complejidad temporal O(E log V) usando un montículo binario. Para grafos muy densos, Prim con un montículo de Fibonacci logra O(E + V log V).

¿Puede un grafo tener múltiples MSTs válidos?

Sí, un grafo puede tener múltiples MSTs válidos si hay aristas con pesos iguales. Los diferentes MSTs tendrán el mismo peso total pero pueden incluir aristas diferentes. Kruskal y Prim pueden producir diferentes MSTs para el mismo grafo, pero ambos tendrán el mismo peso total mínimo.

¿Cuáles son las aplicaciones del MST en el mundo real?

Los MSTs se utilizan en el diseño de redes (minimizando la longitud de cables/fibra), diseño de placas de circuitos, análisis de conglomerados, segmentación de imágenes, construcción de taxonomías, aproximación de problemas NP-duros como el Problema del Viajante (TSP) y la construcción de redes de carreteras/tuberías/eléctricas al costo mínimo.

¿Funciona el MST en grafos desconectados?

Un verdadero MST requiere un grafo conectado. Si el grafo está desconectado, los algoritmos producirán un Bosque de Expansión Mínimo: una colección de MSTs, uno para cada componente conectado. Esta calculadora indicará cuándo el grafo no está totalmente conectado.

Recursos Adicionales

• Árbol de expansión mínimo - Wikipedia
• Algoritmo de Kruskal - Wikipedia
• Algoritmo de Prim - Wikipedia