stringtranslate.com

Á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:

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:

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 VE = 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. VE = 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 subyacente no dirigido 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 de á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 de á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, …, 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

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 secuencias de Prüfer , que naturalmente muestran un resultado más sólido: el número de árboles con vértices 1, 2, …, n de grados d 1 , d 2 , …, d n respectivamente, es el coeficiente multinomial

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

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

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

con D ≈ 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

Véase también

Notas

  1. ^ Bender y Williamson 2010, pág. 171.
  2. ^ Bender y Williamson 2010, pág. 172.
  3. ^ abcd Deo 1974, pág. 206.
  4. ^ ab Véase Harary y Sumner (1980).
  5. ^ ab Véase Simion (1991).
  6. ^ ab Véase Dasgupta (1999).
  7. ^ ab Véase Kim y Pearl (1983).
  8. ^ Stanley Gill Williamson (1985). Combinatoria para la informática . Courier Dover Publications. pág. 288. ISBN. 978-0-486-42076-9.
  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.
  10. ^ 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.
  11. ^ abcd Deo 1974, pág. 207.
  12. ^ 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.
  13. ^ 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.
  14. ^ 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.
  15. ^ 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.
  16. ^ Kenneth Rosen (2011). Matemática discreta y sus aplicaciones, 7.ª edición . McGraw-Hill Science. pág. 747. ISBN 978-0-07-338309-5.
  17. ^ Alejandro Schrijver (2003). Optimización combinatoria: poliedros y eficiencia . Saltador. pag. 34.ISBN 3-540-44389-4.
  18. ^ 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 und Chemie , 72 (12): 497–508.
  19. ^ DeBiasio, Louis; Lo, Allan (9 de octubre de 2019). "Árboles de expansión con pocos vértices de rama". arXiv : 1709.04937 [math.CO].
  20. ^ Harary y Prins 1959, pág. 150.
  21. ^ 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 (3): 550–560. doi :10.1137/0114048. MR  0209064.
  22. ^ 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.
  23. ^ 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 , 86 (3): 771–792, arXiv : 2102.06197 , doi :10.1093/jrsssb/qkad165
  24. ^ abcdefg Bender y Williamson 2010, pág. 173.
  25. ^ 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 .
  26. ^ 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 )
  27. ^ Stanley, Richard P. (2012), Combinatoria enumerativa, vol. I, Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, pág. 573, ISBN 9781107015425
  28. ^ Diestel (2005), Proposición 8.2.4.
  29. ^ Diestel (2005), Proposición 8.5.2.
  30. ^ Véase Li (1996).

Referencias

Lectura adicional