Árbol de expansión mínimo
Un árbol de expansión mínimo ( MST ) o un árbol de expansión de peso mínimo es un subconjunto de los bordes de un gráfico no dirigido con ponderación de borde conectado que conecta todos los vértices juntos, sin ciclos y con el peso de borde total mínimo posible. [1] Es decir, es un árbol de expansión cuya suma de pesos de borde es lo más pequeña posible. De manera más general, cualquier gráfico no dirigido con ponderación de borde (no necesariamente conectado) tiene un bosque de expansión mínimo , que es una unión de los árboles de expansión mínimos para sus componentes conectados .
Hay muchos casos de uso para árboles de expansión mínimos. Un ejemplo es una empresa de telecomunicaciones que intenta instalar cable en un nuevo barrio. Si está obligado a enterrar el cable solo a lo largo de ciertos caminos (por ejemplo, carreteras), entonces habrá un gráfico que contenga los puntos (por ejemplo, casas) conectados por esos caminos. Algunos de los caminos pueden ser más costosos, porque son más largos o requieren que el cable se entierre más profundamente; estos caminos estarían representados por aristas con pesos más grandes. La moneda es una unidad aceptable para el peso de los bordes; no es necesario que las longitudes de los bordes obedezcan las reglas normales de geometría, como la desigualdad del triángulo . Un árbol de expansiónporque ese gráfico sería un subconjunto de esos caminos que no tiene ciclos pero aún conecta todas las casas; puede haber varios árboles de expansión posibles. Un árbol de expansión mínimo sería uno con el costo total más bajo, lo que representa la ruta menos costosa para tender el cable.
Puede haber varios árboles de expansión mínimos del mismo peso; en particular, si todos los pesos de los bordes de un gráfico dado son iguales, entonces cada árbol de expansión de ese gráfico es mínimo.
Si cada borde tiene un peso distinto, solo habrá un árbol de expansión mínimo único . Esto es cierto en muchas situaciones realistas, como el ejemplo anterior de la compañía de telecomunicaciones, donde es poco probable que dos rutas tengan exactamente el mismo costo. Esto también se generaliza a los bosques que se extienden.
De manera más general, si los pesos de los bordes no son todos distintos, entonces solo el (múltiple) conjunto de pesos en los árboles de expansión mínimos seguramente será único; es igual para todos los árboles de expansión mínimos. [2]
Si los pesos son positivos , entonces un árbol de expansión mínimo es de hecho un subgrafo de costo mínimo que conecta todos los vértices, ya que los subgrafos que contienen ciclos necesariamente tienen más peso total. [ cita requerida ]
