Árbol de expansión

Árbol que incluye todos los vértices de un gráfico.

Un árbol de expansión (bordes azules gruesos) de un gráfico de cuadrícula

En el campo matemático de la teoría de grafos , un árbol de expansión T de un grafo no dirigido G es un subgrafo que es un árbol que incluye todos los vértices de G. ^[1] En general, un gráfico puede tener varios árboles de expansión, pero un gráfico que no está conectado no contendrá un árbol de expansión (consulte acerca de los bosques de expansión a continuación). Si todas las aristas de G son también aristas de un árbol de expansión T de G , entonces G es un árbol y es idéntico a T (es decir, un árbol tiene un árbol de expansión único y es él mismo).

Aplicaciones

Varios algoritmos de búsqueda de rutas , incluido el algoritmo de Dijkstra y el algoritmo de búsqueda A* , construyen internamente un árbol de expansión como paso intermedio para resolver el problema.

Para minimizar el costo de las redes eléctricas, conexiones de cableado, tuberías, reconocimiento automático de voz, etc., la gente suele utilizar algoritmos que construyen gradualmente un árbol de expansión (o muchos de estos árboles) como pasos intermedios en el proceso de encontrar el árbol de expansión mínimo. . ^[2]

Internet y muchas otras redes de telecomunicaciones tienen enlaces de transmisión que conectan nodos entre sí en una topología de malla que incluye algunos bucles. Para evitar bucles de puente y bucles de enrutamiento , muchos protocolos de enrutamiento diseñados para dichas redes (incluido el protocolo de árbol de expansión , abrir primero la ruta más corta , el protocolo de enrutamiento de estado de enlace , el enrutamiento basado en árbol aumentado , etc.) requieren que cada enrutador recuerde un árbol de expansión. ^[3]

Un tipo especial de árbol de expansión, el árbol Xuong , se utiliza en teoría de grafos topológicos para encontrar incrustaciones de grafos con género máximo . Un árbol Xuong es un árbol de expansión tal que, en el gráfico restante, el número de componentes conectados con un número impar de aristas es lo más pequeño posible. Un árbol Xuong y una incrustación de género máximo asociada se pueden encontrar en tiempo polinomial . ^[4]

Definiciones

Un árbol es un gráfico conectado no dirigido sin ciclos . Es un árbol de expansión de un gráfico G si abarca G (es decir, incluye todos los vértices de G ) y es un subgrafo de G (cada arista del árbol pertenece a G ). Un árbol de expansión de un gráfico conectado G también se puede definir como un conjunto máximo de aristas de G que no contiene ningún ciclo, o como un conjunto mínimo de aristas que conectan todos los vértices.

Ciclos fundamentales

Agregar solo un borde a un árbol de expansión creará un ciclo; tal ciclo se llama ciclo fundamental con respecto a ese árbol. Hay un ciclo fundamental distinto para cada borde que no está en el árbol de expansión; por tanto, existe una correspondencia uno a uno entre los ciclos fundamentales y las aristas que no están en el árbol de expansión. Para un gráfico conectado con V vértices, cualquier árbol de expansión tendrá V  − 1 aristas y, por lo tanto, un gráfico de E aristas y uno de sus árboles de expansión tendrá E  −  V  + 1 ciclos fundamentales (el número de aristas restado por el número de aristas incluidas en un árbol de expansión; indicando el número de aristas no incluidas en el árbol de expansión). Para cualquier árbol de expansión dado, el conjunto de todos los ciclos fundamentales E  −  V  + 1 forma una base de ciclo , es decir, una base para el espacio de ciclo . ^[5]

Cortes fundamentales

La noción de un conjunto de cortes fundamental con respecto a un árbol de expansión dado es dual a la noción de ciclo fundamental. Al eliminar solo un borde del árbol de expansión, los vértices se dividen en dos conjuntos separados. El conjunto de corte fundamental se define como el conjunto de aristas que deben eliminarse del gráfico G para lograr la misma partición. Por lo tanto, cada árbol de expansión define un conjunto de conjuntos de cortes fundamentales V  − 1, uno para cada borde del árbol de expansión. ^[6]

La dualidad entre los conjuntos de cortes fundamentales y los ciclos fundamentales se establece al observar que los bordes del ciclo que no están en el árbol de expansión solo pueden aparecer en los conjuntos de cortes de los otros bordes del ciclo; y viceversa : las aristas de un cutset sólo pueden aparecer en aquellos ciclos que contengan la arista correspondiente al cutset. Esta dualidad también se puede expresar utilizando la teoría de las matroides , según la cual un árbol de expansión es una base de la matroide gráfica , un ciclo fundamental es el circuito único dentro del conjunto formado al agregar un elemento a la base, y se definen los cutsets fundamentales. de la misma manera desde la matroide dual . ^[7]

Bosques extensos

Una colección de árboles separados (no conectados) se describe como un bosque . Un bosque expansivo en un gráfico es un subgrafo que es un bosque con un requisito adicional. Hay dos requisitos incompatibles en uso, de los cuales uno es relativamente raro.

• Casi todos los libros y artículos de teoría de grafos definen un bosque expansivo como un bosque que abarca todos los vértices, lo que significa únicamente que cada vértice del gráfico es un vértice del bosque. Un gráfico conectado puede tener un bosque de expansión desconectado, como el bosque sin bordes, en el que cada vértice forma un árbol de un solo vértice. ^{[8] [9]}

• Algunos autores de teoría de grafos definen un bosque expansivo como un subgrafo acíclico máximo del gráfico dado, o de manera equivalente, un subgrafo que consta de un árbol expansivo en cada componente conectado del gráfico. ^[10]

Para evitar confusión entre estas dos definiciones, Gross y Yellen (2005) sugieren el término "bosque de extensión completa" para un bosque de extensión con el mismo número de componentes que el gráfico dado (es decir, un bosque máximo), mientras que Bondy y Murty (2008 ) en lugar de eso, llaman a este tipo de bosque "bosque de expansión máxima" (lo cual es redundante, ya que un bosque máximo contiene necesariamente todos los vértices). ^[11]

Contando árboles de expansión

La fórmula de Cayley cuenta el número de árboles generadores en un gráfico completo. Hay árboles en , árboles en y árboles en . ${\displaystyle 2^{2-2}=1}$ ${\displaystyle K_{2}}$ ${\displaystyle 3^{3-2}=3}$ ${\displaystyle K_{3}}$ ${\displaystyle 4^{4-2}=16}$ ${\displaystyle K_{4}}$

El número t ( G ) de árboles de expansión de un gráfico conexo es una invariante bien estudiada .

En gráficos específicos

En algunos casos, es fácil calcular t ( G ) directamente:

• Si G es en sí mismo un árbol, entonces t ( G ) = 1 .
• Cuando G es el gráfico de ciclo C _n con n vértices, entonces t ( G ) =  n .
• Para un gráfico completo con n vértices, la fórmula de Cayley ^[12] da el número de árboles de expansión como n ^{n  − 2} .
• Si G es el gráfico bipartito completo , entonces . ^[8] ${\displaystyle K_{p,q}}$ ${\displaystyle t(G)=p^{q-1}q^{p-1}}$
• Para el gráfico de hipercubo de n dimensiones , ^[13] el número de árboles de expansión es . ${\displaystyle Q_{n}}$ ${\displaystyle t(G)=2^{2^{n}-n-1}\prod _{k=2}^{n}k^{n \choose k}}$

En gráficos arbitrarios

De manera más general, para cualquier gráfico G , el número t ( G ) se puede calcular en tiempo polinómico como el determinante de una matriz derivada del gráfico, utilizando el teorema del árbol matricial de Kirchhoff . ^[14]

Específicamente, para calcular t ( G ), se construye la matriz laplaciana del gráfico, una matriz cuadrada en la que las filas y columnas están indexadas por los vértices de G. La entrada en la fila i y la columna j es uno de tres valores:

• El grado del vértice i , si i  =  j ,
• −1, si los vértices i y j son adyacentes, o
• 0, si los vértices i y j son diferentes entre sí pero no adyacentes.

La matriz resultante es singular , por lo que su determinante es cero. Sin embargo, eliminar la fila y la columna de un vértice elegido arbitrariamente conduce a una matriz más pequeña cuyo determinante es exactamente  t ( G ).

Contracción de eliminación

Si G es un gráfico o multigrafo y e es una arista arbitraria de G , entonces el número t ( G ) de árboles de expansión de G satisface la recurrencia de deleción-contracción t ( G ) =  t ( G  −  e ) +  t ( G / e ), donde G  −  e es el multigrafo obtenido al eliminar e y G / e es la contracción de G por e . ^[15] El término t ( G  −  e ) en esta fórmula cuenta los árboles de expansión de  G que no usan el borde  e , y el término t ( G / e ) cuenta los árboles de expansión de  G que usan  e .

En esta fórmula, si el gráfico dado G es un multigrafo , o si una contracción hace que dos vértices estén conectados entre sí por múltiples aristas, entonces las aristas redundantes no deben eliminarse, ya que eso llevaría a un total incorrecto. Por ejemplo, un gráfico de enlaces que conecta dos vértices mediante k aristas tiene k árboles de expansión diferentes, cada uno de los cuales consta de uno solo de estos aristas.

polinomio tutte

El polinomio de Tutte de un gráfico se puede definir como una suma, sobre los árboles generadores del gráfico, de términos calculados a partir de la "actividad interna" y la "actividad externa" del árbol. Su valor en los argumentos (1,1) es el número de árboles de expansión o, en un gráfico desconectado, el número de bosques de expansión máximos. ^[dieciséis]

El polinomio de Tutte también se puede calcular utilizando una recurrencia de contracción-deleción, pero su complejidad computacional es alta: para muchos valores de sus argumentos, calcularlo exactamente es #P-completo , y también es difícil de aproximar con una relación de aproximación garantizada . El punto (1,1), en el que se puede evaluar utilizando el teorema de Kirchhoff, es una de las pocas excepciones. ^[17]

Algoritmos

Construcción

Se puede encontrar un único árbol de expansión de un gráfico en tiempo lineal mediante una búsqueda en profundidad o en amplitud . Ambos algoritmos exploran el gráfico dado, comenzando desde un vértice arbitrario v , recorriendo los vecinos de los vértices que descubren y agregando cada vecino inexplorado a una estructura de datos que se explorará más adelante. Se diferencian en si esta estructura de datos es una pila (en el caso de la búsqueda en profundidad) o una cola (en el caso de la búsqueda en amplitud). En cualquier caso, se puede formar un árbol de expansión conectando cada vértice, distinto del vértice raíz v , al vértice desde el cual se descubrió. Este árbol se conoce como árbol de búsqueda en profundidad o árbol de búsqueda en amplitud según el algoritmo de exploración de gráficos utilizado para construirlo. ^[18] Los árboles de búsqueda en profundidad son un caso especial de una clase de árboles de expansión llamados árboles de Trémaux , que llevan el nombre del descubridor de la búsqueda en profundidad en el siglo XIX. ^[19]

Los árboles de expansión son importantes en la computación distribuida y paralela, como una forma de mantener las comunicaciones entre un conjunto de procesadores; consulte, por ejemplo, el protocolo Spanning Tree utilizado por los dispositivos de capa de enlace OSI o el Shout (protocolo) para informática distribuida. Sin embargo, los métodos de profundidad y amplitud para construir árboles de expansión en computadoras secuenciales no son adecuados para computadoras paralelas y distribuidas. ^[20] En cambio, los investigadores han ideado varios algoritmos más especializados para encontrar árboles de expansión en estos modelos de cálculo. ^[21]

Mejoramiento

En ciertos campos de la teoría de grafos, suele ser útil encontrar un árbol de expansión mínimo de un gráfico ponderado . También se han estudiado otros problemas de optimización en árboles de expansión, incluido el árbol de expansión máximo, el árbol mínimo que abarca al menos k vértices, el árbol de expansión con la menor cantidad de aristas por vértice , el árbol de expansión con el mayor número de hojas , el árbol de expansión con la menor cantidad de hojas (estrechamente relacionado con el problema de la trayectoria hamiltoniana ), el árbol generador de diámetro mínimo y el árbol generador de dilatación mínima. ^{[22] [23]}

También se han estudiado problemas de árbol de expansión óptimo para conjuntos finitos de puntos en un espacio geométrico como el plano euclidiano . Para tal entrada, un árbol de expansión es nuevamente un árbol que tiene como vértices los puntos dados. La calidad del árbol se mide de la misma forma que en un gráfico, utilizando la distancia euclidiana entre pares de puntos como peso para cada arista. Así, por ejemplo, un árbol de expansión mínimo euclidiano es lo mismo que un árbol de expansión mínimo de un gráfico en un gráfico completo con pesos de borde euclidianos. Sin embargo, no es necesario construir este gráfico para resolver el problema de optimización; El problema del árbol de expansión mínimo euclidiano, por ejemplo, se puede resolver de manera más eficiente en tiempo O ( n  log  n ) construyendo la triangulación de Delaunay y luego aplicando un algoritmo de árbol de expansión mínimo de gráfico plano de tiempo lineal a la triangulación resultante. ^[22]

Aleatorización

Un árbol de expansión elegido aleatoriamente entre todos los árboles de expansión con igual probabilidad se llama árbol de expansión uniforme . El algoritmo de Wilson se puede utilizar para generar árboles de expansión uniformes en tiempo polinómico mediante un proceso de realizar un recorrido aleatorio sobre el gráfico dado y borrar los ciclos creados por este recorrido. ^[24]

Un modelo alternativo para generar árboles de expansión de forma aleatoria pero no uniforme es el árbol de expansión mínimo aleatorio . En este modelo, a los bordes del gráfico se les asignan pesos aleatorios y luego se construye el árbol de expansión mínimo del gráfico ponderado. ^[25]

Enumeración

Debido a que un gráfico puede tener exponencialmente muchos árboles de expansión, no es posible enumerarlos todos en tiempo polinómico . Sin embargo, se conocen algoritmos que enumeran todos los árboles de expansión en tiempo polinomial por árbol. ^[26]

En gráficos infinitos

Todo grafo finito conexo tiene un árbol de expansión. Sin embargo, para infinitos gráficos conectados, la existencia de árboles de expansión es equivalente al axioma de elección . Un grafo infinito es conexo si cada par de sus vértices forma el par de puntos finales de un camino finito. Al igual que con los gráficos finitos, un árbol es un gráfico conectado sin ciclos finitos, y un árbol de expansión se puede definir como un conjunto acíclico máximo de aristas o como un árbol que contiene todos los vértices. ^[27]

Los árboles dentro de un gráfico pueden estar parcialmente ordenados por su relación de subgrafo, y cualquier cadena infinita en este orden parcial tiene un límite superior (la unión de los árboles en la cadena). El lema de Zorn , uno de los muchos enunciados equivalentes al axioma de elección, requiere que un orden parcial en el que todas las cadenas estén acotadas superiormente tenga un elemento máximo; en el orden parcial de los árboles del gráfico, este elemento máximo debe ser un árbol de expansión. Por lo tanto, si se supone el lema de Zorn, todo gráfico infinito conectado tiene un árbol de expansión. ^[27]

En la otra dirección, dada una familia de conjuntos , es posible construir un gráfico infinito tal que cada árbol de expansión del gráfico corresponda a una función de elección de la familia de conjuntos. Por lo tanto, si todo gráfico infinito conectado tiene un árbol de expansión, entonces el axioma de elección es verdadero. ^[28]

En multigrafos dirigidos

La idea de un árbol de expansión se puede generalizar a multigrafos dirigidos. ^[29] Dado un vértice v en un multigrafo dirigido G , un árbol de expansión orientado T con raíz en v es un subgrafo acíclico de G en el que cada vértice distinto de v tiene un grado superior a 1. Esta definición sólo se satisface cuando las "ramas" de T apuntar hacia​

Ver también

• Algoritmo de inundación
• Buen árbol de expansión : árbol de expansión para gráficos planos integrados

Referencias

1. "Árbol". Documentación de NetworkX 2.6.2 . Consultado el 10 de diciembre de 2021 . Para árboles y arborescencia, se puede agregar el adjetivo "que se extiende" para designar que el gráfico, cuando se considera un bosque/ramificación, consiste en un único árbol/arborescencia que incluye todos los nodos del gráfico.
2. Graham, RL; Demonios, Pavol (1985). "Sobre la historia del problema del árbol de expansión mínima" (PDF) .
3. Borg, Anita. "Folclore del diseño de protocolos de red". YouTube . Investigación de Microsoft . Consultado el 13 de mayo de 2022 .
4. Beineke, Lowell W .; Wilson, Robin J. (2009), Temas de teoría de grafos topológicos , Enciclopedia de Matemáticas y sus Aplicaciones, vol. 128, Cambridge University Press, Cambridge, pág. 36, doi :10.1017/CBO9781139087223, ISBN 978-0-521-80230-7, señor  2581536
5. Kocay y Kreher (2004), págs. 65–67.
6. Kocay y Kreher (2004), págs. 67–69.
7. Oxley, JG (2006), Teoría matroide, Textos de posgrado en matemáticas de Oxford , vol. 3, Oxford University Press, pág. 141, ISBN 978-0-19-920250-8.
8. Hartsfield, Nora; Ringel, Gerhard (2003), Perlas de la teoría de grafos: una introducción completa , Publicaciones Courier Dover, pág. 100, ISBN 978-0-486-43232-8.
9. Cameron, Peter J. (1994), Combinatoria: temas, técnicas, algoritmos, Cambridge University Press, pág. 163, ISBN 978-0-521-45761-3.
10. Bollobás, Béla (1998), Teoría de grafos moderna, Textos de posgrado en matemáticas, vol. 184, Springer, pág. 350, ISBN 978-0-387-98488-9; Mehlhorn, Kurt (1999), LEDA: una plataforma para la computación geométrica y combinatoria, Cambridge University Press, pág. 260, ISBN 978-0-521-56329-1.
11. Bruto, Jonathan L.; Yellen, Jay (2005), Teoría de grafos y sus aplicaciones (2ª ed.), CRC Press, p. 168, ISBN 978-1-58488-505-4; Bondy, JA; Murty, USR (2008), Teoría de grafos, Textos de posgrado en matemáticas, vol. 244, Springer, pág. 578, ISBN 978-1-84628-970-5.
12. Aigner, Martín ; Ziegler, Günter M. (1998), Pruebas de EL LIBRO , Springer-Verlag , págs. 141-146.
13. Harary, Frank ; Hayes, John P.; Wu, Horng-Jyh (1988), "Un estudio de la teoría de los gráficos de hipercubo", Computadoras y matemáticas con aplicaciones , 15 (4): 277–289, doi :10.1016/0898-1221(88)90213-1, hdl : 2027.42/27522 , SEÑOR  0949280.
14. Kocay, William; Kreher, Donald L. (2004), "5.8 El teorema del árbol de la matriz", Gráficos, algoritmos y optimización, matemáticas discretas y sus aplicaciones, CRC Press, págs. 111-116, ISBN 978-0-203-48905-5.
15. Kocay y Kreher (2004), pág. 109.
16. Bollobás (1998), pág. 351.
17. Goldberg, Luisiana ; Jerrum, M. (2008), "Inaproximabilidad del polinomio de Tutte", Información y Computación , 206 (7): 908–929, arXiv : cs/0605140 , doi :10.1016/j.ic.2008.04.003; Jaeger, F.; Vértigan, DL; Welsh, DJA (1990), "Sobre la complejidad computacional de los polinomios de Jones y Tutte", Mathematical Proceedings of the Cambridge Philosophical Society , 108 : 35–53, doi :10.1017/S0305004100068936.
18. Kozen, Dexter (1992), El diseño y análisis de algoritmos, monografías en informática, Springer, p. 19, ISBN 978-0-387-97687-7.
19. de Fraysseix, Hubert; Rosenstiehl, Pierre (1982), "Una caracterización de la planaridad con una búsqueda en profundidad", Teoría de grafos (Cambridge, 1981) , Ann. Matemáticas discretas, vol. 13, Amsterdam: Holanda Septentrional, págs. 75–80, SEÑOR  0671906.
20. Reif, John H. (1985), "La búsqueda en profundidad es inherentemente secuencial", Information Processing Letters , 20 (5): 229–234, doi :10.1016/0020-0190(85)90024-9, MR  0801987.
21. Gallager, RG; Humboldt, Pensilvania; Spira, PM (1983), "Un algoritmo distribuido para árboles de expansión de peso mínimo", ACM Transactions on Programming Languages ​​and Systems , 5 (1): 66–77, doi : 10.1145/357195.357200 , archivado desde el original el 8 de diciembre. 2023; Gazit, Hillel (1991), "Un algoritmo paralelo aleatorio óptimo para encontrar componentes conectados en un gráfico", SIAM Journal on Computing , 20 (6): 1046–1067, doi :10.1137/0220066, MR  1135748; Bader, David A.; Cong, Guojing (2005), "Un algoritmo de árbol de expansión paralelo rápido para multiprocesadores simétricos (SMP)" (PDF) , Journal of Parallel and Distributed Computing , 65 (9): 994–1006, doi :10.1016/j.jpdc. 2005.03.011, archivado desde el original (PDF) el 23 de septiembre de 2015.
22. Eppstein, David (1999), "Árboles de expansión y llaves inglesas" (PDF) , en Sack, J.-R. ; Urrutia, J. (eds.), Handbook of Computational Geometry , Elsevier, págs. 425–461, archivado (PDF) desde el original el 2 de agosto de 2023..
23. Wu, Bang Ye; Chao, Kun-Mao (2004), Árboles de expansión y problemas de optimización , CRC Press, ISBN 1-58488-436-3.
24. Wilson, David Bruce (1996), "Generación de árboles de expansión aleatorios más rápidamente que el tiempo de cobertura", Actas del vigésimo octavo simposio anual ACM sobre teoría de la informática (STOC 1996) , págs. 296–303, doi :10.1145 /237814.237880, SEÑOR  1427525.
25. McDiarmid, Colin; Johnson, Theodore; Stone, Harold S. (1997), "Sobre la búsqueda de un árbol de expansión mínimo en una red con pesos aleatorios" (PDF) , Estructuras y algoritmos aleatorios , 10 (1–2): 187–204, doi :10.1002/(SICI) 1098-2418(199701/03)10:1/2<187::AID-RSA10>3.3.CO;2-Y, SEÑOR  1611522.
26. Gabow, Harold N .; Myers, Eugene W. (1978), "Encontrar todos los árboles de expansión de gráficos dirigidos y no dirigidos", SIAM Journal on Computing , 7 (3): 280–287, doi :10.1137/0207024, MR  0495152
27. Serre, Jean-Pierre (2003), Árboles , Monografías de Springer en Matemáticas, Springer, p. 23.
28. Soukup, Lajos (2008), "Combinatoria infinita: de finito a infinito", Horizontes de la combinatoria , Bolyai Soc. Matemáticas. Stud., vol. 17, Berlín: Springer, págs. 189–213, doi :10.1007/978-3-540-77200-2_10, MR  2432534. Véase en particular el Teorema 2.1, págs. 192-193.
29. Levine, Lionel (2011). "Grupos de pilas de arena y árboles de expansión de gráficos de líneas dirigidas". Revista de teoría combinatoria, serie A. 118 (2): 350–364. arXiv : 0906.2809 . doi : 10.1016/j.jcta.2010.04.001 . ISSN  0097-3165.