Árbol (teoría de grafos)

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

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

Los diversos tipos de estructuras de datos denominadas árboles en informática tienen gráficos subyacentes que son árboles en la teoría de grafos, aunque dichas estructuras de datos generalmente son árboles con raíces. Un árbol enraizado puede ser dirigido, llamado árbol enraizado dirigido, ^[8]^[9] haciendo que todos sus bordes apunten en dirección opuesta a la raíz, en cuyo caso se llama arborescencia [ ^3]^[10] o árbol externo ^{[11]. ]}^[12] —o hacer que todos sus bordes apunten hacia la raíz—en cuyo caso se denomina antiarborescencia ^[13] o in-tree. ^[11]^[14] Algunos autores han definido un árbol enraizado como un gráfico dirigido. ^[15]^[16]^[17] Un bosque enraizado es una unión desunida de árboles enraizados. Un bosque enraizado puede ser dirigido, llamado bosque enraizado dirigido, ya sea haciendo que todos sus bordes apunten en dirección opuesta a la raíz en cada árbol enraizado (en cuyo caso se llama bosque ramificado o exterior) o haciendo que todos sus bordes apunten hacia la raíz. en cada árbol enraizado, en cuyo caso se llama anti-ramificación o en el bosque.

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$ es conexo y 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$ es conexo y la gráfica completa $K 3$ no es menor de $G$ .
Dos vértices cualesquiera en $G$ pueden conectarse mediante un camino simple ú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$ es conexo y tiene $n - 1$ aristas.
$G$ es conexo y cada subgrafo de $G$ incluye al menos un vértice con cero o un borde 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 gráfico de orden cero (gráfico sin vértices) generalmente no se considera un árbol: si bien está conectado de manera vacía como un gráfico (dos vértices cualesquiera pueden estar conectados por una ruta), no es 0 -conectado (o incluso (−1)-conectado) en topología algebraica, a diferencia de los árboles no vacíos, y viola la relación "un vértice más que aristas". Sin embargo, puede considerarse como un bosque formado por cero árboles.

Un vértice interno (o vértice interno) es un vértice de grado al menos 2. De manera similar, un vértice externo (o vértice externo, 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 de serie reducida) 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 gráfico no dirigido en el que dos vértices cualesquiera están conectados por como máximo un camino. De manera equivalente, un bosque es un gráfico acíclico no dirigido, todos cuyos componentes conectados son árboles; en otras palabras, el grafo consta de una unión disjunta de árboles. Como casos especiales, el gráfico de orden cero (un bosque que consta de cero árboles), un solo árbol y un gráfico sin aristas son ejemplos de bosques. Dado que para cada árbol $V - E = 1$ , podemos contar fácilmente el número de árboles que hay dentro de un bosque restando la diferencia entre el total de vértices y los bordes totales. $V - E =$ número de árboles en un bosque.

Poliárbol

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

Algunos autores ^{[ ¿quién? ]} restringe la frase "árbol dirigido" al caso en el que todos los bordes están dirigidos hacia un vértice particular, o todos se alejan de un vértice particular (ver arborescencia ).

Poliforestal

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

Algunos autores ^{[ ¿quién? ]} restringe 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 ).

árbol enraizado

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

En un contexto donde los árboles suelen tener una raíz, un árbol sin una raíz designada se denomina árbol libre .

Un árbol etiquetado es un árbol en el que cada vértice recibe una etiqueta única. Los vértices de un árbol etiquetado en $n$ vértices (para números enteros no negativos $n$ ) generalmente reciben las etiquetas $1, 2,\dots, n$ . Un árbol recursivo es un árbol enraizado 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 enraizado, el padre de un vértice $v$ es el vértice conectado a $v$ en el camino hacia la raíz; Cada vértice tiene un padre único, excepto que la raíz no tiene padre. ^[21] Un hijo de un vértice $v$ es un vértice del cual $v$ es el padre. ^[21] 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 hijo de $v$ o sea (recursivamente) descendiente de un hijo de $v$ . Un hermano de un vértice $v$ es cualquier otro vértice del árbol que comparte un padre con $v$ . ^[21] Una hoja es un vértice sin hijos. ^[21] Un vértice interno es un vértice que no es una hoja. ^[21]

La altura de un vértice en un árbol enraizado es la longitud del camino descendente más largo hasta 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 hasta su raíz ( camino raíz ). Esta ^{[ aclaración necesaria (¿Esta ___?) ]} es comúnmente necesaria en la manipulación de varios á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, raíz y hoja) tiene profundidad ^{[ aclaración necesaria (solo hemos definido la profundidad de un vértice, no también la profundidad del árbol). ) ]} y altura cero. Convencionalmente, un árbol vacío (un árbol sin vértices, si están permitidos) tiene profundidad y altura −1.

Un árbol k -ario (para enteros no negativos $k$ ) es un árbol enraizado en el que cada vértice tiene como máximo $k$ hijos. ^[22] Los árboles biarios a menudo se denominan árboles binarios , mientras que los árboles triarios a veces se denominan árboles ternarios .

árbol ordenado

Un árbol ordenado (alternativamente, árbol plano o árbol posicional ^[23] ) es un árbol enraizado en el que se especifica un orden para los hijos de cada vértice. ^[21]^[24] Esto se llama "á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 bajos que ese vértice. Dada la incrustación de un árbol enraizado en el plano, si uno fija una dirección de los niños, digamos de izquierda a derecha, entonces una incrustación da un orden de los niños. Por el contrario, dado un árbol ordenado, y convencionalmente dibujando la raíz en la parte superior, los vértices secundarios en un árbol ordenado se pueden dibujar de izquierda a derecha, produciendo una incrustación plana esencialmente única.

Propiedades

Cada árbol es un gráfico bipartito . Un gráfico es bipartito si y sólo si no contiene ciclos de longitud impar. Como un árbol no contiene ningún ciclo, es bipartito.
Cada árbol con sólo 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 todos los vértices de G y cuyas aristas son aristas de G. Los tipos más específicos de árboles que abarcan, existentes en cada gráfico finito conectado, incluyen árboles de búsqueda en profundidad y árboles de búsqueda en amplitud . Generalizando la existencia de árboles de búsqueda en profundidad, cada gráfico conectado con solo un número contable de vértices tiene un árbol de Trémaux . ^[25] Sin embargo, algunos gráficos de orden incontable no tienen dicho árbol. ^[26]
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 gráficos de trayectorias ; el número máximo, n − 1 , se alcanza sólo mediante gráficos estelares . El número de hojas es al menos el grado máximo del vértice.
Para tres vértices cualesquiera de un árbol, los tres caminos entre ellos tienen exactamente un vértice en común. De manera más general, un vértice en un gráfico que pertenece a tres caminos más cortos entre tres vértices se llama mediana de estos vértices. Debido a que cada tres vértices de un árbol tiene una mediana única, cada árbol es un gráfico de mediana .
Todo árbol tiene un centro que consta de uno 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 consta de 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 del borde entre los dos vértices centroidales divide el árbol en dos subárboles de exactamente n /2 vértices.
Los grupos máximos de un árbol son precisamente sus bordes, lo que implica que la clase de árboles tiene pocos grupos .

Enumeración

Árboles etiquetados

La fórmula de Cayley establece que hay $n n -2$ árboles en $n$ vértices etiquetados. Una prueba clásica utiliza secuencias de Prüfer , que naturalmente muestran un resultado más fuerte: 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 \elige 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 , lo cual 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 complicado. No se conoce ninguna fórmula cerrada para el número $t (n)$ de árboles con $n$ vértices hasta el isomorfismo del gráfico . 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 el OEIS ).

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

t(n)\sim C\alpha ^{n}n^{-5/2}\quad {\text{as }}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 para el número $r (n)$ de árboles enraizados sin etiquetar con $n$ vértices:

r(n)\sim D\alpha ^{n}n^{-3/2}\quad {\text{as }}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 ^[27]

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 ruta (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 gráficos de ruta adjuntos. Más formalmente, un árbol tiene 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 de oruga es un árbol en el que todos los vértices están a una distancia 1 de un subgrafo de ruta central.
Un árbol de langosta es un árbol en el que todos los vértices están a una distancia de 2 de un subgrafo de ruta central.
Un árbol regular de grado $d$ es el árbol infinito con $d$ aristas en cada vértice. Éstos surgen como los gráficos de Cayley de grupos libres y en la teoría de los edificios de Tit .

Ver también

Notas

^ Bender y Williamson 2010, pág. 171.
^ Bender y Williamson 2010, pág. 172.
^ abcd Deo 1974, pag. 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 . Publicaciones de Courier Dover. pag. 288.ISBN _ 978-0-486-42076-9.
^ Mehran Mesbahi; Magnus Egerstedt (2010). Métodos de teoría de grafos en redes multiagente . Prensa de la Universidad de Princeton. pag. 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 . Medios de ciencia y negocios de Springer. pag. 108.ISBN _ 978-1-4614-1701-9.
^ abcd Deo 1974, pag. 207.
^ Jonathan L. bruto; Jay Yellen; Ping Zhang (2013). Manual de teoría de grafos, segunda edición . Prensa CRC. pag. 116.ISBN _ 978-1-4398-8018-0.
^ Bernhard Korte ; Jens Vygen (2012). Optimización combinatoria: teoría y algoritmos (5ª ed.). Medios de ciencia y negocios de Springer. pag. 28.ISBN _ 978-3-642-24488-9.
^ Kurt Mehlhorn ; Peter Sanders (2008). Algoritmos y estructuras de datos: la caja de herramientas básica (PDF) . Medios de ciencia y negocios de Springer. pag. 52.ISBN _ 978-3-540-77978-0. Archivado (PDF) desde el original el 8 de septiembre de 2015.
^ David Makinson (2012). Conjuntos, Lógica y Matemáticas para la Computación . Medios de ciencia y negocios de Springer. págs. 167-168. ISBN 978-1-4471-2499-3.
^ Kenneth Rosen (2011). Matemática discreta y sus aplicaciones, 7ª edición . Ciencia de McGraw-Hill. pag. 747.ISBN _ 978-0-07-338309-5.
^ Alejandro Schrijver (2003). Optimización combinatoria: poliedros y eficiencia . Saltador. pag. 34.ISBN _ 3-540-44389-4.
^ Cayley (1857) "Sobre la teoría de las formas analíticas llamadas árboles", Philosophical Magazine , cuarta serie, 13 : 172-176.
Sin embargo, cabe mencionar que en 1847, KGC von Staudt , en su libro Geometrie der Lage (Núremberg, (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 basado 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" (Sobre la solución de las ecuaciones a las que nos lleva la investigación de la distribución lineal de las corrientes galvánicas ), Annalen der Physik und Chemie , 72 (12): 497–508.
^ DeBiasio, Luis; Hola, Allan (9 de octubre de 2019). "Árboles extensos con pocos vértices de ramas". arXiv : 1709.04937 [matemáticas.CO].
^ Harary y Prins 1959, pág. 150.
^ abcdefg Bender y Williamson 2010, pág. 173.
^ Véase Black, Paul E. (4 de mayo de 2007). "árbol k-ary". Instituto Nacional de Estándares y Tecnología de EE. UU . 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. pag. 1174.ISBN _ 9780262046305. Consultado el 20 de julio de 2023 .{{cite book}}: Mantenimiento CS1: ubicación ( enlace )
^ Stanley, Richard P. (2012), Combinatoria enumerativa, vol. I, Estudios de Cambridge en Matemáticas Avanzadas, vol. 49, Prensa de la Universidad de Cambridge, pág. 573, ISBN 9781107015425
^ Diestel (2005), Proposición 8.2.4.
^ Diestel (2005), Proposición 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), "Aprendiendo poliárboles", en Proc. 15.ª Conferencia sobre la incertidumbre en la inteligencia artificial (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) desde el original el 2019-05-17
Harary, Frank ; Prins, Geert (1959), "El número de árboles y otras especies homeomórficamente irreducibles", 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, SEÑOR 0603363.
Kim, Jin H.; Pearl, Judea (1983), "Un modelo computacional para el razonamiento causal y de diagnóstico en motores de inferencia", en Proc. Octava Conferencia Internacional Conjunta sobre Inteligencia Artificial (IJCAI 1983), Karlsruhe, Alemania, agosto de 1983 (PDF) , págs..
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. 9.
Simion, Rodica (1991), "Árboles con 1 factor y árboles orientados", Matemáticas discretas , 88 (1): 93–104, doi : 10.1016/0012-365X(91)90061-6 , MR 1099270.

Otras lecturas

Wikimedia Commons tiene medios relacionados con el árbol (teoría de grafos) .

Diestel, Reinhard (2005), Teoría de grafos (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", Cartas de procesamiento de información , 51 (3): 111–116, doi :10.1016/0020-0190(94)00085-9, ISSN 0020- 0190.
Otter, Richard (1948), "El número de árboles", Annals of Mathematics , segunda serie, 49 (3): 583–599, doi :10.2307/1969046, JSTOR 1969046.