Árbol de expansión

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

Un árbol de expansión (bordes azules intensos) 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 grafo puede tener varios árboles de expansión, pero un grafo que no esté conectado no contendrá un árbol de expansión (ver sobre 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., las personas a menudo utilizan algoritmos que construyen gradualmente un árbol de expansión (o muchos árboles de este tipo) 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 (incluidos Spanning Tree Protocol , Open Shortest Path First , Link-state Routing Protocol , Augmented Tree-based Routing , etc.) requieren que cada enrutador recuerde un árbol de expansión. ^[3]

En la teoría de grafos topológicos se utiliza un tipo especial de árbol de expansión, el árbol Xuong , para encontrar incrustaciones de grafos con género máximo . Un árbol Xuong es un árbol de expansión tal que, en el grafo 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 grafo conexo no dirigido sin ciclos . Es un árbol de expansión de un grafo G si abarca G (es decir, incluye cada vértice de G ) y es un subgrafo de G (cada arista del árbol pertenece a G ). Un árbol de expansión de un grafo conexo 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

Añadir sólo una arista a un árbol de expansión creará un ciclo; un ciclo de este tipo se llama ciclo fundamental con respecto a ese árbol. Hay un ciclo fundamental distinto para cada arista que no está en el árbol de expansión; por lo tanto, hay una correspondencia uno a uno entre los ciclos fundamentales y las aristas que no están en el árbol de expansión. Para un grafo conectado con V vértices, cualquier árbol de expansión tendrá V  − 1 aristas y, por lo tanto, un grafo de E aristas y uno de sus árboles de expansión tendrán E  −  V  + 1 ciclos fundamentales (el número de aristas restado por el número de aristas incluidas en un árbol de expansión; dando 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]

Conjuntos de corte fundamentales

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

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

Abarcando bosques

Una colección de árboles disjuntos (no conectados) se describe como un bosque . Un bosque de expansión en un grafo 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 sobre teoría de grafos definen un bosque de expansión como un bosque que abarca todos los vértices, lo que significa únicamente que cada vértice del grafo es un vértice del bosque. Un grafo conectado puede tener un bosque de expansión desconectado, como el bosque sin aristas, 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 de expansión como un subgrafo acíclico máximo del grafo dado, o equivalentemente un subgrafo que consiste en un árbol de expansión en cada componente conectado del grafo. ^[10]

Para evitar confusiones entre estas dos definiciones, Gross y Yellen (2005) sugieren el término "bosque de expansión completa" para un bosque de expansió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 cambio llaman a este tipo de bosque un "bosque de expansión máxima" (lo cual es redundante, ya que un bosque máximo necesariamente contiene todos los vértices). ^[11]

Contando árboles de expansión

La fórmula de Cayley cuenta la cantidad de árboles de expansión 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 un invariante bien estudiado .

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 del 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 grafo bipartito completo , entonces . ^[8] ${\displaystyle K_{p,q}}$ ${\displaystyle t(G)=p^{q-1}q^{p-1}}$
• Para el gráfico de hipercubo n -dimensional , ^[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 polinomial como el determinante de una matriz derivada del gráfico, utilizando el teorema de matriz-árbol de Kirchhoff . ^[14]

En concreto, para calcular t ( G ), se construye la matriz laplaciana del grafo, una matriz cuadrada en la que las filas y las 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, al eliminar la fila y la columna de un vértice elegido arbitrariamente, se obtiene una matriz más pequeña cuyo determinante es exactamente  t ( G ).

Deleción-contracción

Si G es un grafo 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 contracción-eliminació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 la arista  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 grafo 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 no se deben eliminar las aristas redundantes, ya que eso daría lugar a un total incorrecto. Por ejemplo, un grafo de enlace que conecta dos vértices por k aristas tiene k árboles de expansión diferentes, cada uno de los cuales consta de una sola de estas aristas.

Polinomio de Tutte

El polinomio de Tutte de un grafo puede definirse como una suma, sobre los árboles de expansión del grafo, 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 grafo desconectado, el número de bosques de expansión máximos. ^[16]

El polinomio de Tutte también puede calcularse utilizando una recurrencia de deleción-contracció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 razón de aproximación garantizada . El punto (1,1), en el que puede evaluarse utilizando el teorema de Kirchhoff, es una de las pocas excepciones. ^[17]

Algoritmos

Construcción

Un árbol de expansión único de un grafo se puede encontrar en tiempo lineal mediante una búsqueda en profundidad o una búsqueda en amplitud . Ambos algoritmos exploran el grafo dado, comenzando desde un vértice arbitrario v , recorriendo los vecinos de los vértices que descubren y añadiendo cada vecino inexplorado a una estructura de datos que se explorará más tarde. 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, excepto el vértice raíz v , al vértice desde el que 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 grafos 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 Trémaux , llamados así por el descubridor del siglo XIX de la búsqueda en profundidad. ^[19]

Los árboles de expansión son importantes en la computación paralela y distribuida, como una forma de mantener las comunicaciones entre un conjunto de procesadores; véase, por ejemplo, el Protocolo de árbol de expansión utilizado por los dispositivos de la capa de enlace OSI o el protocolo Shout para la computación 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 computación. ^[21]

Mejoramiento

En ciertos campos de la teoría de grafos, a menudo resulta útil encontrar un árbol de expansión mínimo de un grafo ponderado . También se han estudiado otros problemas de optimización sobre árboles de expansión, incluidos 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 del camino hamiltoniano ), el árbol de expansión de diámetro mínimo y el árbol de expansión de dilatación mínima. ^{[22] [23]}

También se han estudiado problemas de árboles de expansión óptimos para conjuntos finitos de puntos en un espacio geométrico como el plano euclidiano . Para una entrada de este tipo, 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 manera que en un grafo, utilizando la distancia euclidiana entre pares de puntos como el 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 grafo en un grafo completo con pesos de aristas euclidianos. Sin embargo, no es necesario construir este grafo 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 grafo planar 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 denomina árbol de expansión uniforme . El algoritmo de Wilson se puede utilizar para generar árboles de expansión uniformes en tiempo polinomial mediante un proceso de realizar un recorrido aleatorio en 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 una cantidad exponencial de árboles de expansión, no es posible enumerarlos todos en tiempo polinomial . Sin embargo, se conocen algoritmos para enumerar todos los árboles de expansión en tiempo polinomial por árbol. ^[26]

En grafos infinitos

Todo grafo conexo finito tiene un árbol de expansión. Sin embargo, para grafos conexos infinitos, 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 grafos finitos, un árbol es un grafo conexo sin ciclos finitos, y un árbol de expansión puede definirse 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 grafo 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 en los árboles del grafo, este elemento máximo debe ser un árbol de expansión. Por lo tanto, si se supone el lema de Zorn, todo grafo infinito conexo tiene un árbol de expansión. ^[27]

En la otra dirección, dada una familia de conjuntos , es posible construir un grafo infinito tal que cada árbol de expansión del grafo corresponda a una función de elección de la familia de conjuntos. Por lo tanto, si cada grafo infinito conexo 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 grado de salida 1. Esta definición solo se satisface cuando las "ramas" de T apuntan hacia v .

Véase 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 arborescencias, se puede agregar el adjetivo "que abarca" para indicar que el gráfico, cuando se considera como un bosque/ramificación, consta de un solo árbol/arborescencia que incluye todos los nodos del gráfico.
2. Graham, RL; Hell, Pavol (1985). "Sobre la historia del problema del árbol de expansión mínimo" (PDF) .
3. Borg, Anita. "Folklore del diseño de protocolos de red". YouTube . Microsoft Research . 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, Sr.  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 de matroides, Oxford Graduate Texts in Mathematics , vol. 3, Oxford University Press, pág. 141, ISBN 978-0-19-920250-8.
8. Hartsfield, Nora; Ringel, Gerhard (2003), Perlas en la teoría de grafos: una introducción completa , Courier Dover Publications, 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 computación combinatoria y geométrica, Cambridge University Press, pág. 260, ISBN 978-0-521-56329-1.
11. Gross, Jonathan L.; Yellen, Jay (2005), Teoría de grafos y sus aplicaciones (2.ª ed.), CRC Press, pág. 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, Martin ; 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 hipercubos", Computers & Mathematics with Applications , 15 (4): 277–289, doi :10.1016/0898-1221(88)90213-1, hdl : 2027.42/27522 , MR  0949280.
14. Kocay, William; Kreher, Donald L. (2004), "5.8 El teorema del árbol de matrices", Gráficos, algoritmos y optimización, Matemática discreta 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, LA ; 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.; Vertigan, 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 Ciencias de la Computación, Springer, pág. 19, ISBN 978-0-387-97687-7.
19. de Fraysseix, Hubert; Rosenstiehl, Pierre (1982), "Una caracterización de la planaridad mediante búsqueda en profundidad", Graph theory (Cambridge, 1981) , Ann. Discrete Math., vol. 13, Ámsterdam: Holanda Septentrional, págs. 75-80, MR  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; Humblet, PA; 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 de 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 rápido y paralelo 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), "Spanning trees and spanners" (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), "Generar árboles de expansión aleatorios más rápidamente que el tiempo de cobertura", Actas del vigésimo octavo simposio anual de la ACM sobre la teoría de la computación (STOC 1996) , págs. 296-303, doi :10.1145/237814.237880, MR  1427525.
25. McDiarmid, Colin; Johnson, Theodore; Stone, Harold S. (1997), "Sobre cómo encontrar un árbol de expansión mínimo en una red con pesos aleatorios" (PDF) , Random Structures & Algorithms , 10 (1–2): 187–204, doi :10.1002/(SICI)1098-2418(199701/03)10:1/2<187::AID-RSA10>3.3.CO;2-Y, MR  1611522.
26. Gabow, Harold N. ; Myers, Eugene W. (1978), "Encontrar todos los árboles de expansión de grafos dirigidos y no dirigidos", SIAM Journal on Computing , 7 (3): 280–287, doi :10.1137/0207024, MR  0495152
27. Serre, Jean-Pierre (2003), Árboles , Springer Monographs in Mathematics, Springer, pág. 23.
28. Soukup, Lajos (2008), "Combinatoria infinita: de lo finito a lo infinito", Horizons of combinatorics , Bolyai Soc. Math. 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 Sandpile y árboles de expansión de grafos de líneas dirigidas". Journal of Combinatorial Theory, Serie A . 118 (2): 350–364. arXiv : 0906.2809 . doi : 10.1016/j.jcta.2010.04.001 . ISSN  0097-3165.