Árbol de expansión mínimo

Compartir Imprimir Citar

Árbol menos pesado que conecta vértices gráficos

Un gráfico plano y su árbol de azotes 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 árbol de expansión de peso mínimo es un subconjunto de los bordes de un borde ponderado no dirigido gráfico que conecta todos los vértices entre sí, sin ningún ciclo y con el mínimo peso de arista total posible. Es decir, es un árbol de expansión cuya suma de pesos de arista es lo más pequeña posible. En términos más generales, 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 los árboles de expansión mínimos. Un ejemplo es una empresa de telecomunicaciones que trata de instalar cable en un nuevo vecindario. Si está obligado a enterrar el cable solo a lo largo de ciertos caminos (por ejemplo, caminos), entonces habría un gráfico que contiene los puntos (por ejemplo, casas) conectados por esos caminos. Algunas de las rutas pueden ser más costosas, porque son más largas o requieren que el cable se entierre más profundo; estos caminos estarían representados por aristas con mayor peso. 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 la 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 así 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, representando la ruta menos costosa para tender el cable.

Propiedades

Multiplicidad posible

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 azotes mínimo en un gráfico. En la figura, los dos árboles debajo del gráfico son dos posibilidades de azote 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 todos los árboles de expansión de ese gráfico son mínimos.

Singularidad

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 a los bosques extensos también.

Prueba:

Suponga lo contrario, que hay dos MST diferentes $A$ y $B$ .
Desde $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, dejar $e 1$ ser el que tiene menos peso; esta elección es única porque los pesos del borde son todos distintos. Sin pérdida de generalidad, asuma $e 1$ está dentro $A$ .
As $B$ es un MST, ${} e 1 \cup B$ debe contener un ciclo $C$ con $e 1$ .
Como árbol, $A$ no contiene ciclos, por lo tanto $C$ debe tener un borde $e 2$ que no está $A$ .
Desde $e 1$ fue elegido como el borde de peso más bajo único entre los que pertenecen exactamente a uno de $A$ y $B$ , el peso de $e 2$ debe ser mayor que el peso de $e 1$ .
As $e 1$ y $e 2$ son parte del ciclo $C$ , sustitución $e 2$ con $e 1$ dentro $B$ por lo tanto produce un árbol de azotes con un peso más pequeño.
Esto contradice el supuesto de que $B$ es un MST.

De manera más general, si los pesos de los bordes no son todos distintos, entonces solo el conjunto (múltiple) de pesos en los árboles de expansión mínimos es seguro que es único; es lo mismo 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 cualquiera de los pesos individuales de todos los demás bordes de $C$ , entonces este borde no puede pertenecer a un MST.

Prueba: Asuma lo contrario, es decir, que $e$ pertenece a un MST $T 1$ . Luego, eliminar $e$ romperá $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 que 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 inferior al de $T 1$ , porque el peso de $f$ es menor que el peso de e.

Propiedad de corte

Esta figura muestra la propiedad cortada de MSTs.

T

es el único MST del gráfico dado. Si

S = A, B, D, E}

por lo tanto

V - S = C, F}

entonces hay 3 posibilidades del borde a través del corte

() S, V - S)

, son bordes

BC

CE

EF

del gráfico original. Entonces, e es uno de los pesos mínimos para el corte, por lo tanto

S . e}

es parte del MST

T

Para cualquier corte $C$ del gráfico, si el peso de una arista $e$ en el conjunto de cortes de $C$ es estrictamente más pequeño 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'$ . Eliminando $e'$ obtenemos un árbol de expansión $T ∖ {e'} \cup {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 algún árbol de expansión mínimo.

Ventaja de costo mínimo

Si la ventaja de costo mínimo $e$ de un gráfico es única, esta ventaja se incluye en cualquier MST.

Prueba: si $e$ no se incluyó en el MST, eliminando 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 bordes MST, entonces podemos contraer $T$ en un solo vértice manteniendo la invariante de que el MST del grafo contraído más $T$ da el MST para el gráfico antes de la contracción.

Algoritmos

En todos los algoritmos a continuación, $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 (consulte el algoritmo de Borůvka). Su finalidad era una eficiente cobertura eléctrica 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 a cada vértice en el gráfico $G$ , luego forma el gráfico $G 1 = G F$ como entrada para el siguiente paso. Aquí $G F$ denota el gráfico derivado de $G$ contrayendo 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.

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)$ tal que $x$ está en $T$ y $y$ aún 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)$ o $O (m + n log n)$ , dependiendo de los datos- estructuras 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, que no se usa con tanta frecuencia, es el algoritmo de eliminación inversa, que es el reverso del algoritmo de Kruskal. Su tiempo de ejecución es $O(m log n (log log n) 3)$ .

Los cuatro son algoritmos codiciosos. Dado que se ejecutan en tiempo polinomial, el problema de encontrar tales árboles está en FP y los problemas de decisión relacionados, como determinar si un borde particular está en el MST o determinar si el peso total mínimo excede 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 informático.

En un modelo de comparación, en el que las únicas operaciones permitidas en los pesos de los bordes son las comparaciones por pares, Karger, Klein & Tarjan (1995) encontró un algoritmo aleatorizado 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 almacenamiento dinámico, 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 extremadamente lentamente, por lo que a efectos prácticos puede considerarse una constante no superior a 4; por lo 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 \geq log log log n)$ , entonces un algoritmo determinista de Fredman y Tarjan encuentra el MST a tiempo $O... m)$ . El algoritmo ejecuta una serie de fases. Cada fase ejecuta el algoritmo de Prim muchas veces, cada una por 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 $n '$ , el número de vértices que quedan después de una fase es al máximo ${displaystyle {tfrac {n'}{2^{m/n'}}}}$ . Por lo tanto, como mucho $log* n$ fases son necesarias, lo que da un tiempo de ejecución lineal para gráficos densos.

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

Pesos de 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 con enteros. Sigue siendo una pregunta abierta si el problema se puede resolver determinísticamente para un gráfico general en tiempo lineal mediante un algoritmo basado en comparación.

Árboles de decisión

Dado el gráfico $G$ donde los nodos y los bordes son fijos pero los pesos son desconocidos, es posible construir una decisión binaria árbol (DT) para calcular el MST para cualquier permutación de pesos. Cada nodo interno del IME contiene una comparación entre dos aristas, p. "¿El peso del borde entre $x$ y $y$ mayor que el peso del borde 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 del tiempo de ejecución de un DT es la mayor cantidad de consultas necesarias para encontrar el MST, que es solo la profundidad del DT. Un DT para un gráfico $G$ se llama óptimo si tiene la profundidad más pequeña de todos los DT correctos para $G$ .

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

A. Generando todos los DT potenciales

Hay $2^{{r choose 2}}$ diferentes gráficos en $r$ vertices.
Para cada gráfico, siempre se puede encontrar un MST usando $r () r - 1)$ comparaciones, por ejemplo por el algoritmo de Prim.
Por lo tanto, la profundidad de un DT óptimo es menos que $r 2$ .
Por lo tanto, el número de nodos internos en un DT óptimo es menor que el $2^{r^{2}}$ .
Cada nodo interno compara dos bordes. El número de bordes es en la mayoría $r 2$ por lo que el número diferente de comparaciones es en la mayoría $r 4$ .
Por lo tanto, el número de DT potenciales es menor que el
${displaystyle {(r^{4})}^{(2^{r^{2}})}=r^{2^{(r^{2}+2)}}.}$

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

El número de tales permutaciones es en su mayoría $() r 2)!$ .
Para cada permutación, solucione el problema MST en el gráfico dado utilizando cualquier algoritmo existente, y compare el resultado a la respuesta dada por el DT.
El tiempo de funcionamiento de cualquier algoritmo MST es en la mayoría $r 2$ , por lo que el tiempo total requerido para comprobar todas las permutaciones es al máximo $() r 2 + 1)!$ .

Por lo tanto, el tiempo total requerido para encontrar un DT óptimo para todos gráficos con $r$ vértices es:

{displaystyle 2^{r choose 2}cdot r^{2^{(r^{2}+2)}}cdot (r^{2}+1)!,}

que es menor que

{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 demostrablemente óptimo. La siguiente es una descripción simplificada del algoritmo.

Vamos $r = log log log n$ , donde $n$ es el número de vértices. Encontrar todos los árboles de decisión óptimos $r$ vertices. Esto se puede hacer a tiempo $O () n)$ (ver árboles de decisión arriba).
Partición del gráfico a los componentes con $r$ vertices en cada componente. Esta partición utiliza un montón suave, que "corrupta" un pequeño número de los bordes del gráfico.
Utilice los árboles de decisión óptimos para encontrar un MST para el subgrafo incorrupto dentro de cada componente.
Contratar cada componente conectado abarcado por los MST a un solo vértice, y aplicar cualquier algoritmo que funcione en gráficos densos a tiempo $O () m)$ a la contracción del subgrafo incorrupto
Agregue los bordes dañados al bosque resultante para formar un subgrafo garantizado para contener el árbol mínimo de azotes, y más pequeño por un factor constante que el gráfico inicial. Aplicar el algoritmo óptimo recursivamente a este gráfico.

El tiempo de ejecución de todos los pasos del algoritmo es $O (m)$ , excepto el paso de utilizar 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 decisión óptimo. Así, este algoritmo tiene la peculiar propiedad de que es probablemente óptimo aunque su complejidad en tiempo de ejecución es desconocida.

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 en $O (log n)$ tiempo. Bader &amperio; Cong (2006) demuestra un algoritmo que puede calcular MST 5 veces más rápido en 8 procesadores que un algoritmo secuencial optimizado.

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 "Diseño de un algoritmo de árbol de expansión mínimo de memoria externa" por Roman, Dementiev et al., puede operar, por autores' afirma, tan solo de 2 a 5 veces más lento que un algoritmo tradicional en memoria. 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 forma 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 mostró que dado un gráfico completo n vértices, con pesos de borde que son variables aleatorias distribuidas idénticamente con función de distribución $F$ satisfacción $0}" xmlns="http://www.w3.org/1998/Math/MathML">F.()0)■0{displaystyle F'(0)}0" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/22813ad123b73c17ee8704115c2b4fe8432ab529" style="vertical-align: -0.838ex; width:9.732ex; height:3.009ex;"/>$ , entonces como n enfoques + dieta el peso esperado del MST se acerca $zeta (3)/F'(0)$ , donde $zeta$ es la función Riemann zeta (más específicamente es $zeta (3)$ La constante de Apéry). Frieze y Steele también demostraron convergencia en probabilidad. Svante Janson demostró un teorema límite central para el peso del MST.

Para pesos aleatorios uniformes en $[0,1]$ , el tamaño exacto esperado del árbol mínimo de azotes ha sido calculado para pequeños gráficos completos.

Vertices	Tamaño previsto	Tamaño previsto 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

Los árboles de expansión mínimos tienen aplicaciones directas en el diseño de redes, incluidas las redes informáticas, las redes de telecomunicaciones, las redes de transporte, las redes de suministro de agua y las redes eléctricas (para las que se inventaron por primera vez, 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 la coincidencia perfecta ponderada de costo mínimo.

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

Taxonomía.
Análisis de racimo: puntos de agrupación en el plano, agrupación de un solo enlace (un método de agrupación jerárquica), agrupación gráfica-teórica y datos de expresión de genes agrupados.
Construyendo árboles para la difusión en redes informáticas.
Registro de imágenes y segmentación – vea la segmentación mínima basada en árboles.
Extracción de características Curvilinear en la visión de la computadora.
Reconocimiento de escritura de expresiones matemáticas.
Diseño del circuito: implementación de multiplicaciones constantes eficientes, como se utiliza en filtros de respuesta del impulso finito.
Regionalización de áreas sociogeográficas, agrupación de áreas en regiones homogéneas y contiguas.
Comparando datos ecotoxicológicos.
Vigilancia topológica en sistemas de energía.
Medición de la homogeneidad de los materiales bidimensionales.
Control de proceso Minimax.
También se pueden utilizar árboles mínimos para describir los mercados financieros. Se puede crear una matriz de correlación calculando un coeficiente de correlación entre dos acciones. Esta matriz puede ser representada topológicamente como una red compleja y se puede construir un árbol de lazo mínimo para visualizar las relaciones.

Problemas relacionados

Mínimo Árboles Steiner 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. Las plazas representan puntos Steiner.

Se sabe que el problema de encontrar el árbol de Steiner de un subconjunto de 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 árboles de expansión más pequeños. peso. (Tenga en cuenta que este problema no está relacionado con el árbol de expansión mínimo k).

El árbol de expansión mínimo euclidiano es un árbol de expansión de un gráfico con pesos de borde correspondientes 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 correspondientes 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 el á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 un nodo c. c se llama capacidad de un árbol. Resolver CMST de manera óptima es NP-difícil, pero las buenas heurísticas como Esau-Williams y Sharma producen soluciones cercanas al óptimo en tiempo polinomial.

El árbol de expansión mínimo con restricción de 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 un número determinado d. El caso d = 2 es un caso especial del problema del viajante de comercio, por lo que el árbol de expansión mínimo con restricciones de grado es NP-duro en general.

Para gráficos dirigidos, el problema mínimo del árbol de azotes se llama el problema de la Arborescencia y se puede resolver en $O(E + V log V)$ tiempo utilizando el algoritmo 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 cualquier otro árbol de expansión. Dicho árbol se puede encontrar con algoritmos como Prim's o Kruskal's después de multiplicar los pesos de los bordes por -1 y resolver el problema MST en el nuevo gráfico. Un camino en el árbol de expansión máximo es el camino más ancho en el gráfico entre sus dos puntos finales: entre todos los caminos posibles, maximiza el peso del borde de peso mínimo. Los árboles de expansión máximos encuentran aplicaciones en algoritmos de análisis para lenguajes naturales y en algoritmos de entrenamiento para campos aleatorios condicionales.

El problema del MST dinámico se refiere a la actualización de un MST previamente calculado 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 menos tipos de etiquetas si cada borde de un gráfico está asociado con una etiqueta de un conjunto finito de etiquetas en lugar de un peso.

Un borde de cuello de botella es el borde de mayor peso 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 (probable por la propiedad de corte), pero un MBST no es necesariamente un MST.