Árbol (teoría de grafos)

En teoría de grafos , un árbol es un grafo no dirigido en el que dos vértices cualesquiera están conectados por exactamente un camino , o equivalentemente un grafo no dirigido acíclico conexo . ^[1] Un bosque es un grafo no dirigido en el que dos vértices cualesquiera están conectados por como máximo un camino, o equivalentemente un grafo no dirigido acíclico, o equivalentemente una unión disjunta de árboles. ^[2]

Un árbol dirigido, ^[3] árbol orientado, ^[4]^[5] poliárbol , ^[6] o red conexa simple ^[7] es un grafo acíclico dirigido (DAG) cuyo grafo no dirigido subyacente es un árbol. Un polibosque (o bosque dirigido o bosque orientado) es un grafo acíclico dirigido cuyo grafo no dirigido subyacente es un bosque.

Los distintos tipos de estructuras de datos a los que se hace referencia como árboles en informática tienen grafos subyacentes que son árboles en teoría de grafos, aunque dichas estructuras de datos son generalmente árboles con raíz. Un árbol con raíz puede ser dirigido, llamado árbol con raíz dirigido, ^[8]^[9] ya sea haciendo que todos sus bordes apunten lejos de la raíz, en cuyo caso se llama arborescencia [ ^3]^[10] o árbol externo ^[11]^[12] —o haciendo que todos sus bordes apunten hacia la raíz, en cuyo caso se llama antiarborescencia ^[13] o árbol interno. ^[11]^[14] Un árbol con raíz en sí mismo ha sido definido por algunos autores como un grafo dirigido. ^[15]^[16]^[17] Un bosque con raíz es una unión disjunta de árboles con raíz. Un bosque enraizado puede ser dirigido, llamado bosque enraizado dirigido, ya sea haciendo que todos sus bordes apunten lejos de la raíz en cada árbol enraizado, en cuyo caso se llama ramificado o bosque externo, o haciendo que todos sus bordes apunten hacia la raíz en cada árbol enraizado, en cuyo caso se llama antiramificado o bosque interno.

El término árbol fue acuñado en 1857 por el matemático británico Arthur Cayley . ^[18]

Definiciones

Árbol

Un árbol es un gráfico no dirigido $G$ que satisface cualquiera de las siguientes condiciones equivalentes:

$G$ está conectado y es acíclico (no contiene ciclos).
$G$ es acíclico y se forma un ciclo simple si se agrega cualquier arista a $G.$
$G$ está conectado, pero se desconectaría si se eliminara cualquier borde de $G.$
$G$ está conexo y el grafo completo $K 3$ no es menor de $G$ .
Dos vértices cualesquiera en $G$ pueden estar conectados por un camino simple y único .

Si $G$ tiene un número finito de vértices, digamos $n$ de ellos, entonces las afirmaciones anteriores también son equivalentes a cualquiera de las siguientes condiciones:

$G$ está conectado y tiene $n - 1$ aristas.
$G$ es conexo y cada subgrafo de $G$ incluye al menos un vértice con cero o una arista incidente. (Es decir, $G$ es conexo y 1-degenerado ).
$G$ no tiene ciclos simples y tiene $n - 1$ aristas.

Como en otras partes de la teoría de grafos, el grafo de orden cero (grafo sin vértices) no suele considerarse un árbol: si bien está vacuamente conectado como grafo (cualquier par de vértices puede estar conectado por un camino), no está conectado en cero (ni siquiera conectado en (−1)) en topología algebraica, a diferencia de los árboles no vacíos, y viola la relación de "un vértice más que aristas". Sin embargo, puede considerarse como un bosque que consta de cero árboles.

Un vértice interno (o vértice interior) es un vértice de grado al menos 2. De manera similar, un vértice externo (o vértice exterior, vértice terminal u hoja) es un vértice de grado 1. Un vértice de rama en un árbol es un vértice de grado al menos 3. ^[19]

Un árbol irreducible (o árbol reducido en serie) es un árbol en el que no hay ningún vértice de grado 2 (enumerado en la secuencia A000014 en la OEIS ). ^[20]

Bosque

Un bosque es un grafo acíclico no dirigido o, equivalentemente, una unión disjunta de árboles. De manera trivial, cada componente conectado de un bosque es un árbol. Como casos especiales, el grafo de orden cero (un bosque que consta de cero árboles), un árbol único y un grafo sin aristas son ejemplos de bosques. Dado que para cada árbol $V - E = 1$ , podemos contar fácilmente la cantidad de árboles que hay dentro de un bosque restando la diferencia entre el total de vértices y el total de aristas. $V - E =$ cantidad de árboles en un bosque.

Poliárbol

Un poliárbol ^[6] (o árbol dirigido ^[3] o árbol orientado ^[4]^[5] o red conexa simple ^[7] ) es un grafo acíclico dirigido (DAG) cuyo grafo no dirigido subyacente es un árbol. En otras palabras, si reemplazamos sus aristas dirigidas por aristas no dirigidas, obtenemos un grafo no dirigido que es a la vez conexo y acíclico.

Algunos autores restringen la frase "árbol dirigido" al caso en el que todas las aristas están dirigidas hacia un vértice particular, o todas dirigidas lejos de un vértice particular (ver arborescencia ). ^[21]^[22]^[23]

Polibosque

Un polibosque (o bosque dirigido o bosque orientado) es un grafo acíclico dirigido cuyo grafo no dirigido subyacente es un bosque. En otras palabras, si reemplazamos sus aristas dirigidas por aristas no dirigidas, obtenemos un grafo no dirigido que es acíclico.

Al igual que con los árboles dirigidos, algunos autores restringen la frase "bosque dirigido" al caso en el que los bordes de cada componente conectado están todos dirigidos hacia un vértice particular, o todos dirigidos lejos de un vértice particular (ver ramificación ). ^[22]

Árbol enraizado

Un árbol enraizado es un árbol en el que un vértice ha sido designado como raíz. ^[24] A los bordes de un árbol enraizado se les puede asignar una orientación natural, ya sea lejos o hacia la raíz, en cuyo caso la estructura se convierte en un árbol enraizado dirigido. Cuando un árbol enraizado dirigido tiene una orientación lejos de la raíz, se denomina arborescencia ^[3] o árbol externo ; ^[11] cuando tiene una orientación hacia la raíz, se denomina antiarborescencia o árbol interno . ^[11] El orden del árbol es el ordenamiento parcial de los vértices de un árbol con $u < v$ si y solo si el camino único desde la raíz hasta $v$ pasa por $u$ . Un árbol enraizado $T$ que es un subgrafo de algún grafo $G$ es un árbol normal si los extremos de cada camino $T$ en $G$ son comparables en este orden del árbol (Diestel 2005, p. 15). Los árboles enraizados, a menudo con una estructura adicional como un ordenamiento de los vecinos en cada vértice, son una estructura de datos clave en la ciencia informática; ver estructura de datos de árbol .

En un contexto donde los árboles normalmente tienen una raíz, un árbol sin ninguna raíz designada se denomina árbol libre .

Un árbol etiquetado es un árbol en el que cada vértice tiene una etiqueta única. Los vértices de un árbol etiquetado en $n$ vértices (para números enteros no negativos $n$ ) normalmente tienen las etiquetas $1, 2, \dots, n$ . Un árbol recursivo es un árbol raíz etiquetado donde las etiquetas de los vértices respetan el orden del árbol (es decir, si $u < v$ para dos vértices $u$ y $v$ , entonces la etiqueta de $u$ es más pequeña que la etiqueta de $v$ ).

En un árbol con raíz, el padre de un vértice $v$ es el vértice conectado a $v$ en el camino a la raíz; cada vértice tiene un padre único, excepto la raíz que no tiene padre. ^[24] Un hijo de un vértice $v$ es un vértice del cual $v$ es el padre. ^[24] Un ascendente de un vértice $v$ es cualquier vértice que sea el padre de $v$ o sea (recursivamente) un ascendente de un padre de $v$ . Un descendiente de un vértice $v$ es cualquier vértice que sea un hijo de $v$ o sea (recursivamente) un descendiente de un hijo de $v$ . Un hermano de un vértice $v$ es cualquier otro vértice en el árbol que comparte un padre con $v$ . ^[24] Una hoja es un vértice sin hijos. ^[24] Un vértice interno es un vértice que no es una hoja. ^[24]

La altura de un vértice en un árbol enraizado es la longitud del camino descendente más largo hacia una hoja desde ese vértice. La altura del árbol es la altura de la raíz. La profundidad de un vértice es la longitud del camino hacia su raíz ( ruta raíz ). La profundidad de un árbol es la profundidad máxima de cualquier vértice. La profundidad es comúnmente necesaria en la manipulación de los diversos árboles autoequilibrados, en particular los árboles AVL . La raíz tiene profundidad cero, las hojas tienen altura cero y un árbol con un solo vértice (por lo tanto, tanto una raíz como una hoja) tiene profundidad y altura cero. Convencionalmente, un árbol vacío (un árbol sin vértices, si se permiten) tiene profundidad y altura −1.

Un árbol k -ario (para números enteros no negativos $k$ ) es un árbol con raíz en el que cada vértice tiene como máximo $k$ hijos. ^[25] Los árboles 2-arios a menudo se denominan árboles binarios , mientras que los árboles 3-arios a veces se denominan árboles ternarios .

Árbol ordenado

Un árbol ordenado (alternativamente, árbol plano o árbol posicional ^[26] ) es un árbol con raíz en el que se especifica un ordenamiento para los hijos de cada vértice. ^[24]^[27] Esto se llama un "árbol plano" porque un ordenamiento de los hijos es equivalente a una incrustación del árbol en el plano, con la raíz en la parte superior y los hijos de cada vértice más abajo que ese vértice. Dada una incrustación de un árbol con raíz en el plano, si uno fija una dirección de los hijos, digamos de izquierda a derecha, entonces una incrustación da un ordenamiento de los hijos. Por el contrario, dado un árbol ordenado, y dibujando convencionalmente la raíz en la parte superior, entonces los vértices hijos en un árbol ordenado se pueden dibujar de izquierda a derecha, produciendo una incrustación plana esencialmente única.

Propiedades

Todo árbol es un grafo bipartito . Un grafo es bipartito si y solo si no contiene ciclos de longitud impar. Como un árbol no contiene ciclos en absoluto, es bipartito.
Todo árbol con un número contable de vértices es un gráfico plano .
Todo grafo conexo G admite un árbol de expansión , que es un árbol que contiene cada vértice de G y cuyas aristas son aristas de G. Tipos más específicos de árboles de expansión, existentes en todo grafo finito conexo, incluyen árboles de búsqueda en profundidad y árboles de búsqueda en amplitud . Generalizando la existencia de árboles de búsqueda en profundidad, todo grafo conexo con solo un número contable de vértices tiene un árbol de Trémaux . ^[28] Sin embargo, algunos grafos de orden incontable no tienen dicho árbol. ^[29]
Todo árbol finito con n vértices, con n > 1 , tiene al menos dos vértices terminales (hojas). Este número mínimo de hojas es característico de los grafos de trayectoria ; el número máximo, n − 1 , se alcanza solo en los grafos de estrella . El número de hojas es al menos el grado máximo del vértice.
Para tres vértices cualesquiera en un árbol, los tres caminos entre ellos tienen exactamente un vértice en común. En términos más generales, un vértice en un grafo que pertenece a tres caminos más cortos entre tres vértices se denomina mediana de estos vértices. Debido a que cada tres vértices en un árbol tienen una mediana única, cada árbol es un grafo de mediana .
Cada árbol tiene un centro que consiste en un vértice o dos vértices adyacentes. El centro es el vértice medio o los dos vértices medios en cada camino más largo. De manera similar, cada árbol de n vértices tiene un centroide que consiste en un vértice o dos vértices adyacentes. En el primer caso, la eliminación del vértice divide el árbol en subárboles de menos de n /2 vértices. En el segundo caso, la eliminación de la arista entre los dos vértices centroidales divide el árbol en dos subárboles de exactamente n /2 vértices.
Las camarillas máximas de un árbol son precisamente sus bordes, lo que implica que la clase de árboles tiene pocas camarillas .

Enumeración

Árboles etiquetados

La fórmula de Cayley establece que hay $n n -2$ árboles en $n$ vértices etiquetados. Una demostración clásica utiliza sucesiones de Prüfer , que naturalmente muestran un resultado más sólido: el número de árboles con vértices $1, 2, \dots, n$ de grados $d 1, d 2, \dots, d n$ respectivamente, es el coeficiente multinomial

{n-2 \choose d_{1}-1,d_{2}-1,\ldots ,d_{n}-1}.

Un problema más general es contar árboles de expansión en un gráfico no dirigido , que se aborda mediante el teorema del árbol matricial . (La fórmula de Cayley es el caso especial de árboles de expansión en un gráfico completo ). El problema similar de contar todos los subárboles independientemente del tamaño es #P-completo en el caso general (Jerrum (1994)).

Árboles sin etiquetar

Contar el número de árboles libres sin etiquetar es un problema más difícil. No se conoce ninguna fórmula cerrada para el número $t (n)$ de árboles con $n$ vértices hasta el isomorfismo del grafo . Los primeros valores de $t (n)$ son

1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, … (secuencia A000055 en la OEIS ).

Otter (1948) demostró la estimación asintótica

t(n)\sim C\alpha ^{n}n^{-5/2}\quad {\text{como }}n\to \infty ,

con $C \approx 0,534949606...$ y $α \approx 2,95576528565...$ (secuencia A051491 en la OEIS ). Aquí, el símbolo $~ significa que$

\lim _{n\to \infty }{\frac {t(n)}{C\alpha ^{n}n^{-5/2}}}=1.

Esto es una consecuencia de su estimación asintótica del número $r (n)$ de árboles enraizados no etiquetados con $n$ vértices:

r(n)\sim D\alpha ^{n}n^{-3/2}\quad {\text{como }}n\to \infty ,

con $D \approx 0,43992401257...$ y el mismo $α$ que arriba (cf. Knuth (1997), cap. 2.3.4.4 y Flajolet & Sedgewick (2009), cap. VII.5, p. 475).

Los primeros valores de $r (n)$ son ^[30]

1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, 32973, … (secuencia A000081 en la OEIS ).

Tipos de arboles

Un gráfico de trayectoria (o gráfico lineal ) consta de $n$ vértices dispuestos en una línea, de modo que los vértices $i$ e $i + 1$ están conectados por una arista para $i = 1, \dots, n - 1$ .
Un árbol en forma de estrella consta de un vértice central llamado raíz y varios grafos de trayectorias unidos a él. Más formalmente, un árbol es en forma de estrella si tiene exactamente un vértice de grado mayor que 2.
Un árbol estrella es un árbol que consta de un único vértice interno (y $n - 1$ hojas). En otras palabras, un árbol estrella de orden $n$ es un árbol de orden $n$ con tantas hojas como sea posible.
Un árbol oruga es un árbol en el que todos los vértices están dentro de la distancia 1 de un subgrafo de ruta central.
Un árbol de langosta es un árbol en el que todos los vértices están dentro de la distancia 2 de un subgrafo de ruta central.
Un árbol regular de grado $d$ es el árbol infinito con $d$ aristas en cada vértice. Estos surgen como los grafos de Cayley de grupos libres y en la teoría de los edificios de Tit . En mecánica estadística se conocen como redes de Bethe .

Véase también

Notas

^ Bender y Williamson 2010, pág. 171.
^ Bender y Williamson 2010, pág. 172.
^ abcd Deo 1974, pág. 206.
^ ab Véase Harary y Sumner (1980).
^ ab Véase Simion (1991).
^ ab Véase Dasgupta (1999).
^ ab Véase Kim y Pearl (1983).
^ Stanley Gill Williamson (1985). Combinatoria para la informática . Courier Dover Publications. pág. 288. ISBN. 978-0-486-42076-9.
^ Mehran Mesbahi; Magnus Egerstedt (2010). Métodos de teoría de grafos en redes multiagente . Princeton University Press. pág. 38. ISBN 978-1-4008-3535-5.
^ Ding-Zhu Du; Ker-I Ko; Xiaodong Hu (2011). Diseño y análisis de algoritmos de aproximación . Springer Science & Business Media. pág. 108. ISBN 978-1-4614-1701-9.
^ abcd Deo 1974, pág. 207.
^ Jonathan L. Gross; Jay Yellen; Ping Zhang (2013). Manual de teoría de grafos, segunda edición . CRC Press. pág. 116. ISBN 978-1-4398-8018-0.
^ Bernhard Korte ; Jens Vygen (2012). Optimización combinatoria: teoría y algoritmos (5.ª ed.). Springer Science & Business Media. pág. 28. ISBN 978-3-642-24488-9.
^ Kurt Mehlhorn ; Peter Sanders (2008). Algoritmos y estructuras de datos: la caja de herramientas básica (PDF) . Springer Science & Business Media. pág. 52. ISBN 978-3-540-77978-0. Archivado (PDF) del original el 8 de septiembre de 2015.
^ David Makinson (2012). Conjuntos, lógica y matemáticas para la informática . Springer Science & Business Media. págs. 167-168. ISBN 978-1-4471-2499-3.
^ Kenneth Rosen (2011). Matemática discreta y sus aplicaciones, 7.ª edición . McGraw-Hill Science. pág. 747. ISBN 978-0-07-338309-5.
^ Alexander Schrijver (2003). Optimización combinatoria: poliedros y eficiencia . Springer. pág. 34. ISBN. 3-540-44389-4.
↑ Cayley (1857) "Sobre la teoría de las formas analíticas llamadas árboles", Philosophical Magazine , 4.ª serie, 13 : 172-176.
Sin embargo, cabe mencionar que en 1847, KGC von Staudt , en su libro Geometrie der Lage (Nürnberg, (Alemania): Bauer und Raspe, 1847), presentó una prueba del teorema del poliedro de Euler que se basa en árboles en las páginas 20-21. También en 1847, el físico alemán Gustav Kirchhoff investigó circuitos eléctricos y encontró una relación entre el número (n) de cables/resistencias (ramas), el número (m) de uniones (vértices) y el número (μ) de bucles (caras) en el circuito. Demostró la relación mediante un argumento que se basaba en árboles. Ver: Kirchhoff, GR (1847) "Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird" Archivado el 20 de julio de 2023 en Wayback Machine (Sobre la solución de ecuaciones a las que nos lleva la investigación de la distribución lineal de las corrientes galvánicas), Annalen der Physik un d Chemie , 72 (12): 497–508.
^ DeBiasio, Louis; Lo, Allan (9 de octubre de 2019). "Árboles de expansión con pocos vértices de rama". arXiv : 1709.04937 [math.CO].
^ Harary y Prins 1959, pág. 150.
^ Chen, Wai-kai (1966). "Sobre árboles dirigidos y árboles $k$ dirigidos de un dígrafo y su generación". Revista SIAM de Matemáticas Aplicadas . 14 : 550–560. doi :10.1137/0114048. MR 0209064.
^ ab Kozlov, Dmitry N. (1999). "Complejos de árboles dirigidos". Journal of Combinatorial Theory . Serie A. 88 (1): 112–122. doi :10.1006/jcta.1999.2984. MR 1713484.
^ Tran, Ngoc Mai; Buck, Johannes; Klüppelberg, Claudia (febrero de 2024), "Estimación de un árbol dirigido para extremos", Journal of the Royal Statistical Society Series B: Statistical Methodology , arXiv : 2102.06197 , doi :10.1093/jrsssb/qkad165
^ abcdefg Bender y Williamson 2010, pág. 173.
^ Véase Black, Paul E. (4 de mayo de 2007). «árbol k-ario». Instituto Nacional de Normas y Tecnología de Estados Unidos. Archivado desde el original el 8 de febrero de 2015. Consultado el 8 de febrero de 2015 .
^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2022). Introducción a los algoritmos (4.ª ed.). Sección B.5.3, Árboles binarios y posicionales : MIT Press. p. 1174. ISBN 9780262046305Archivado desde el original el 16 de julio de 2023 . Consultado el 20 de julio de 2023 .{{cite book}}: Mantenimiento de CS1: ubicación ( enlace )
^ Stanley, Richard P. (2012), Combinatoria enumerativa, vol. I, Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, pág. 573, ISBN 9781107015425
^ Diestel (2005), Prop. 8.2.4.
^ Diestel (2005), Prop. 8.5.2.
^ Véase Li (1996).

Referencias

Bender, Edward A.; Williamson, S. Gill (2010), Listas, decisiones y gráficos. Con una introducción a la probabilidad
Dasgupta, Sanjoy (1999), "Aprendizaje de polytrees", en Proc. 15th Conference on Uncertainty in Artificial Intelligence (UAI 1999), Estocolmo, Suecia, julio-agosto de 1999 (PDF) , págs. 134-141.
Deo, Narsingh (1974), Teoría de grafos con aplicaciones a la ingeniería y la informática (PDF) , Englewood, Nueva Jersey: Prentice-Hall, ISBN 0-13-363473-6, archivado (PDF) del original el 17 de mayo de 2019
Harary, Frank ; Prins, Geert (1959), "El número de árboles homeomórficamente irreducibles y otras especies", Acta Mathematica , 101 (1–2): 141–162, doi : 10.1007/BF02559543 , ISSN 0001-5962
Harary, Frank ; Sumner, David (1980), "El número dicromático de un árbol orientado", Journal of Combinatorics, Information & System Sciences , 5 (3): 184–187, MR 0603363.
Kim, Jin H.; Pearl, Judea (1983), "Un modelo computacional para el razonamiento causal y diagnóstico en motores de inferencia", en Proc. 8th International Joint Conference on Artificial Intelligence (IJCAI 1983), Karlsruhe, Alemania, agosto de 1983 (PDF) , págs. 190–193.
Li, Gang (1996), "Generación de árboles enraizados y árboles libres", Tesis de maestría, Departamento de Ciencias de la Computación, Universidad de Victoria, BC, Canadá (PDF) , pág. 9.
Simion, Rodica (1991), "Árboles con 1-factores y árboles orientados", Discrete Mathematics , 88 (1): 93–104, doi : 10.1016/0012-365X(91)90061-6 , MR 1099270.

Lectura adicional

Wikimedia Commons alberga una categoría multimedia sobre Árbol (teoría de grafos) .

Diestel, Reinhard (2005), Graph Theory (3.ª ed.), Berlín, Nueva York: Springer-Verlag, ISBN 978-3-540-26183-4.
Flajolet, Philippe; Sedgewick, Robert (2009), Combinatoria analítica , Cambridge University Press, ISBN 978-0-521-89806-5
"Árbol", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
Knuth, Donald E. (14 de noviembre de 1997), El arte de la programación informática, volumen 1: algoritmos fundamentales (3.ª ed.), Addison-Wesley Professional
Jerrum, Mark (1994), "Contar árboles en un gráfico es #P-completo", Information Processing Letters , 51 (3): 111–116, doi :10.1016/0020-0190(94)00085-9, ISSN 0020-0190.
Otter, Richard (1948), "El número de árboles", Anales de Matemáticas , Segunda serie, 49 (3): 583–599, doi :10.2307/1969046, JSTOR 1969046.