Hispanopedia Wiki
Articulo de referencia

árbol de expansión mínima

Un grafo planar y su árbol de expansión mínima. Cada arista está etiquetada con su peso, que en este caso es aproximadamente proporcional a su longitud. En teoría de grafos , un...

Hispanopedia WikiContenido en espanolLectura gratuita

Un grafo planar y su árbol de expansión mínima. Cada arista está etiquetada con su peso, que en este caso es aproximadamente proporcional a su longitud.

En teoría de grafos , un árbol de expansión mínima ( MST ) o árbol de expansión de peso mínimo es un subconjunto de las aristas de un grafo no dirigido conexo y ponderado que conecta todos los vértices entre sí, sin ciclos 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 ponderado (no necesariamente conexo) tiene un bosque de expansión mínima , que es una unión de los árboles de expansión mínima para sus componentes conexas .

Existen numerosos casos de uso para los árboles de expansión mínima. Un ejemplo es una empresa de telecomunicaciones que intenta instalar cableado en un nuevo vecindario. Si está restringida a enterrar el cable solo a lo largo de ciertas rutas (por ejemplo, carreteras), entonces existiría un grafo que contendría los puntos (por ejemplo, casas) conectados por esas rutas. Algunas rutas podrían ser más costosas, ya sea por ser más largas o por requerir que el cable se entierre a mayor profundidad; estas rutas estarían representadas por aristas con mayor peso. La moneda es una unidad aceptable para el peso de las aristas; no es necesario que las longitudes de las aristas cumplan las reglas geométricas habituales, como la desigualdad triangular . Un árbol de expansión para ese grafo sería un subconjunto de esas rutas que no tiene ciclos pero que aún conecta todas las casas; podrían existir varios árboles de expansión posibles. Un árbol de expansión mínima sería aquel con el menor costo total, representando la ruta menos costosa para instalar el cable.

Propiedades

Posible multiplicidad

Si hay n vértices en el grafo, 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 grafo. En la figura, los dos árboles que se muestran debajo del grafo representan dos posibles árboles de expansión mínima para dicho grafo.

Puede haber varios árboles de expansión mínima del mismo peso; en particular, si todos los pesos de las aristas de un grafo dado son iguales, entonces cada árbol de expansión de ese grafo es mínimo.

Unicidad

Si cada arista tiene un peso distinto, entonces solo habrá un árbol de expansión mínimo único . Esto se cumple en muchas situaciones realistas, como el ejemplo de la compañía de telecomunicaciones mencionado anteriormente, donde es improbable que dos caminos tengan exactamente el mismo costo. Esto también se aplica a los bosques de expansión.

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, existe al menos una arista que pertenece a una pero no a la otra. Entre dichas aristas, sea e 1 la que tiene 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 1 está en A.
  3. Como B es un MST, { e 1 } ∪ B debe contener un ciclo C con e 1 .
  4. Como árbol, A no contiene ciclos, por lo tanto C debe tener una arista e 2 que no está en A.
  5. Dado que e 1 fue elegido como el único borde de menor peso 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 .
  6. Como e 1 y e 2 son parte del ciclo C , reemplazar e 2 con e 1 en B produce un árbol de expansión con un peso menor.
  7. Esto contradice la suposición de que B es un MST.

En términos más generales, si los pesos de las aristas no son todos distintos, entonces solo 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 coste mínimo

Si los pesos son positivos , entonces un árbol de expansión mínima 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 ciclista

Para cualquier ciclo C en el grafo, 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 1. Entonces, al eliminar e, T 1 se dividirá 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 subárboles diferentes, es decir, reconecta los subárboles en un árbol T 2 con un peso menor que el de T 1 , porque el peso de f es menor que el peso de e .

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 }, entonces V – S = { C , F }, entonces hay 3 posibilidades de la arista que cruza el corte ( S , V – S ) , que 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 grafo, 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 grafo.

Demostración: Supongamos que existe un MST T que no contiene e . Si añadimos e a T , se formará un ciclo que cruza el corte una vez en e y vuelve a cruzarlo en otra arista e' . Si eliminamos e' , obtenemos un árbol de expansión T ∖{ e' } ∪ { e } con un peso estrictamente menor que T. Esto contradice la suposición de que T era un MST.

Siguiendo un razonamiento similar, si más de una arista tiene el peso mínimo a través de un corte, entonces cada una de esas aristas está contenida en algún árbol de expansión mínima.

Ventaja de coste mínimo

Si la arista de coste mínimo e de un grafo es única, entonces esta arista se incluye en cualquier MST.

Prueba: si e no se incluyera en el MST, eliminar cualquiera de las aristas (de mayor coste) en el ciclo formado después de añadir e al MST, daría como resultado 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 grafo contraído más T da el MST del grafo antes de la contracción. [ 4 ]

Algoritmos

En todos los algoritmos que se describen a continuación, m es el número de aristas del grafo y n es el número de vértices.

Algoritmos clásicos

El primer algoritmo para encontrar un árbol de expansión mínima fue desarrollado por el científico checo Otakar Borůvka en 1926 (véase el algoritmo de Borůvka ). Su propósito era lograr una cobertura eléctrica eficiente de Moravia . El algoritmo se desarrolla en una secuencia de etapas. En cada etapa, denominada paso de Borůvka , identifica un bosque F formado por la arista de peso mínimo incidente a cada vértice del grafo G , y luego forma el grafo G₁ = G \ F como entrada para el siguiente paso. Aquí, G \ F denota el grafo derivado de G mediante la contracción de aristas en F (por la propiedad de corte , estas aristas pertenecen al MST). Cada paso de Borůvka tiene una complejidad temporal lineal. Dado que el número de vértices se reduce al menos a la mitad en cada paso, el algoritmo de Borůvka tiene una complejidad temporal de O ( m log n ) . [ 4 ]

A second algorithm is Prim's algorithm, which was invented by Vojtěch Jarník in 1930 and rediscovered by Prim in 1957 and Dijkstra in 1959. Basically, it grows the MST (T) one edge at a time. Initially, T contains an arbitrary vertex. In each step, T is augmented with a least-weight edge (x,y) such that x is in T and y is not yet in T. By the Cut property, all edges added to T are in the MST. Its run-time is either O(m log n) or O(m + n log n), depending on the data-structures used.

A third algorithm commonly in use is Kruskal's algorithm, which also takes O(m log n) time.

A fourth algorithm, not as commonly used, is the reverse-delete algorithm, which is the reverse of Kruskal's algorithm. Its runtime is O(m log n (log log n)3).

All four of these are greedy algorithms. Since they run in polynomial time, the problem of finding such trees is in FP, and related decision problems such as determining whether a particular edge is in the MST or determining if the minimum total weight exceeds a certain value are in P.

Faster algorithms

Several researchers have tried to find more computationally-efficient algorithms.

In a comparison model, in which the only allowed operations on edge weights are pairwise comparisons, Karger, Klein & Tarjan (1995) found a linear time randomized algorithm based on a combination of Borůvka's algorithm and the reverse-delete algorithm.[5][6]

El algoritmo de comparación no aleatorio más rápido con complejidad conocida, desarrollado por Bernard Chazelle , se basa en el montículo 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 despacio, por lo que, a efectos prácticos, puede considerarse una constante no mayor que 4; por lo tanto, el algoritmo de Chazelle se ejecuta en un tiempo casi 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 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áximonorte′2metro/norte′{\displaystyle {\tfrac {n'}{2^{m/n'}}}}Por lo tanto, se necesitan como máximo log* n fases, lo que da un tiempo de ejecución lineal para grafos densos. [ 4 ]

Existen otros algoritmos que funcionan en tiempo lineal en grafos densos. [ 7 ] [ 10 ]

pesos enteros

Si los pesos de las aristas son enteros representados en binario, se conocen algoritmos deterministas que resuelven el problema en O ( m + n ) operaciones enteras. [ 11 ] Si el problema puede resolverse de forma determinista para un grafo general en tiempo lineal mediante un algoritmo basado en comparaciones sigue siendo una cuestión abierta.

Grafos planares

Se conocen algoritmos deterministas que resuelven el problema para grafos planares en tiempo lineal. [ 12 ] [ 13 ] Por la característica de Euler de los grafos planares, m ≤ 3 n - 6 ∈ O ( n ) , por lo que esto es en tiempo O ( n ) .

Árboles de decisión

Dado un grafo G con nodos y aristas fijos pero pesos 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, "¿Es el peso de la arista entre x e y 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 temporal de un DT es el mayor número de consultas necesarias para encontrar el MST, que es simplemente la profundidad del DT. Un DT para un grafo G se denomina óptimo si tiene la menor profundidad de todos los DT correctos para G.

Para cada entero r , es posible encontrar árboles de decisión óptimos para todos los grafos con r vértices mediante búsqueda por fuerza bruta . Esta búsqueda se lleva a cabo en dos pasos.

A. Generar todos los DT potenciales

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

(r4)(2r2)=r2(r2+2).{\displaystyle {(r^{4})}^{(2^{r^{2}})}=r^{2^{(r^{2}+2)}}.}

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

  • El número de tales permutaciones es como máximo ( r 2 )! .
  • Para cada permutación, resuelva el problema del MST en el grafo dado utilizando cualquier algoritmo existente y compare el resultado con la respuesta proporcionada por el DT.
  • El tiempo de ejecución de cualquier algoritmo MST es como máximo r 2 , por lo que el tiempo total requerido para comprobar todas las permutaciones es como máximo ( r 2 + 1)! .

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

2(r2)⋅r2(r2+2)⋅(r2+1)¡,{\displaystyle 2^{r \choose 2}\cdot r^{2^{(r^{2}+2)}}\cdot (r^{2}+1)!,}

lo cual es menor que

22r2+o(r).{\displaystyle 2^{2^{r^{2}+o(r)}}.}

Algoritmo óptimo

Seth Pettie y Vijaya Ramachandran han encontrado un algoritmo determinista de árbol de expansión mínima basado en comparaciones que es demostrablemente óptimo. [ 4 ] A continuación se presenta 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 con r vértices. Esto se puede hacer en tiempo O ( n ) (véase Árboles de decisión más arriba).
  2. Dividir el grafo en componentes con un máximo de r vértices cada uno. Esta partición utiliza un montón suave , que "corromperá" un pequeño número de aristas del grafo.
  3. Utilice los árboles de decisión óptimos para encontrar un MST para el subgrafo no corrupto dentro de cada componente.
  4. Contraer cada componente conexa generada por los MST a un único vértice y aplicar cualquier algoritmo que funcione en grafos densos en tiempo O ( m ) a la contracción del subgrafo no corrupto.
  5. Agregue nuevamente las aristas corruptas al bosque resultante para formar un subgrafo que garantice contener el árbol de expansión mínima y que sea menor por un factor constante que el grafo inicial. Aplique el algoritmo óptimo recursivamente a este grafo.

El tiempo de ejecución de todos los pasos del algoritmo es O ( m ) , excepto el paso de uso de 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 superar al árbol de decisión óptimo. Por lo tanto, este algoritmo posee la peculiar propiedad de ser demostrablemente óptimo, aunque se desconozca su complejidad temporal .

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 ) . [ 14 ] [ 15 ]

El problema también puede abordarse de forma 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ínima distribuido .

MST en grafos completos con pesos aleatorios

Alan M. Frieze demostró que, dado un grafo completo con n vértices y pesos de aristas que son variables aleatorias independientes idénticamente distribuidas con función de distribuciónF{\displaystyle F}satisfactorioF′(0)>0{\displaystyle F'(0)>0}, entonces a medida que n se acerca a +∞, el peso esperado del MST se acercaζ(3)/F′(0){\displaystyle \zeta (3)/F'(0)}, dóndeζ{\displaystyle \zeta }es la función zeta de Riemann (más específicamente esζ(3){\displaystyle \zeta (3)}La constante de Apéry ). Frieze y Steele también demostraron la convergencia en probabilidad. Svante Janson demostró un teorema del límite central para el peso del MST.

Para pesos aleatorios uniformes en[0,1]{\displaystyle [0,1]}, el tamaño esperado exacto del árbol de expansión mínima se ha calculado para grafos completos pequeños. [ 16 ]

Variante fraccionaria

Existe una variante fraccionaria del MST, en la que cada arista puede aparecer "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 es ni vacío ni 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∑mi∈miF(mi)⋅w(mi){\displaystyle \sum _{e\in E}f(e)\cdot w(e)}es lo más pequeño posible.

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∑mi∈miF(mi)⋅w(mi){\displaystyle \sum _{e\in E}f(e)\cdot w(e)}En ese caso, el conjunto generador resultante es necesariamente un árbol, ya que si contuviera un ciclo, se podría eliminar una arista sin afectar la condición de generador. Por lo tanto, el problema del conjunto generador fraccional mínimo es una relajación del problema del MST y también se le puede llamar problema del MST fraccional.

El problema del MST fraccional se puede resolver en tiempo polinomial utilizando el método del elipsoide . [ 17 ] : 248 Sin embargo, si añadimos el requisito de que f ( e ) debe ser semi-entero (es decir, f ( e ) debe estar en {0, 1/2, 1}), entonces el problema se vuelve NP-difícil , [ 17 ] : 248 ya que incluye como caso especial el problema del ciclo hamiltoniano : en unnorte{\displaystyle n}-grafo no ponderado de vértices, un MST de medio entero de pesonorte/2{\displaystyle n/2}Solo se puede obtener asignando un peso de 1/2 a cada arista de un ciclo hamiltoniano.

Otras variantes

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

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 fueron inventados originalmente, como se mencionó anteriormente). [ 33 ] Se invocan como subrutinas en algoritmos para otros problemas, incluido el algoritmo de Christofides para aproximar el problema del viajante de comercio , [ 34 ] aproximar el problema del corte mínimo multiterminal (que es equivalente en el caso de un solo terminal al problema del flujo máximo ), [ 35 ] y aproximar el emparejamiento perfecto ponderado de costo mínimo . [ 36 ]

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

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ínima es un grafo que consta del subconjunto de aristas que conectan todos los nodos conectados, minimizando la suma total de los 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ínima es un subgrafo del grafo (un árbol) con la suma mínima de pesos de aristas. Un bosque de expansión es la unión de los árboles de expansión para cada componente conexa del grafo.
  3. ↑ "¿Los árboles de expansión mínima de un grafo ponderado tienen el mismo número de aristas con un peso dado?" . cs.stackexchange.com . Consultado el 4 de abril de 2018 .
  4. 1 2 3 4 5 Pettie, Seth; Ramachandran, Vijaya (2002), "Un algoritmo óptimo de árbol de expansión mínima" (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 aleatorio de tiempo lineal para encontrar árboles de expansión mínima", 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), "Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms" , Proc. 13th ACM-SIAM Symposium on Discrete Algorithms (SODA '02) , San Francisco, California, pp. 713–722 , ISBN  978-0-89871-513-2{{citation}}: CS1 mantenimiento: falta el editor de ubicación ( enlace ) .
  7. 1 2 Chazelle, Bernard (2000), "Un algoritmo de árbol de expansión mínima con complejidad de tipo Ackermann inversa", Journal of the Association for Computing Machinery , 47 (6): 1028– 1047, doi : 10.1145/355541.355562 , MR 1866456 , S2CID 6276962  .
  8. ↑ Chazelle, Bernard (2000), "The soft heap: an approxim priority queue with optimal error rate", 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). "Montículos de Fibonacci y sus usos en algoritmos mejorados de optimización de redes" . Journal of the 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 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. ↑ Matsui, Tomomi (1995-03-10). "El problema del árbol de expansión mínima en un grafo planar". Matemáticas Aplicadas Discretas . 58 (1): 91– 94. doi : 10.1016/0166-218X(94)00095-U . ISSN 0166-218X . 
  13. ↑ Cheriton, David; Tarjan, Robert Endre (diciembre de 1976). "Finding Minimum Spanning Trees" . SIAM Journal on Computing . 5 (4): 724–742 . doi : 10.1137/0205051 . ISSN 0097-5397 . 
  14. ↑ Chong, Ka Wong; Han, Yijie; Lam, Tak Wah (2001), "Hilos concurrentes y algoritmo óptimo de árboles de expansión mínima en paralelo", Journal of the Association for Computing Machinery , 48 (2): 297–323 , doi : 10.1145/375827.375847 , MR 1868718 , S2CID 1778676  .
  15. ↑ Pettie, Seth; Ramachandran, Vijaya (2002), "Un algoritmo paralelo óptimo de tiempo y 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 .
  16. ↑ Steele, J. Michael (2002), "Árboles de expansión mínima para grafos con longitudes de aristas aleatorias", Matemáticas e informática, II (Versalles, 2002) , Trends Math., Basilea: Birkhäuser, pp. 223–245 , MR 1940139  
  17. 1 2 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, MR 1261419 
  18. ↑ Garey, Michael R.; Johnson , David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness . Serie de libros en ciencias matemáticas (1.ª ed.). Nueva York: WH Freeman and Company . ISBN  9780716710455. MR 0519066 . OCLC 247570676 .  ND12
  19. ↑ 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 .
  20. ↑ Eppstein, David (1992), "Finding the k smallest spanning trees", BIT , 32 (2): 237– 248, doi : 10.1007/BF01994879 , MR 1172188 , S2CID 121160520  .
  21. ↑ Frederickson, Greg N. (1997), "Estructuras de datos ambivalentes para conectividad dinámica de 2 aristas y k árboles de expansión más pequeños" , SIAM Journal on Computing , 26 (2): 484–538 , doi : 10.1137/S0097539792226825 , MR 1438526 .
  22. ↑ Jothi, Raja; Raghavachari, Balaji (2005), "Algoritmos de aproximación para el problema del árbol de expansión mínima con capacidad y sus variantes en el diseño de redes", ACM Trans. Algorithms , 1 (2): 265– 282, doi : 10.1145/1103963.1103967 , S2CID 8302085 
  23. ↑ Hu, TC (1961), "El problema de la ruta de máxima capacidad", Operations Research , 9 (6): 898–900 , doi : 10.1287/opre.9.6.898 , JSTOR 167055 .
  24. ↑ McDonald, Ryan; Pereira, Fernando; Ribarov, Kiril; Hajič, Jan (2005). "Análisis de dependencias no proyectivas mediante algoritmos de árboles de expansión" (PDF) . Proc. HLT/EMNLP .
  25. ↑ Simas, Tiago; Correia, Rion B.; Rocha, Luis M. (2021), "The distance backbone of complex networks", Journal of Complex Networks , 9 (6) cnab021, arXiv : 2103.04668 , doi : 10.1093/comnet/cnab021 , PMID 38348382 .
  26. ↑ Rozum, Jordan C.; Rocha, Luis M. (2021), "La estructura ultramétrica es la unión de todos los bosques de expansión mínima", Journal of Physics: Complexity , 5 (3): 035009, doi : 10.1088/2632-072X/ad679e , PMID 39131403 Este artículo incorpora texto de esta fuente, que está disponible bajo la licencia CC BY 4.0 . 
  27. ↑ Spira, PM; Pan, A. (1975), "Sobre la búsqueda y actualización de árboles de expansión y rutas más cortas" (PDF) , SIAM Journal on Computing , 4 (3): 375–380 , doi : 10.1137/0204032 , MR 0378466 .
  28. ↑ Holm, Jacob; de Lichtenberg, Kristian; Thorup, Mikkel (2001), "Algoritmos totalmente dinámicos deterministas polilogarítmicos para conectividad, árbol de expansión mínima, 2-aristas y biconectividad", Journal of the Association for Computing Machinery , 48 (4): 723–760 , doi : 10.1145/502090.502095 , MR 2144928 , S2CID 7273552  .
  29. ↑ Chin, 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.
  30. ↑ 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.
  31. ↑ "Todo sobre Bottleneck Spanning Tree" . flashing-thoughts.blogspot.ru . 5 de junio de 2010. Consultado el 4 de abril de 2018 .
  32. ↑ "Copia archivada" (PDF) . Archivado del original (PDF) el 12-06-2013 . Recuperado el 02-07-2014 .{{cite web}}: CS1 mantenimiento: copia archivada como título ( enlace )
  33. ↑ 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 , Bibcode : 1985IAHC....7a..43G , doi : 10.1109/MAHC.1985.10011 , MR 0783327 , S2CID 10555375  
  34. ↑ Nicos Christofides , Análisis del peor caso de una nueva heurística para el problema del viajante , Informe 388, Escuela de Posgrado de Administración Industrial, CMU, 1976.
  35. ↑ 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 .
  36. ↑ Supowit, Kenneth J.; Plaisted, David A.; Reingold, Edward M. (1980). Heurísticas para el 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 . 
  37. ↑ Sneath, PHA (1 de agosto de 1957). "La aplicación de las computadoras a la taxonomía" . Journal of General Microbiology . 17 (1): 201– 226. doi : 10.1099/00221287-17-1-201 . PMID 13475686 . 
  38. ↑ 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. pp. 252–257 . doi : 10.1145/73393.73419 .  
  39. ↑ Gower, JC; Ross, GJS (1969). "Árboles de expansión mínima y análisis de conglomerados de enlace simple". Journal of the Royal Statistical Society . C (Estadística Aplicada). 18 (1): 54– 64. doi : 10.2307/2346439 . JSTOR 2346439 . 
  40. ↑ Päivinen, Niina (1 de mayo de 2005). "Agrupamiento con un árbol de expansión mínima de estructura similar a la libre de escala". Pattern Recognition Letters . 26 (7): 921– 930. Bibcode : 2005PaReL..26..921P . doi : 10.1016/j.patrec.2004.09.039 .
  41. ↑ Xu, Y.; Olman, V.; Xu, D. (1 de abril de 2002). "Agrupación de datos de expresión génica mediante un enfoque basado en la teoría de grafos: una aplicación de árboles de expansión mínima" . Bioinformatics . 18 (4): 536– 545. doi : 10.1093/bioinformatics/18.4.536 . PMID 12016051 . 
  42. ↑ Dalal, Yogen K.; Metcalfe, Robert M. (1 de diciembre de 1978). "Reenvío de ruta inversa de paquetes de difusión" . Communications of the ACM . 21 (12): 1040– 1048. doi : 10.1145/359657.359665 . S2CID 5638057 . 
  43. ↑ Ma, B.; Hero, A.; Gorman, J.; Michel, O. (2000). Registro de imágenes con algoritmo de árbol de expansión mínima (PDF) . Conferencia Internacional sobre Procesamiento de Imágenes. Vol. 1. págs. 481–484 . doi : 10.1109/ICIP.2000.901000 . Archivado (PDF) del original el 9 de octubre de 2022.  
  44. ^ P. Felzenszwalb, D. Huttenlocher: Segmentación de imágenes eficiente basada en gráficos. IJCV 59(2) (septiembre de 2004)
  45. ↑ Suk, Minsoo; Song, Ohyoung (1 de junio de 1984). "Extracción de características curvilíneas mediante árboles de expansión mínima". Computer Vision, Graphics, and Image Processing . 26 (3): 400– 411. doi : 10.1016/0734-189X(84)90221-4 .
  46. ↑ Tapia, Ernesto; Rojas, Raúl (2004). "Reconocimiento de expresiones matemáticas manuscritas en línea mediante la construcción de un árbol de expansión mínima y la dominancia de símbolos" (PDF) . Reconocimiento gráfico. Avances y perspectivas recientes . Notas de clase en informática. Vol. 3088. Berlín Heidelberg: Springer-Verlag. pp. 329–340 . ISBN   978-3-540-22478-5Archivado (PDF) del original el 09/10/2022 .
  47. ↑ Ohlsson, H. (2004). Implementación de filtros FIR de baja complejidad utilizando un árbol de expansión mínima . 12.ª Conferencia Electrotécnica Mediterránea del IEEE (MELECON 2004). Vol. 1. pp. 261–264 . doi : 10.1109/MELCON.2004.1346826 .  
  48. ↑ 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 bibliográfico : 2006IJGIS..20..797A . doi : 10.1080/13658810600665111 . S2CID 2530748 . 
  49. ↑ 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. Bibcode : 1989EcoES..17..227D . doi : 10.1016/0147-6513(89)90042-0 . PMID 2737116 . 
  50. ↑ 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". IEEE Transactions on Power Systems . 6 (2): 491– 500. Bibcode : 1991ITPSy...6..491M . doi : 10.1109/59.76691 .
  51. ↑ Filliben, James J.; Kafadar, Karen ; Shier, Douglas R. (1 de enero de 1983). "Prueba de homogeneidad de superficies bidimensionales". Mathematical Modelling . 4 (2): 167– 189. doi : 10.1016/0270-0255(83)90026-X .
  52. ↑ Kalaba, Robert E. (1963), Teoría de grafos y control automático (PDF) , archivado del original (PDF) el 21 de febrero de 2016
  53. ↑ Mantegna, RN (1999). Estructura jerárquica en los mercados financieros . The European Physical Journal B-Condensed Matter and Complex Systems, 11(1), 193–197.
  54. ↑ Djauhari, M., & Gan, S. (2015). Problema de optimalidad de la topología de red en el análisis del mercado de valores . Physica A: Statistical Mechanics and Its Applications, 419, 108–114.

Lecturas adicionales

  • 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-7Capí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 págs.
  • Kromkowski, John David. "Aún sin derretirse después de todos estos años", en Ediciones anuales, Relaciones raciales y étnicas, 17.ª ed. (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).
  • Implementado en BGL, la biblioteca gráfica de Boost
  • Repositorio de algoritmos de Stony Brook - Códigos de árbol de expansión mínima
  • Implementado en QuickGraph para .Net
Obtenido de " https://en.wikipedia.org/w/index.php?title=Minimum_spanning_tree&oldid=1363457418 "
Lecturas relacionadas
6 articulos
Gráfico planarGráfico planarEn teoría de grafos , un grafo plano es un grafo que se puede incrustar en el plano , es decir, se puede dibujar en el plano de tal manera que sus ...Teoría de grafosTeoría de grafosEn matemáticas , la teoría de grafos es el estudio de los grafos , que son estructuras matemáticas utilizadas para modelar relaciones por pares ent...Gráfica (matemática discreta)Gráfica (matemática discreta)En matemáticas discretas , particularmente en teoría de grafos , un grafo es una estructura que consiste en un conjunto de objetos donde algunos pa...Conectividad (teoría de grafos)Conectividad (teoría de grafos)Este gráfico se desconecta cuando se elimina el nodo más a la derecha en el área gris de la izquierda. Este gráfico se desconecta cuando se elimina...Vertex (graph theory)Vertex (graph theory)In discrete mathematics, and more specifically in graph theory, a vertex (plural vertices) or node is the fundamental unit of which graphs are form...Ciclo (teoría de grafos)Ciclo (teoría de grafos)En teoría de grafos , un ciclo en un grafo es un camino no vacío en el que solo el primer y el último vértice son iguales. Un ciclo dirigido en un ...