Árbol de expansión mínimo

Árbol de menor peso que conecta los vértices del gráfico

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 conectado , ponderado por los bordes, que conecta todos los vértices entre sí, sin ningún ciclo y con el peso de borde total mínimo posible. ^[1] Es decir, es un árbol de expansión cuya suma de pesos de los bordes es lo más pequeña posible. ^[2] De manera más general, cualquier gráfico no dirigido ponderado por bordes (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ínima. Un ejemplo es una empresa de telecomunicaciones que intenta tender cable en un nuevo barrio. Si está obligado a enterrar el cable sólo a lo largo de ciertos caminos (por ejemplo, carreteras), entonces habrá un gráfico que contiene 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 esté enterrado más profundamente; Estos caminos estarían representados por aristas con pesos mayores. La moneda es una unidad aceptable para el peso de los bordes: no es necesario que las longitudes de los bordes obedezcan 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 que aún conecta cada casa; puede haber varios árboles de expansión posibles. Un árbol de expansión mínimo sería aquel con el costo total más bajo, representando el camino menos costoso 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 cobertura mínima del mismo peso; en particular, si todos los pesos de los bordes de un gráfico determinado son iguales, entonces cada árbol de expansión de ese gráfico es mínimo.

Unicidad

Si cada borde tiene un peso distinto, entonces solo habrá un árbol de expansión mínimo único . Esto es cierto en muchas situaciones realistas, como en el ejemplo anterior de la empresa de telecomunicaciones, donde es poco probable que dos rutas tengan exactamente el mismo costo. Esto también se generaliza a los bosques extensos.

Prueba:

1. Supongamos lo contrario , que existen dos MST diferentes , A y B.
2. Dado que A y B difieren a pesar de contener los mismos nodos, hay al menos una arista que pertenece a uno pero no al otro. Entre dichos bordes, sea e ₁ 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 que e ₁ está en A.
3. Como B es un MST, { e ₁ } ∪ B debe contener un ciclo C con e ₁ .
4. Como árbol, A no contiene ciclos, por lo tanto C debe tener una arista e ₂ que no esté en A.
5. 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 ₁ .
6. Como e ₁ y e ₂ son parte del ciclo C , reemplazar e ₂ con e ₁ en B produce un árbol de expansión con un peso menor.
7. 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 sólo el (multi)conjunto de pesos en los árboles de expansión mínima es seguro que será único; es lo mismo para todos los árboles de expansión mínima. ^[3]

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 si un subgrafo contiene un ciclo , eliminar cualquier borde a lo largo de ese ciclo disminuirá su costo y preservará la conectividad.

Propiedad del ciclo

Para cualquier ciclo C en el gráfico, si el peso de una arista e de C es mayor que cualquiera de los pesos individuales de todas las demás aristas de C , entonces esta arista no puede pertenecer a un MST.

Prueba: Supongamos lo contrario , es decir, que e pertenece a un MST T ₁ . Luego, eliminar e dividirá T ₁ en dos subárboles con los dos extremos de e en subárboles diferentes. El resto de C reconecta los subárboles, por lo tanto hay una arista f de C con extremos en diferentes subárboles, es decir, reconecta los subárboles en un árbol T ₂ con peso menor que el de T ₁ , 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 }, por lo tanto V – S = { C , F }, entonces hay 3 posibilidades de la arista a través del corte ( S , V – S ) , son aristas BC , EC , EF del gráfico original. 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 una arista 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 esta arista pertenece a todos los MST del gráfico. .

Prueba: Supongamos 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' } ∪ { e } de peso estrictamente menor que T . Esto contradice la suposición de que T era un MST.

Según 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 del costo mínimo

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

Prueba: si e no estuviera incluido 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 manteniendo la invariante de que el MST del gráfico contraído más T da el MST del gráfico antes de la contracción. ^[4]

Algoritmos

En todos los algoritmos siguientes, m es el número de aristas del 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 Algoritmo de Borůvka ). Su finalidad era una cobertura eléctrica eficiente de Moravia . El algoritmo procede en una secuencia de etapas. En cada etapa, llamada paso Boruvka , identifica un bosque F que consta del borde de peso mínimo incidente en cada vértice en el gráfico G , luego forma el gráfico G ₁ = G \ F como entrada para el siguiente paso. Aquí G \ F denota el gráfico derivado de G al contraer aristas en F (según la propiedad Cut, estas aristas pertenecen al MST). Cada paso de Boruvka requiere 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 tarda O ( m log n ) tiempo. ^[4]

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. Mediante 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 comúnmente utilizado es el algoritmo de Kruskal , que también requiere tiempo O ( m log n ) .

Un cuarto algoritmo, que no se usa con tanta frecuencia, es el algoritmo de eliminación inversa , que es lo inverso del algoritmo de Kruskal. Su tiempo de ejecución es O( m log n (log log n ) ³ ) .

Los cuatro son algoritmos codiciosos . Dado que se ejecutan en tiempo polinomial, el problema de encontrar dichos á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 computacionalmente más eficientes.

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 en el tiempo lineal basado en una combinación del algoritmo de Borůvka y el algoritmo de eliminación inversa. ^{[5] [6]}

El algoritmo basado en comparaciones no aleatorio más rápido con complejidad conocida, de Bernard Chazelle , se basa en el montón suave , una cola de prioridad aproximada. ^{[7] [8]} Su tiempo de ejecución es O ( m α( m , n )) , donde α es la inversa funcional clásica de la función de Ackermann . La función α crece extremadamente lentamente, de modo que para 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 ) . ^[9] El algoritmo ejecuta una serie de fases. Cada fase ejecuta el algoritmo de Prim muchas veces, cada una durante 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 como máximo . Por lo tanto, se necesitan como máximo log* n fases, lo que proporciona un tiempo de ejecución lineal para gráficos densos. ^[4] ${\displaystyle {\tfrac {n'}{2^{m/n'}}}}$

Existen otros algoritmos que funcionan en tiempo lineal en gráficos densos. ^{[7] [10]}

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 con números enteros. ^[11] Sigue siendo una cuestión abierta si el problema puede resolverse de forma determinista 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 aristas 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 del DT contiene una comparación entre dos aristas, por ejemplo "¿Es el peso de la arista entre xey mayor 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 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 número entero r , es posible encontrar árboles de decisión óptimos para todos los gráficos en r vértices mediante búsqueda de fuerza bruta . Esta búsqueda se desarrolla en dos pasos.

A. Generar todos los DT potenciales

• Hay diferentes gráficas en r vértices. ${\displaystyle 2^{r \choose 2}}$
• Para cada gráfico, siempre se puede encontrar un MST usando comparaciones r ( r – 1) , por ejemplo, mediante el algoritmo de Prim .
• Por tanto, la profundidad de un DT óptimo es menor que r ² .
• Por lo tanto, el número de nodos internos en un DT óptimo es menor que . ${\displaystyle 2^{r^{2}}}$
• Cada nodo interno compara dos aristas. El número de aristas es como máximo r ² , por lo que el número diferente de comparaciones es como máximo r ⁴ .
• Por lo tanto, el número de DT potenciales es menor que

${\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, se debe comprobar en todas las posibles permutaciones de los pesos de los bordes.

• ¡ El número de tales permutaciones es como máximo ( r ² )! .
• Para cada permutación, resuelva el problema 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 r ² , por lo que el tiempo total necesario para comprobar todas las permutaciones es como máximo ( r ² + 1). .

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

${\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 comparación determinista demostrablemente óptimo. ^[4] La siguiente es una descripción simplificada del algoritmo.

1. Sea r = log log log n , 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 ) (consulte Árboles de decisión más arriba).
2. Divida el gráfico en componentes con como máximo r vértices en cada componente. Esta partición utiliza un montón suave , que "corrompe" una pequeña cantidad de bordes del gráfico.
3. Utilice los árboles de decisión óptimos para encontrar un MST para el subgrafo no dañado dentro de cada componente.
4. 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 no corrupto.
5. Vuelva a agregar los bordes corruptos al bosque resultante para formar un subgrafo que garantice que contenga el árbol de expansión mínimo y que sea 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 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 funcionar mejor que el árbol de decisión ó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ínima. Con un número lineal de procesadores es posible resolver el problema en tiempo O (log n ) . ^{[12] [13]}

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 con pesos aleatorios

Alan M. Frieze demostró que dado un gráfico completo en n vértices, con pesos de borde que son variables aleatorias independientes distribuidas de manera idéntica con una función de distribución que satisface , 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 de 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. ^[14] ${\displaystyle [0,1]}$

Variante fraccionaria

Existe una variante fraccionaria del MST, en la que se permite que cada borde aparezca "fraccionalmente". Formalmente, un conjunto de expansión fraccionaria de un gráfico (V,E) es una función no negativa f en E tal que, para cada subconjunto no trivial W de V (es decir, W no está vacío ni es igual a V ), la suma de f ( e ) sobre todos los bordes que conectan un nodo de W con un nodo de V \ W es al menos 1. Intuitivamente, f ( e ) representa la fracción de e que está contenida en el conjunto generador. Un conjunto de expansión fraccional mínimo es un conjunto de expansión fraccional para el cual la suma es lo más pequeña posible. ${\displaystyle \sum _{e\in E}f(e)\cdot w(e)}$

Si las fracciones f ( e ) se fuerzan a estar en {0,1}, entonces el conjunto T de aristas con f(e)=1 es un conjunto generador, ya que cada nodo o subconjunto de nodos está conectado al resto de los gráfica por al menos un borde de T . Además, si f minimiza , entonces el conjunto de expansión resultante es necesariamente un árbol, ya que si contuviera un ciclo, entonces se podría eliminar un borde sin afectar la condición de expansión. Entonces, el problema del conjunto de expansión fraccional mínimo es una relajación del problema MST y también puede denominarse problema MST fraccional. ${\displaystyle \sum _{e\in E}f(e)\cdot w(e)}$

El problema de MST fraccional se puede resolver en tiempo polinómico utilizando el método del elipsoide . ^{[15] : 248} Sin embargo, si agregamos el requisito de que f ( e ) debe ser medio entero (es decir, f ( e ) debe estar en {0, 1/2, 1}), entonces el problema se convierte en NP- hard , ^{[15] : 248} ya que incluye como caso especial el problema del ciclo hamiltoniano : en un gráfico no ponderado de vértices, un MST de peso medio entero solo se puede obtener asignando peso 1/2 a cada arista de un ciclo hamiltoniano . ${\displaystyle n}$ ${\displaystyle n/2}$

Otras variantes

Á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.

• El árbol de Steiner de un subconjunto de vértices es el árbol mínimo que abarca el subconjunto dado. Encontrar el árbol de Steiner es NP-Completo . ^[dieciséis]

• El k -árbol de expansión mínimo ( k -MST) es el árbol que abarca algún subconjunto de k vértices en el gráfico con 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. ^{[17] [18] [19]} (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).
• El árbol de expansión mínimo distribuido es una extensión de MST al modelo distribuido , donde cada nodo se considera una computadora y ningún nodo sabe nada excepto sus propios enlaces conectados. La definición matemática del problema es la misma pero existen diferentes enfoques para su solución.
• El árbol de expansión mínima capacitado es un árbol que tiene un nodo marcado (origen o raíz) y cada uno de los subárboles adjuntos al nodo contiene no más de c nodos. c se llama capacidad de árbol. Resolver CMST de manera óptima es NP-difícil , ^[20] pero buenas heurísticas como Esau-Williams y Sharma producen soluciones cercanas a las óptimas en tiempo polinomial.
• El árbol de expansión mínimo de grado restringido es un MST en el que cada vértice está conectado a no más de d otros vértices, para un número dado d . El caso d  = 2 es un caso especial del problema del viajante , por lo que el árbol de expansión mínimo de grado restringido es NP-duro en general.
• Una arborescencia es una variante de MST para grafos dirigidos . Se puede resolver a tiempo utilizando el algoritmo de Chu-Liu/Edmonds . ${\displaystyle O(E+V\log V)}$
• Un árbol de expansión máximo es un árbol de expansión con un peso mayor o igual al peso de todos los demás árboles de expansión. Dicho á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. ^[21] Los árboles de expansión máxima encuentran aplicaciones en algoritmos de análisis para lenguajes naturales ^[22] y en algoritmos de entrenamiento para campos aleatorios condicionales .
• El problema de 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. ^{[23] [24] [25]}
• El problema del árbol de expansión de etiquetado mínimo es encontrar un árbol de expansión con el menor número 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. ^[26]
• 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 mediante la propiedad de corte), pero un MBST no es necesariamente un MST. ^{[27] [28]}
• Un juego de árbol de expansión de costo mínimo es un juego cooperativo en el que los jugadores tienen que compartir entre ellos los costos de construir el árbol de expansión óptimo.

Aplicaciones

Los árboles de expansión mínima tienen aplicaciones directas en el diseño de redes, incluidas redes informáticas , redes de telecomunicaciones , redes de transporte , redes de suministro de agua y redes eléctricas (para las que se inventaron por primera vez, como se mencionó anteriormente). ^[29] Se invocan como subrutinas en algoritmos para otros problemas, incluido el algoritmo de Christofides para aproximar el problema del viajante , ^[30] aproximar el problema de corte mínimo multiterminal (que es equivalente en el caso de un solo terminal al flujo máximo problema ), ^{[31] y aproximar el} emparejamiento perfecto ponderado de costo mínimo . ^[32]

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

• Taxonomía . ^[33]
• Análisis de conglomerados : puntos de agrupamiento en el plano, ^[34] agrupamiento de enlace único (un método de agrupamiento jerárquico ), ^[35] agrupamiento teórico de grafos, ^[36] y agrupamiento de datos de expresión génica . ^[37]
• Construcción de árboles para transmisión en redes informáticas. ^[38]
• Registro de imágenes ^[39] y segmentación ^[40] ; consulte Segmentación basada en árbol de expansión mínima .
• Extracción de características curvilíneas en visión por computadora . ^[41]
• Reconocimiento de escritura a mano de expresiones matemáticas. ^[42]
• Diseño de circuitos : implementación de multiplicaciones constantes múltiples eficientes, como se usa en filtros de respuesta de impulso finito . ^[43]
• Regionalización de áreas sociogeográficas, agrupación de áreas en regiones homogéneas y contiguas. ^[44]
• Comparación de datos de ecotoxicología . ^[45]
• Observabilidad topológica en sistemas de potencia. ^[46]
• Medición de la homogeneidad de materiales bidimensionales. ^[47]
• Control de procesos minimax . ^[48]
• También se pueden utilizar árboles de expansión mínima para describir los mercados financieros. ^{[49] [50]} Se puede crear una matriz de correlación calculando un coeficiente de correlación entre dos acciones 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.

Referencias

1. "scipy.sparse.csgraph.minimum_spanning_tree - Manual de SciPy v1.7.1". Documentación de Numpy y Scipy — Documentación de Numpy y Scipy . Consultado el 10 de diciembre de 2021 . Un árbol de expansión mínimo es un gráfico que consta de un subconjunto de aristas que juntas conectan todos los nodos conectados, minimizando al mismo tiempo la suma total de pesos en las aristas.
2. "networkx.algorithms.tree.mst.minimum_spanning_edges". Documentación de NetworkX 2.6.2 . Consultado el 13 de diciembre de 2021 . Un árbol de expansión mínimo es un subgrafo del gráfico (un árbol) con la suma mínima de pesos de los bordes. Un bosque de expansión es una unión de los árboles de expansión para cada componente conectado del gráfico.
3. "¿Los árboles de expansión mínima de un gráfico ponderado tienen el mismo número de aristas con un peso determinado?". cs.stackexchange.com . Consultado el 4 de abril de 2018 .
4. Pettie, Seth; Ramachandran, Vijaya (2002), "Un algoritmo de árbol de expansión mínimo óptimo" (PDF) , Revista de la Asociación de Maquinaria de Computación , 49 (1): 16–34, doi :10.1145/505241.505243, MR  2148431, S2CID  5362916.
5. Karger, David R .; Klein, Philip N.; Tarjan, Robert E. (1995), "Un algoritmo aleatorio de tiempo lineal para encontrar árboles de expansión mínimos", Revista de la Asociación de Maquinaria de Computación , 42 (2): 321–328, doi : 10.1145/201019.201022 , MR  1409738, S2CID  832583
6. Pettie, Seth; Ramachandran, Vijaya (2002), "Minimizar la aleatoriedad en el árbol de expansión mínimo, la conectividad paralela y establecer algoritmos de máximos", Proc. 13.º Simposio ACM-SIAM sobre algoritmos discretos (SODA '02), San Francisco, California, págs. 713–722, ISBN 9780898715132{{citation}}: Mantenimiento CS1: falta el editor de la ubicación ( enlace ).
7. Chazelle, Bernard (2000), "Un algoritmo de árbol de expansión mínimo con complejidad de tipo Ackermann inverso", Revista de la Asociación de Maquinaria de Computación , 47 (6): 1028–1047, doi : 10.1145/355541.355562 , MR  1866456, S2CID  6276962.
8. Chazelle, Bernard (2000), "El montón blando: una cola de prioridad aproximada con una tasa de error óptima", Revista de la Asociación de Maquinaria de Computación , 47 (6): 1012–1027, doi : 10.1145/355541.355554 , MR  1866455, S2CID  12556140.
9. Fredman, ML; Tarjan, RE (1987). "Montones de Fibonacci y sus usos en algoritmos mejorados de optimización de redes". Revista de la ACM . 34 (3): 596. doi : 10.1145/28869.28874 . S2CID  7904683.
10. Gabow, HN ; Galil, Z.; Spencer, T.; Tarjan, RE (1986). "Algoritmos eficientes para encontrar árboles de expansión mínima en gráficos dirigidos y no dirigidos". Combinatoria . 6 (2): 109. doi :10.1007/bf02579168. S2CID  35618095.
11. Fredman, ML ; Willard, DE (1994), "Algoritmos transdicotómicos para árboles de expansión mínima y caminos más cortos", Journal of Computer and System Sciences , 48 ​​(3): 533–551, doi : 10.1016/S0022-0000(05)80064-9 , señor  1279413.
12. Chong, Ka Wong; Han, Yijie; Lam, Tak Wah (2001), "Subprocesos concurrentes y algoritmo óptimo de árboles de expansión mínima paralela", Revista de la Asociación de Maquinaria de Computación , 48 (2): 297–323, doi :10.1145/375827.375847, MR  1868718, S2CID  1778676.
13. Pettie, Seth; Ramachandran, Vijaya (2002), "Un algoritmo paralelo óptimo de tiempo-trabajo aleatorio para encontrar un bosque de expansión mínima" (PDF) , SIAM Journal on Computing , 31 (6): 1879–1895, doi :10.1137/S0097539700371065, MR  1954882.
14. Steele, J. Michael (2002), "Árboles de expansión mínima para gráficos con longitudes de borde aleatorias", Matemáticas e informática, II (Versalles, 2002) , Trends Math., Basilea: Birkhäuser, págs. 223-245, MR  1940139
15. Grötschel, Martín ; Lovász, László ; Schrijver, Alexander (1993), Algoritmos geométricos y optimización combinatoria, Algoritmos y combinatoria, vol. 2 (2ª ed.), Springer-Verlag, Berlín, doi :10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, señor  1261419
16. Garey, Michael R .; Johnson, David S. (1979). Computadoras e intratabilidad: una guía para la teoría de la integridad NP . Serie de libros de ciencias matemáticas (1ª ed.). Nueva York: WH Freeman and Company . ISBN 9780716710455. SEÑOR  0519066. OCLC  247570676.. ND12
17. Gabow, Harold N. (1977), "Dos algoritmos para generar árboles de expansión ponderados en orden", SIAM Journal on Computing , 6 (1): 139–150, doi :10.1137/0206011, MR  0441784.
18. Eppstein, David (1992), "Encontrar los k árboles de expansión más pequeños", BIT , 32 (2): 237–248, doi :10.1007/BF01994879, MR  1172188, S2CID  121160520.
19. Frederickson, Greg N. (1997), "Estructuras de datos ambivalentes para conectividad dinámica de 2 bordes y k árboles de expansión más pequeños", SIAM Journal on Computing , 26 (2): 484–538, doi :10.1137/S0097539792226825, MR  1438526.
20. Jothi, Raja; Raghavachari, Balaji (2005), "Algoritmos de aproximación para el problema del árbol de expansión mínimo capacitado y sus variantes en el diseño de redes", ACM Trans. Algoritmos , 1 (2): 265–282, doi :10.1145/1103963.1103967, S2CID  8302085
21. Hu, TC (1961), "El problema de la ruta de máxima capacidad", Investigación de operaciones , 9 (6): 898–900, doi :10.1287/opre.9.6.898, JSTOR  167055.
22. McDonald, Ryan; Pereira, Fernando; Ribarov, Kiril; Hajič, enero (2005). "Análisis de dependencias no proyectivas mediante algoritmos de árbol de expansión" (PDF) . Proc. HLT/EMNLP .
23. Espira, PM; Pan, A. (1975), "Sobre la búsqueda y actualización de árboles de expansión y caminos más cortos" (PDF) , SIAM Journal on Computing , 4 (3): 375–380, doi :10.1137/0204032, MR  0378466.
24. Holm, Jacob; de Lichtenberg, Kristian; Thorup, Mikkel (2001), "Algoritmos totalmente dinámicos deterministas polilogarítmicos para conectividad, árbol de expansión mínimo, 2 bordes y biconectividad", Revista de la Asociación de Maquinaria de Computación , 48 (4): 723–760, doi :10.1145 /502090.502095, SEÑOR  2144928, S2CID  7273552.
25. Barbilla, F.; Houck, D. (1978), "Algoritmos para actualizar árboles de expansión mínima", Journal of Computer and System Sciences , 16 (3): 333–344, doi :10.1016/0022-0000(78)90022-3.
26. Chang, RS; Leu, SJ (1997), "El etiquetado mínimo que abarca los árboles", Cartas de procesamiento de información , 63 (5): 277–282, doi :10.1016/s0020-0190(97)00127-0.
27. "Todo sobre el árbol de expansión de cuellos de botella". pensamientos-destellantes.blogspot.ru . 5 de junio de 2010 . Consultado el 4 de abril de 2018 .
28. "Copia archivada" (PDF) . Archivado desde el original (PDF) el 12 de junio de 2013 . Consultado el 2 de julio de 2014 .{{cite web}}: Mantenimiento CS1: copia archivada como título ( enlace )
29. Graham, RL ; Hell, Pavol (1985), "Sobre la historia del problema del árbol de expansión mínima", Annals of the History of Computing , 7 (1): 43–57, doi :10.1109/MAHC.1985.10011, MR  0783327, S2CID  10555375
30. Nicos Christofides , Análisis del peor de los casos de una nueva heurística para el problema del viajante, Informe 388, Escuela de Graduados en Administración Industrial, CMU, 1976.
31. Dahlhaus, E.; Johnson, DS ; Papadimitriou, CH ; Seymour, PD ; Yannakakis, M. (agosto de 1994). «La complejidad de los cortes multiterminales» (PDF) . Revista SIAM de Computación . 23 (4): 864–894. doi :10.1137/S0097539792225297. Archivado desde el original (PDF) el 24 de agosto de 2004 . Consultado el 17 de diciembre de 2012 .
32. Supowit, Kenneth J.; Plaisted, David A.; Reingold, Edward M. (1980). Heurísticas para una coincidencia perfecta ponderada. 12º Simposio Anual ACM sobre Teoría de la Computación (STOC '80). Nueva York, NY, Estados Unidos: ACM. págs. 398–419. doi :10.1145/800141.804689.
33. Sneath, PHA (1 de agosto de 1957). "La aplicación de las computadoras a la taxonomía". Revista de Microbiología General . 17 (1): 201–226. doi : 10.1099/00221287-17-1-201 . PMID  13475686.
34. Asano, T .; Bhattacharya, B.; Keil, M.; Yao, F. (1988). Algoritmos de agrupamiento basados ​​en árboles de expansión mínima y máxima . Cuarto Simposio Anual sobre Geometría Computacional (SCG '88). vol. 1. págs. 252–257. doi :10.1145/73393.73419.
35. Gower, JC; Ross, GJS (1969). "Árboles de expansión mínima y análisis de conglomerados de enlace único". Revista de la Real Sociedad de Estadística . C (Estadística Aplicada). 18 (1): 54–64. doi :10.2307/2346439. JSTOR  2346439.
36. Päivinen, Niina (1 de mayo de 2005). "Agrupación con un árbol de expansión mínimo de estructura libre de escala". Letras de reconocimiento de patrones . 26 (7): 921–930. Código Bib : 2005PaReL..26..921P. doi :10.1016/j.patrec.2004.09.039.
37. Xu, Y.; Olman, V.; Xu, D. (1 de abril de 2002). "Agrupación de datos de expresión genética mediante un enfoque de teoría de gráficos: una aplicación de árboles de expansión mínima". Bioinformática . 18 (4): 536–545. doi : 10.1093/bioinformática/18.4.536 . PMID  12016051.
38. Dalal, Yogen K.; Metcalfe, Robert M. (1 de diciembre de 1978). "Reenvío de ruta inversa de paquetes de difusión". Comunicaciones de la ACM . 21 (12): 1040–1048. doi : 10.1145/359657.359665 . S2CID  5638057.
39. Mamá, B.; Héroe, A.; Gorman, J.; Michel, O. (2000). Registro de imágenes con algoritmo de árbol de expansión mínimo (PDF) . Congreso Internacional sobre Procesamiento de Imágenes. vol. 1. págs. 481–484. doi :10.1109/ICIP.2000.901000. Archivado (PDF) desde el original el 9 de octubre de 2022.
40. P. Felzenszwalb, D. Huttenlocher: segmentación eficiente de imágenes basada en gráficos. IJCV 59(2) (septiembre de 2004)
41. Suk, Minsoo; Canción, Ohyoung (1 de junio de 1984). "Extracción de características curvilíneas utilizando árboles de expansión mínima". Visión por computadora, gráficos y procesamiento de imágenes . 26 (3): 400–411. doi :10.1016/0734-189X(84)90221-4.
42. Tapia, Ernesto; Rojas, Raúl (2004). "Reconocimiento de expresiones matemáticas manuscritas en línea utilizando una construcción de árbol de expansión mínima y dominio de símbolos" (PDF) . Reconocimiento de gráficos. Avances y perspectivas recientes . Apuntes de conferencias sobre informática. vol. 3088. Berlín Heidelberg: Springer-Verlag. págs. 329–340. ISBN 978-3540224785. Archivado (PDF) desde el original el 9 de octubre de 2022.
43. Ohlsson, H. (2004). Implementación de filtros FIR de baja complejidad utilizando un árbol de expansión mínimo . XII Conferencia Electrotécnica Mediterránea del IEEE (MELECON 2004). vol. 1. págs. 261–264. doi :10.1109/MELCON.2004.1346826.
44. Assunção, RM; MC Neves; G. Cámara; C. Da Costa Freitas (2006). "Técnicas eficientes de regionalización de unidades geográficas socioeconómicas utilizando árboles de expansión mínima". Revista Internacional de Ciencia de la Información Geográfica . 20 (7): 797–811. Código Bib : 2006IJGIS..20..797A. doi :10.1080/13658810600665111. S2CID  2530748.
45. Devillers, J.; Dore, JC (1 de abril de 1989). "Potencia heurística del método del árbol de expansión mínima (MST) en toxicología". Ecotoxicología y Seguridad Ambiental . 17 (2): 227–235. Código Bib :1989EcoES..17..227D. doi :10.1016/0147-6513(89)90042-0. PMID  2737116.
46. Mori, H.; Tsuzuki, S. (1 de mayo de 1991). "Un método rápido para el análisis de observabilidad topológica utilizando una técnica de árbol de expansión mínima". Transacciones IEEE sobre sistemas de energía . 6 (2): 491–500. Código Bib : 1991ITPSy...6..491M. doi :10.1109/59.76691.
47. Filliben, James J.; Kafadar, Karen ; Shier, Douglas R. (1 de enero de 1983). "Pruebas de homogeneidad de superficies bidimensionales". Modelo matematico . 4 (2): 167–189. doi :10.1016/0270-0255(83)90026-X.
48. Kalaba, Robert E. (1963), Teoría de grafos y control automático (PDF) , archivado desde el original (PDF) el 21 de febrero de 2016
49. Mantegna, enfermera registrada (1999). Estructura jerárquica en los mercados financieros. The European Physical Journal B-Materia condensada y sistemas complejos, 11 (1), 193–197.
50. Djauhari, M. y Gan, S. (2015). Problema de optimización de la topología de red en el análisis del mercado de valores. Physica A: Mecánica estadística y sus aplicaciones, 419, 108-114.

Otras lecturas

• Otakar Boruvka sobre el problema del árbol de expansión mínima (traducción de ambos artículos de 1926, comentarios, historia) (2000) Jaroslav Nešetřil , Eva Milková, Helena Nesetrilová. (La Sección 7 presenta su algoritmo, que parece un cruce entre el de Prim y el de 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ínima, págs. 561–579. 
• Eisner, Jason (1997). Algoritmos de última generación para árboles de expansión mínima: una discusión tutorial. Manuscrito, Universidad de Pennsylvania, abril. 78 págs.
• Kromkowski, John David. "Still Unmelted after All These Years", en ediciones anuales, Race and Ethnic Relations, 17/e (2009 McGraw Hill) (Utilizando un árbol de expansión mínimo como método de análisis demográfico de la diversidad étnica en los Estados Unidos).

enlaces externos

• Implementada en BGL, la biblioteca Boost Graph
• Repositorio de algoritmos de Stony Brook: códigos mínimos del árbol de expansión
• Implementado en QuickGraph para .Net