Árbol de expansión mínimo - Minimum spanning tree

Un gráfico plano y su árbol de expansión mínimo. Cada borde está etiquetado con su peso, que aquí es aproximadamente proporcional a su longitud.

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. 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. Algunas de las rutas pueden ser más caras, porque son más largas 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 del borde; 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ón para 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.

Propiedades

Posible multiplicidad

Si hay $n$ vértices en el gráfico, entonces cada árbol de expansión tiene $n - 1$ aristas.

Esta figura muestra que puede haber más de un árbol de expansión mínimo en un gráfico. En la figura, los dos árboles debajo del gráfico son dos posibilidades de árbol de expansión mínimo del gráfico dado.

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.

Unicidad

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 se generaliza también a los bosques que se extienden.

Prueba:

Asumir el contrario , que hay dos MSTs diferentes A y B .
Dado que A y B difieren a pesar de contener los mismos nodos, hay al menos un borde que pertenece a uno pero no al otro. Entre tales bordes, deja e ₁ sea el que tiene menos peso; esta elección es única porque los pesos de los bordes son todos distintos. Sin pérdida de generalidad, supongamos e ₁ se encuentra en una .
Como B es un MST, { e ₁ } B debe contener un ciclo C con e ₁ . ${\ Displaystyle \ cup}$
Como un árbol, A no contiene ciclos, por lo tanto C debe tener un borde e ₂ que no está en A .
Dado que e ₁ fue elegido como el único borde de menor peso entre los que pertenecen exactamente a uno de A y B , el peso de e ₂ debe ser mayor que el peso de e ₁ .
Como e ₁ y e ₂ son parte del ciclo C, al reemplazar e ₂ con e ₁ en B, se obtiene un árbol de expansión con un peso menor.
Esto contradice la suposición de que B es un MST.

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ínima seguramente será único; es igual para todos los árboles de expansión mínimos.

Subgrafo de costo mínimo

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.

Propiedad del ciclo

Para cualquier ciclo $C$ en el gráfico, si el peso de un borde $e$ de $C$ es mayor que los pesos individuales de todos los demás bordes de $C$ , entonces este borde no puede pertenecer a un MST.

Prueba: Supongamos lo contrario , es decir, que $e$ pertenece a un MST $T 1$ . Luego, al eliminar $e,$ se dividirá $T 1$ en dos subárboles con los dos extremos de $e$ en diferentes subárboles. El resto de $C$ vuelve a conectar los subárboles, por lo tanto, hay un borde $f$ de $C$ con extremos en diferentes subárboles, es decir, vuelve a conectar los subárboles en un árbol $T 2$ con un peso menor que el de $T 1$ , porque el peso de $f$ es menor que el peso de $e$ .

Cortar propiedad

Esta figura muestra la propiedad de corte de los MST. T es el único MST del gráfico dado. Si S = {A, B, D, E}, entonces VS = {C, F}, entonces hay 3 posibilidades del borde a través del corte (S, VS), son los bordes BC, EC, EF del original. grafico. Entonces, e es uno de los bordes de peso mínimo para el corte, por lo tanto S ∪ {e} es parte del MST T.

Para cualquier corte C del gráfico, si el peso de un borde e en el conjunto de cortes de C es estrictamente menor que los pesos de todos los demás bordes del conjunto de cortes de C , entonces este borde pertenece a todos los MST del gráfico. .

Prueba: Suponga que hay un MST T que no contiene e . Agregar e a T producirá un ciclo que cruza el corte una vez en e y vuelve a cruzar en otro borde e ' . Eliminación e ' obtenemos un árbol de expansión T ∖ {e'} ∪ {e} de peso estrictamente menor que T . Esto contradice la suposición de que T era un MST.

Con un argumento similar, si más de un borde tiene un peso mínimo en un corte, entonces cada uno de esos bordes está contenido en un árbol de expansión mínimo.

Ventaja de costo mínimo

Si el margen de costo mínimo e de un gráfico es único, entonces este margen se incluye en cualquier MST.

Prueba: si e no se incluyó en el MST, eliminar cualquiera de los bordes (de mayor costo) en el ciclo formado después de agregar e al MST, produciría un árbol de expansión de menor peso.

Contracción

Si T es un árbol de aristas MST, entonces podemos contraer T en un solo vértice mientras mantenemos el invariante que el MST del gráfico contraído más T da el MST para el gráfico antes de la contracción.

Algoritmos

En todos los algoritmos siguientes, m es el número de aristas en el gráfico y n es el número de vértices.

Algoritmos clásicos

El primer algoritmo para encontrar un árbol de expansión mínimo fue desarrollado por el científico checo Otakar Borůvka en 1926 (ver el algoritmo de Borůvka ). Su propósito era una cobertura eléctrica eficiente de Moravia . El algoritmo procede en una secuencia de etapas. En cada etapa, llamada paso de Boruvka , identifica un bosque F que consiste en el borde de peso mínimo incidente en cada vértice en el gráfico G , luego forma el gráfico como entrada para el siguiente paso. Aquí denota el gráfico derivado de G al contraer los bordes en F (por la propiedad Cut , estos bordes pertenecen al MST). Cada paso de Boruvka toma un tiempo lineal. Dado que el número de vértices se reduce al menos a la mitad en cada paso, el algoritmo de Boruvka toma O ( m log n ) tiempo. ${\ Displaystyle G_ {1} = G \ setminus F}$ ${\ Displaystyle G \ setminus F}$

Un segundo algoritmo es el algoritmo de Prim , que fue inventado por Vojtěch Jarník en 1930 y redescubierto por Prim en 1957 y Dijkstra en 1959. Básicamente, hace crecer el MST ( T ) un borde a la vez. Inicialmente, T contiene un vértice arbitrario. En cada paso, T se aumenta con un borde de menor peso ( x , y ) tales que x está en T y y todavía no está en T . Por la propiedad Cortar , todos los bordes agregados a T están en el MST. Su tiempo de ejecución es O ( m log n ) u O ( m + n log n ), dependiendo de las estructuras de datos utilizadas.

Un tercer algoritmo de uso común es el algoritmo de Kruskal , que también toma O ( m log n ) tiempo.

Un cuarto algoritmo, no tan comúnmente utilizado, es el algoritmo de eliminación inversa , que es el inverso del algoritmo de Kruskal. Su tiempo de ejecución es O ( m log n (log log n ) ³ ).

Los cuatro son algoritmos codiciosos . Puesto que se ejecutan en tiempo polinómico, el problema de encontrar tales árboles está en FP , y relacionados problemas de decisión tales como la determinación de si un borde particular es en el MST o determinar si el peso mínimo total excede de un cierto valor están en P .

Algoritmos más rápidos

Varios investigadores han intentado encontrar algoritmos más eficientes desde el punto de vista computacional.

En un modelo de comparación, en el que las únicas operaciones permitidas en los pesos de los bordes son comparaciones por pares, Karger, Klein y Tarjan (1995) encontraron un algoritmo aleatorio de tiempo lineal basado en una combinación del algoritmo de Borůvka y el algoritmo de eliminación inversa.

El algoritmo basado en comparación no aleatorio más rápido con complejidad conocida, de Bernard Chazelle , se basa en el montón suave , una cola de prioridad aproximada. Su tiempo de ejecución es O ( m α ( m , n )), donde α es el inverso funcional clásico de la función de Ackermann . La función α crece muy lentamente, por lo que a todos los efectos prácticos puede considerarse una constante no mayor que 4; por tanto, el algoritmo de Chazelle se acerca mucho al tiempo lineal.

Algoritmos de tiempo lineal en casos especiales

Gráficos densos

Si el gráfico es denso (es decir, m / n ≥ log log log n ), entonces un algoritmo determinista de Fredman y Tarjan encuentra el MST en el tiempo O ( m ). El algoritmo ejecuta una serie de fases. Cada fase ejecuta el algoritmo de Prim muchas veces, cada una para un número limitado de pasos. El tiempo de ejecución de cada fase es O ( m + n ). Si el número de vértices antes de una fase es , el número de vértices que quedan después de una fase es como máximo . Por lo tanto, se necesitan en la mayoría de las fases, lo que proporciona un tiempo de ejecución lineal para gráficos densos. ${\ Displaystyle n '}$ ${\ Displaystyle n '/ 2 ^ {m / n'}}$ ${\ Displaystyle \ log ^ {*} {n}}$

Hay otros algoritmos que funcionan en tiempo lineal en gráficos densos.

Pesos enteros

Si los pesos de los bordes son números enteros representados en binario, entonces se conocen algoritmos deterministas que resuelven el problema en O ( m + n ) operaciones enteras. Si el problema se puede resolver de forma determinista para un gráfico general en tiempo lineal mediante un algoritmo basado en comparación sigue siendo una cuestión abierta.

Árboles de decisión

Dado el gráfico G donde los nodos y los bordes son fijos pero se desconocen los pesos, es posible construir un árbol de decisión binario (DT) para calcular el MST para cualquier permutación de pesos. Cada nodo interno de la DT contiene una comparación entre dos bordes, por ejemplo, "es el peso del borde entre x y y más grande que el peso de la arista entre w y z ?". Los dos hijos del nodo corresponden a las dos posibles respuestas "sí" o "no". En cada hoja del DT, hay una lista de aristas de G que corresponden a un MST. La complejidad en tiempo de ejecución de un DT es el mayor número de consultas necesarias para encontrar el MST, que es solo la profundidad del DT. A DT para un gráfico de G se llama óptima si tiene la menor profundidad de todos los DTs correctos para G .

Para cada entero r , es posible encontrar árboles de decisión óptimos para todos los gráficos en r vértices mediante la búsqueda de fuerza bruta . Esta búsqueda se realiza en dos pasos.

A. Generación de todos los DT potenciales

Hay diferentes gráficos en r vértices. ${\ Displaystyle 2 ^ {r \ Choose 2}}$
Para cada gráfico, siempre se puede encontrar un MST utilizando comparaciones r ( r -1), por ejemplo, mediante el algoritmo de Prim .
Por tanto, la profundidad de un DT óptimo es menor que . ${\ Displaystyle r ^ {2}}$
Por tanto, el número de nodos internos en un DT óptimo es menor que . ${\ Displaystyle 2 ^ {r ^ {2}}}$
Cada nodo interno compara dos bordes. El número de aristas es como máximo, por lo que el número diferente de comparaciones es como máximo . ${\ Displaystyle r ^ {2}}$ ${\ Displaystyle r ^ {4}}$
Por lo tanto, el número de DT potenciales es menos de: . ${\ Displaystyle {(r ^ {4})} ^ {(2 ^ {r ^ {2}})} = r ^ {2 ^ {(r ^ {2} +2)}}}$

B. Identificación de los DT correctos Para comprobar si un DT es correcto, debe comprobarse en todas las posibles permutaciones de los pesos de los bordes.

El número de tales permutaciones es como máximo . ${\ displaystyle (r ^ {2})!}$
Para cada permutación, resuelva el problema de MST en el gráfico dado usando cualquier algoritmo existente y compare el resultado con la respuesta dada por el DT.
El tiempo de ejecución de cualquier algoritmo MST es como máximo , por lo que el tiempo total requerido para verificar todas las permutaciones es como máximo . ${\ Displaystyle (r ^ {2})}$ ${\ displaystyle (r ^ {2} +1)!}$

Por lo tanto, el tiempo total requerido para encontrar un óptimo DT para todos los gráficos con r vértices es: , que es inferior a: . ${\ displaystyle 2 ^ {r \ elige 2} \ cdot r ^ {2 ^ {(r ^ {2} +2)}} \ cdot (r ^ {2} +1)!}$ ${\ Displaystyle 2 ^ {2 ^ {r ^ {2} + o (r)}}}$

Algoritmo óptimo

Seth Pettie y Vijaya Ramachandran han encontrado un algoritmo de árbol de expansión mínimo basado en una comparación determinista óptima demostrablemente. La siguiente es una descripción simplificada del algoritmo.

Sea , donde n es el número de vértices. Encuentre todos los árboles de decisión óptimos en r vértices. Esto se puede hacer en el tiempo O ( n ) (ver Árboles de decisión arriba). ${\ Displaystyle r = \ log \ log \ log n}$
Divida el gráfico en componentes con un máximo de r vértices en cada componente. Esta partición utiliza un montón suave , que "corrompe" una pequeña cantidad de los bordes del gráfico.
Utilice los árboles de decisión óptimos para encontrar un MST para el subgráfico no dañado dentro de cada componente.
Contraiga cada componente conectado abarcado por los MST a un solo vértice y aplique cualquier algoritmo que funcione en gráficos densos en el tiempo O ( m ) a la contracción del subgrafo incorrupto
Vuelva a agregar los bordes dañados al bosque resultante para formar un subgrafo garantizado para contener el árbol de expansión mínimo, y más pequeño en un factor constante que el gráfico inicial. Aplique el algoritmo óptimo de forma recursiva a este gráfico.

El tiempo de ejecución de todos los pasos del algoritmo es O ( m ), excepto el paso de usar los árboles de decisión . Se desconoce el tiempo de ejecución de este paso, pero se ha demostrado que es óptimo: ningún algoritmo puede hacerlo mejor que el árbol de decisiones óptimo. Por lo tanto, este algoritmo tiene la propiedad peculiar de que es demostrablemente óptimo, aunque se desconoce su complejidad en tiempo de ejecución .

Algoritmos paralelos y distribuidos

La investigación también ha considerado algoritmos paralelos para el problema del árbol de expansión mínimo. Con un número lineal de procesadores es posible resolver el problema a tiempo. Bader y Cong (2006) demuestran un algoritmo que puede calcular MST 5 veces más rápido en 8 procesadores que un algoritmo secuencial optimizado. ${\ Displaystyle O (\ log n)}$

Se han diseñado otros algoritmos especializados para calcular árboles de expansión mínimos de un gráfico tan grande que la mayor parte debe almacenarse en el disco en todo momento. Estos algoritmos de almacenamiento externo , por ejemplo, como se describe en "Ingeniería de un algoritmo de árbol de expansión mínimo de memoria externa" de Roman, Dementiev et al., Pueden funcionar, según las afirmaciones de los autores, de 2 a 5 veces más lento que un algoritmo en memoria tradicional. algoritmo. Se basan en algoritmos de clasificación de almacenamiento externo eficientes y en técnicas de contracción de gráficos para reducir el tamaño del gráfico de manera eficiente.

El problema también se puede abordar de manera distribuida . Si cada nodo se considera una computadora y ningún nodo sabe nada excepto sus propios enlaces conectados, aún se puede calcular el árbol de expansión mínimo distribuido .

MST en gráficos completos

Alan M. Frieze demostró que dado un gráfico completo en n vértices, con pesos de aristas que son variables aleatorias independientes distribuidas de manera idéntica con una función de distribución satisfactoria , entonces cuando n se acerca a + ∞ el peso esperado de los enfoques MST , donde está la función zeta de Riemann ( más específicamente es la constante de Apéry ). Frieze y Steele también demostraron convergencia en probabilidad. Svante Janson demostró un teorema del límite central para el peso del MST. ${\ Displaystyle F}$ ${\ displaystyle F '(0)> 0}$ ${\ Displaystyle \ zeta (3) / F '(0)}$ ${\ Displaystyle \ zeta}$ ${\ Displaystyle \ zeta (3)}$

Para pesos aleatorios uniformes en , se ha calculado el tamaño exacto esperado del árbol de expansión mínimo para gráficos pequeños y completos. ${\ Displaystyle [0,1]}$

Vértices	Tamaño esperado	Tamaño estimado aproximado
2	1/2	0,5
3	3/4	0,75
4	31/35	0.8857143
5	893/924	0,9664502
6	278/273	1.0183151
7	30739/29172	1.053716
8	199462271/184848378	1.0790588
9	126510063932/115228853025	1.0979027

Aplicaciones

Árboles de expansión mínima tienen aplicaciones directas en el diseño de redes, incluidas las redes de computadoras , redes de telecomunicaciones , redes de transporte , redes de suministro de agua y redes eléctricas (que fueron inventadas por primera vez ya que, como se mencionó anteriormente). Se invocan como subrutinas en algoritmos para otros problemas, incluido el algoritmo de Christofides para aproximar el problema del viajante de comercio , aproximar el problema de corte mínimo de múltiples terminales (que es equivalente en el caso de un solo terminal al problema de flujo máximo ) y aproximar el de costo mínimo ponderado perfecta coincidencia .

Otras aplicaciones prácticas basadas en árboles de expansión mínimos incluyen:

Taxonomía .
Análisis de conglomerados : agrupación de puntos en el plano, agrupación de un solo enlace (un método de agrupación jerárquica ), agrupación de gráficos teóricos y agrupación de datos de expresión génica .
Construcción de árboles para retransmisiones en redes informáticas.
Registro y segmentación de imágenes : consulte la segmentación mínima basada en árbol de expansión .
Extracción de características curvilíneas en visión artificial .
Reconocimiento de escritura a mano de expresiones matemáticas.
Diseño de circuito : implementación de multiplicaciones constantes múltiples eficientes, como se usa en filtros de respuesta de impulso finito .
Regionalización de áreas sociogeográficas, agrupación de áreas en regiones homogéneas y contiguas.
Comparación de datos ecotoxicológicos .
Topológica observabilidad en sistemas de potencia.
Medición de la homogeneidad de materiales bidimensionales.
Control de procesos Minimax .
Los árboles de expansión mínimos también se pueden utilizar para describir los mercados financieros. Se puede crear una matriz de correlación calculando un coeficiente de correlación entre dos valores cualesquiera. Esta matriz se puede representar topológicamente como una red compleja y se puede construir un árbol de expansión mínimo para visualizar las relaciones.

Problemas relacionados

Árboles Steiner mínimos de vértices de polígonos regulares con N = 3 a 8 lados. La longitud de red más baja L para N > 5 es la circunferencia menos un lado. Los cuadrados representan puntos Steiner.

Se sabe que el problema de encontrar el árbol de Steiner de un subconjunto de los vértices, es decir, el árbol mínimo que abarca el subconjunto dado, es NP-Completo .

Un problema relacionado es el k -árbol de expansión mínimo ( k -MST), que es el árbol que abarca algún subconjunto de k vértices en el gráfico con un peso mínimo.

Un conjunto de k árboles de expansión más pequeños es un subconjunto de k árboles de expansión (de todos los árboles de expansión posibles) de modo que ningún árbol de expansión fuera del subconjunto tiene un peso menor. (Tenga en cuenta que este problema no está relacionado con el árbol de expansión k- mínimo).

El árbol de expansión mínimo euclidiano es un árbol de expansión de un gráfico con pesos de borde que corresponden a la distancia euclidiana entre vértices que son puntos en el plano (o espacio).

El árbol de expansión mínimo rectilíneo es un árbol de expansión de un gráfico con pesos de borde que corresponden a la distancia rectilínea entre vértices que son puntos en el plano (o espacio).

En el modelo distribuido , donde cada nodo se considera una computadora y ningún nodo sabe nada excepto sus propios enlaces conectados, se puede considerar un árbol de expansión mínimo distribuido . La definición matemática del problema es la misma, pero existen diferentes enfoques para una solución.

El árbol de expansión mínimo capacitado es un árbol que tiene un nodo marcado (origen o raíz) y cada uno de los subárboles adjuntos al nodo no contiene más de c nodos. c se llama capacidad de árbol. Resolver CMST de manera óptima es NP-difícil , pero las buenas heurísticas como Esau-Williams y Sharma producen soluciones cercanas a las óptimas en tiempo polinomial.

El árbol de expansión mínimo restringido por grados es un árbol de expansión mínimo en el que cada vértice está conectado a no más de d otros vértices, para algún número d dado . El caso d = 2 es un caso especial del problema del viajante de comercio , por lo que el árbol de expansión mínimo restringido por grados es NP-duro en general.

Para gráficos dirigidos , el problema del árbol de expansión mínimo se denomina problema de arborescencia y se puede resolver en tiempo cuadrático utilizando el algoritmo de Chu – Liu / Edmonds .

Un árbol de expansión máximo es un árbol de expansión con un peso mayor o igual que el peso de todos los demás árboles de expansión. Este árbol se puede encontrar con algoritmos como Prim o Kruskal después de multiplicar los pesos de los bordes por -1 y resolver el problema de MST en el nuevo gráfico. Una ruta en el árbol de expansión máxima es la ruta más ancha en el gráfico entre sus dos puntos finales: entre todas las rutas posibles, maximiza el peso del borde de peso mínimo. Los árboles de expansión máxima encuentran aplicaciones en algoritmos de análisis para lenguajes naturales y en algoritmos de entrenamiento para campos aleatorios condicionales .

El problema dinámico de MST se refiere a la actualización de un MST calculado previamente después de un cambio de peso de borde en el gráfico original o la inserción / eliminación de un vértice.

El problema del árbol de expansión de etiquetado mínimo es encontrar un árbol de expansión con el mínimo de tipos de etiquetas si cada borde de un gráfico está asociado con una etiqueta de un conjunto de etiquetas finito en lugar de un peso.

Un borde de cuello de botella es el borde ponderado más alto en un árbol de expansión. Un árbol de expansión es un árbol de expansión de cuello de botella mínimo (o MBST ) si el gráfico no contiene un árbol de expansión con un peso de borde de cuello de botella menor. Un MST es necesariamente un MBST (demostrable por la propiedad de corte ), pero un MBST no es necesariamente un MST.

Referencias

Otras lecturas

Otakar Boruvka sobre el problema del árbol de expansión mínimo (traducción de ambos artículos de 1926, comentarios, historia) (2000) Jaroslav Nešetřil , Eva Milková, Helena Nesetrilová. (La Sección 7 da su algoritmo, que parece un cruce entre Prim y Kruskal).
Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest y Clifford Stein . Introducción a los algoritmos , segunda edición. MIT Press y McGraw-Hill, 2001. ISBN 0-262-03293-7 . Capítulo 23: Árboles de expansión mínimos, págs. 561–579.
Eisner, Jason (1997). Algoritmos de última generación para árboles de expansión mínimos: un tutorial de discusión . Manuscrito, Universidad de Pennsylvania, abril. 78 págs.
Kromkowski, John David. "Aún sin fundir después de todos estos años", en Ediciones anuales, Raza y relaciones étnicas, 17 / e (2009 McGraw Hill) (Uso de árbol de expansión mínimo como método de análisis demográfico de la diversidad étnica en los Estados Unidos).

Languages

In other projects