Á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ínima. Cada arista está etiquetada 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 las aristas de un grafo no dirigido con ponderación de aristas conectado que conecta todos los vértices entre sí, sin ningún ciclo y con el mínimo peso total de arista posible. ^[1] Es decir, es un árbol de expansión cuya suma de pesos de aristas es lo más pequeña posible. ^[2] De manera más general, cualquier grafo no dirigido con ponderación de aristas (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 .

Existen muchos casos de uso para árboles de expansión mínima. Un ejemplo es una empresa de telecomunicaciones que intenta tender un cable en un nuevo vecindario. Si está restringida a enterrar el cable solo a lo largo de ciertos caminos (por ejemplo, carreteras), entonces habría 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 se representarían mediante aristas con pesos mayores. La moneda es una unidad aceptable para el peso de las aristas; no hay ningún requisito de que las longitudes de las aristas 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 que aún así conecta cada casa; podría haber varios árboles de expansión posibles. Un árbol de expansión mínimo sería uno con el costo total más bajo, 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ínima en un gráfico. En la figura, los dos árboles debajo del gráfico son dos posibilidades de árbol de expansión mínima 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 los mismos, entonces cada árbol de expansión de ese gráfico es mínimo.

Unicidad

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

Prueba:

1. Supongamos lo contrario , que hay dos MST diferentes , A y B.
2. Como A y B difieren a pesar de contener los mismos nodos, hay al menos una arista que pertenece a una pero no a la otra. Entre dichas aristas, sea e ₁ la que tenga el menor peso; esta elección es única porque los pesos de las aristas 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 ₂ por 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 solo el conjunto (múltiple) de pesos en los árboles de expansión mínima seguramente 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 arista 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.

Demostración: Supongamos lo contrario , es decir, que e pertenece a un MST T ₁ . Entonces, eliminar e dividirá T ₁ en dos subárboles con los dos extremos de e en diferentes subárboles. 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 .

Propiedad cortada

Esta figura muestra la propiedad de corte de los MST. T es el único MST del grafo 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 las aristas BC , EC , EF del grafo original. Entonces, e es una de las aristas 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 corte de C es estrictamente menor que los pesos de todas las demás aristas del conjunto de corte de C , entonces esta arista pertenece a todos los MST del gráfico.

Demostración: Supongamos que existe un MST T que no contiene e . Añadir e a T producirá un ciclo que cruza el corte una vez en e y vuelve a cruzarlo en otro borde e' . Si eliminamos 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.

Mediante un argumento similar, si más de un borde tiene un peso mínimo a lo largo de 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 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, al eliminar cualquiera de los bordes (de mayor costo) en el ciclo formado después de agregar e al MST, se obtendrí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 único vértice manteniendo la invariancia 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 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 a cada vértice en el grafo G , luego forma el grafo G ₁ = G \ F como entrada al siguiente paso. Aquí G \ F denota el grafo derivado de G mediante la contracción de 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 un tiempo O ( m log n ) . ^[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 ) una arista a la vez. Inicialmente, T contiene un vértice arbitrario. En cada paso, T se aumenta con una arista de menor peso ( x , y ) tal que x está en T e y aún no está en T . Por la propiedad Cut, todas las aristas agregadas 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 las estructuras de datos utilizadas.

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

Un cuarto algoritmo, que no se utiliza tan comúnmente, 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 voraces . 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 una arista 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 lineal en el tiempo basado en una combinación del algoritmo de Borůvka y el algoritmo de eliminación inversa. ^{[5] [6]}

El algoritmo de comparación no aleatorio más rápido con complejidad conocida, de Bernard Chazelle , se basa en el soft heap , 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, por lo que para todos los fines prácticos puede considerarse una constante no mayor que 4; por lo tanto, el algoritmo de Chazelle toma un tiempo muy cercano al lineal.

Algoritmos de tiempo lineal en casos especiales

Gráficos densos

Si el grafo 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 varias 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 restantes después de una fase es como máximo . Por lo tanto, se necesitan como máximo log* n fases, lo que da un tiempo de ejecución lineal para grafos densos. ^[4] ${\displaystyle {\tfrac {n'}{2^{m/n'}}}}$

Existen otros algoritmos que trabajan en tiempo lineal sobre 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] Si el problema se puede resolver de manera determinista para un gráfico general en tiempo lineal mediante un algoritmo basado en comparación sigue siendo una pregunta abierta.

Árboles de decisión

Dado un grafo G donde los nodos y las aristas son fijos pero los pesos son desconocidos, 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 "¿El peso de la arista entre x e y es 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 en tiempo de ejecución de un DT es la mayor cantidad de consultas requeridas para encontrar el MST, que es simplemente la profundidad del DT. Un DT para un grafo 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 grafos en r vértices mediante una búsqueda de fuerza bruta . Esta búsqueda se realiza en dos pasos.

A. Generar 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 lo 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 permutaciones posibles 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 requerido para verificar todas las permutaciones es como máximo ( r ² + 1) !.

Por lo tanto, el tiempo total necesario 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 descubierto 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 tiempo O ( n ) (vea Árboles de decisión arriba).
2. Particionar el gráfico en componentes con un máximo de r vértices en cada componente. Esta partición utiliza un montón blando , que "corrompe" una pequeña cantidad de aristas del gráfico.
3. Utilice los árboles de decisión óptimos para encontrar un MST para el subgráfico no corrupto dentro de cada componente.
4. Contraer cada componente conectado abarcado por los MST a un único vértice y aplicar cualquier algoritmo que funcione en gráficos densos en tiempo O ( m ) a la contracción del subgráfico no corrupto
5. Vuelva a agregar los bordes dañados al bosque resultante para formar un subgrafo que contenga el árbol de expansión mínimo y que sea más pequeño por un factor constante que el grafo inicial. Aplique el algoritmo óptimo de forma recursiva a este grafo.

El tiempo de ejecución de todos los pasos del algoritmo es O ( m ) , excepto el paso de utilizar los árboles de decisión . El tiempo de ejecución de este paso es desconocido, pero se ha demostrado que es óptimo: ningún algoritmo puede hacerlo 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 de 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 en tiempo O (log n ) . ^{[12] [13]}

El problema también puede abordarse de manera distribuida . Si cada nodo se considera una computadora y ningún nodo conoce nada más que 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 grafo completo en n vértices, con pesos de aristas que son variables aleatorias independientes idénticamente distribuidas con una función de distribución que satisface , entonces cuando n se acerca a +∞ el peso esperado del MST se acerca a , donde es la función zeta de Riemann (más específicamente es la constante de Apéry ). Frieze y Steele también demostraron la 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 esperado exacto del árbol de expansión mínimo para gráficos completos pequeños. ^[14] ${\displaystyle [0,1]}$

Variante fraccionaria

Existe una variante fraccionaria del MST, en la que se permite que cada arista aparezca "fraccionalmente". Formalmente, un conjunto generador fraccionario de un grafo (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 todas las aristas 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 generador fraccionario mínimo es un conjunto generador fraccionario 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 del grafo por al menos una arista de T . Además, si f minimiza , entonces el conjunto generador resultante es necesariamente un árbol, ya que si contuviera un ciclo, entonces se podría eliminar una arista sin afectar la condición generadora. Por lo tanto, el problema del conjunto generador fraccional mínimo es una relajación del problema MST, y también puede llamarse el problema MST fraccional. ${\displaystyle \sum _{e\in E}f(e)\cdot w(e)}$

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

Otras variantes

Árboles de 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 de 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 . ^[16]

• El árbol de expansión k -mínimo ( k -MST) es el árbol que abarca un subconjunto de k vértices en el gráfico con un peso mínimo.
• Un conjunto de árboles de expansión k-más pequeños es un subconjunto de árboles de expansión k (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 k -mínimo).
• El árbol de expansión mínimo euclidiano es un árbol de expansión de un gráfico con pesos de arista 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 arista correspondientes a la distancia rectilínea entre vértices que son puntos en el plano (o espacio).
• El árbol de expansión mínima distribuida es una extensión del modelo distribuido de MST , en el que cada nodo se considera una computadora y ningún nodo conoce nada más que sus propios enlaces conectados. La definición matemática del problema es la misma, pero existen diferentes enfoques para encontrar una solución.
• El árbol de expansión mínima capacitada 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 denomina capacidad de árbol. Resolver CMST de manera óptima es NP-hard , ^[20] pero buenas heurísticas como Esau-Williams y Sharma producen soluciones cercanas a lo óptimo en tiempo polinomial.
• El árbol de expansión mínima con restricciones de grado 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 de comercio , por lo que el árbol de expansión mínima con restricciones de grado es NP-hard en general.
• Una arborescencia es una variante de MST para grafos dirigidos . Se puede resolver en el tiempo utilizando el algoritmo Chu–Liu/Edmonds . ${\displaystyle O(E+V\log V)}$
• Un árbol de expansión máxima es un árbol de expansión con un peso mayor o igual al peso de todos los demás árboles de expansión. Este tipo de árbol se puede encontrar con algoritmos como el de Prim o el de Kruskal después de multiplicar los pesos de las aristas por -1 y resolver el problema MST en el nuevo grafo. Una ruta en el árbol de expansión máxima es la ruta más ancha en el grafo entre sus dos puntos finales: entre todas las rutas posibles, maximiza el peso de la arista 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 MST dinámico 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. ^{[23] [24] [25]}
• El problema del árbol de expansión con etiquetado mínimo es encontrar un árbol de expansión con la menor cantidad 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]
• Una arista de cuello de botella es la arista con 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 arista 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. ^{[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 construcción del árbol de expansión óptimo.
• El problema de diseño de red óptima es el problema de calcular un conjunto, sujeto a una restricción presupuestaria, que contiene un árbol de expansión, de modo que la suma de los caminos más cortos entre cada par de nodos sea lo más pequeña posible.

Aplicaciones

Los á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 (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 de comercio , ^[30] aproximar el problema de corte mínimo multiterminal (que es equivalente en el caso de terminal único al problema de flujo máximo ), ^{[31] y aproximar el} emparejamiento perfecto ponderado de costo mínimo . ^[32]

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

• Taxonomía . ^[33]
• Análisis de conglomerados : agrupamiento de puntos en el plano, ^[34] agrupamiento de enlace simple (un método de agrupamiento jerárquico ), ^[35] agrupamiento de teoría de grafos, ^[36] y agrupamiento de datos de expresión genética . ^[37]
• Construcción de árboles para difusión en redes de computadoras. ^[38]
• Registro de imágenes ^[39] y segmentación ^[40] – ver segmentación basada en árbol de expansión mínimo .
• 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 las utilizadas 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 ecotoxicológicos . ^[45]
• Observabilidad topológica en sistemas de potencia. ^[46]
• Medición de la homogeneidad de materiales bidimensionales. ^[47]
• Control de procesos Minimax . ^[48]
• Los árboles de expansión mínima también se pueden utilizar 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ínima 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 2021-12-10 . Un árbol de expansión mínima es un gráfico que consta de un subconjunto de aristas que, juntas, conectan todos los nodos conectados, mientras se minimiza 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 grafo (un árbol) con la suma mínima de pesos de aristas. Un bosque de expansión es una unión de los árboles de expansión para cada componente conectado del grafo.
3. "¿Los árboles de expansión mínimos de un gráfico ponderado tienen la misma cantidad 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) , Journal of the Association for Computing Machinery , 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 de tiempo lineal aleatorio para encontrar árboles de expansión mínimos", Journal of the Association for Computing Machinery , 42 (2): 321–328, doi : 10.1145/201019.201022 , MR  1409738, S2CID  832583
6. Pettie, Seth; Ramachandran, Vijaya (2002), "Minimización de la aleatoriedad en algoritmos de árboles de expansión mínimos, conectividad paralela y conjuntos máximos", Proc. 13.º Simposio ACM-SIAM sobre algoritmos discretos (SODA '02), San Francisco, California, págs. 713–722, ISBN 9780898715132{{citation}}: Mantenimiento de CS1: falta la ubicación del editor ( enlace ).
7. Chazelle, Bernard (2000), "Un algoritmo de árbol de expansión mínimo con complejidad de tipo Ackermann inverso", Journal of the Association for Computing Machinery , 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", Journal of the Association for Computing Machinery , 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ínimos en grafos dirigidos y no dirigidos". Combinatorica . 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 , MR  1279413.
12. Chong, Ka Wong; Han, Yijie; Lam, Tak Wah (2001), "Hilos concurrentes y algoritmo óptimo de árboles de expansión mínimos en paralelo", Journal of the Association for Computing Machinery , 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 aristas aleatorias", Matemáticas y ciencias de la computación, II (Versalles, 2002) , Trends Math., Basilea: Birkhäuser, pp. 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, Sr.  1261419
16. Garey, Michael R. ; Johnson, David S. (1979). Computadoras e intratabilidad: una guía para la teoría de la NP-completitud . Serie de libros sobre ciencias matemáticas (1.ª ed.). Nueva York: WH Freeman and Company . ISBN 9780716710455. Sr.  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 dos aristas y árboles de expansión más pequeños k", 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. Algorithms , 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č, Jan (2005). "Análisis de dependencia no proyectivo utilizando algoritmos de árbol de expansión" (PDF) . Proc. HLT/EMNLP .
23. Spira, 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 polilogarítmicos deterministas totalmente dinámicos para conectividad, árbol de expansión mínimo, 2 aristas y biconectividad", Journal of the Association for Computing Machinery , 48 (4): 723–760, doi :10.1145/502090.502095, MR  2144928, S2CID  7273552.
25. Chin, F.; Houck, D. (1978), "Algoritmos para actualizar árboles de expansión mínimos", Journal of Computer and System Sciences , 16 (3): 333–344, doi :10.1016/0022-0000(78)90022-3.
26. Chang, RS; Leu, SJ (1997), "Los árboles de expansión de etiquetado mínimo", Information Processing Letters , 63 (5): 277–282, doi :10.1016/s0020-0190(97)00127-0.
27. "Todo sobre el árbol de expansión de cuellos de botella". flashing-thoughts.blogspot.ru . 5 de junio de 2010 . Consultado el 4 de abril de 2018 .
28. "Copia archivada" (PDF) . Archivado desde el original (PDF) el 2013-06-12 . Consultado el 2014-07-02 .{{cite web}}: CS1 maint: archived copy as title (link)
29. Graham, RL ; Hell, Pavol (1985), "Sobre la historia del problema del árbol de expansión mínimo", Anales de la historia de la computación , 7 (1): 43–57, doi :10.1109/MAHC.1985.10011, MR  0783327, S2CID  10555375
30. Nicos Christofides , Análisis del peor caso de una nueva heurística para el problema del viajante de comercio, Informe 388, Escuela de Graduados de 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 emparejamiento perfecto ponderado. 12.º Simposio anual de la ACM sobre teoría de la computación (STOC '80). Nueva York, NY, EE. UU.: 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ínimos y máximos . 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 simple". Revista de la Royal Statistical Society . C (Estadística aplicada). 18 (1): 54–64. doi :10.2307/2346439. JSTOR  2346439.
36. Päivinen, Niina (1 de mayo de 2005). "Agrupamiento con un árbol de expansión mínimo de estructura similar a la de la escala libre". Pattern Recognition Letters . 26 (7): 921–930. Código Bibliográfico :2005PaReL..26..921P. doi :10.1016/j.patrec.2004.09.039.
37. Xu, Y.; Olman, V.; Xu, D. (1 de abril de 2002). "Agrupamiento de datos de expresión génica mediante un enfoque de teoría de grafos: una aplicación de árboles de expansión mínima". Bioinformática . 18 (4): 536–545. doi : 10.1093/bioinformatics/18.4.536 . PMID  12016051.
38. Dalal, Yogen K.; Metcalfe, Robert M. (1 de diciembre de 1978). "Reenvío de paquetes de difusión por ruta inversa". Comunicaciones de la ACM . 21 (12): 1040–1048. doi : 10.1145/359657.359665 . S2CID  5638057.
39. Ma, B.; Hero, A.; Gorman, J.; Michel, O. (2000). Registro de imágenes con algoritmo de árbol de expansión mínimo (PDF) . Conferencia internacional sobre procesamiento de imágenes. Vol. 1. págs. 481–484. doi :10.1109/ICIP.2000.901000. Archivado (PDF) desde el original el 2022-10-09.
40. P. Felzenszwalb, D. Huttenlocher: segmentación eficiente de imágenes basada en gráficos. IJCV 59(2) (septiembre de 2004)
41. Suk, Minsoo; Song, Ohyoung (1 de junio de 1984). "Extracción de características curvilíneas utilizando árboles de expansión mínima". Visión artificial, 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 mediante una construcción de árbol de expansión mínimo y dominancia de símbolos" (PDF) . Reconocimiento de gráficos. Avances y perspectivas recientes . Apuntes de clase en informática. Vol. 3088. Berlín Heidelberg: Springer-Verlag. pp. 329–340. ISBN. 978-3540224785. Archivado (PDF) del 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 . 12.ª 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 de árbol de expansión mínima (MST) en toxicología". Ecotoxicología y seguridad ambiental . 17 (2): 227–235. Bibcode :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ínimo". IEEE Transactions on Power Systems . 6 (2): 491–500. Bibcode :1991ITPSy...6..491M. doi :10.1109/59.76691.
47. Filliben, James J.; Kafadar, Karen ; Shier, Douglas R. (1 de enero de 1983). "Prueba de homogeneidad de superficies bidimensionales". Modelado matemático . 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, RN (1999). Estructura jerárquica en los mercados financieros. The European Physical Journal B-Condensed Matter and Complex Systems, 11(1), 193–197.
50. Djauhari, M. y Gan, S. (2015). Problema de optimalidad 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.

Lectura adicional

• 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 Pensilvania, abril. 78 pp.
• Kromkowski, John David. "Still Unmelted after All These Years", en Annual Editions, Race and Ethnic Relations, 17/e (2009 McGraw Hill) (Uso del árbol de expansión mínima 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 de árbol de expansión mínimo
• Implementado en QuickGraph para .Net