Hispanopedia Wiki
Articulo de referencia

Árbol (teoría de grafos)

1"},"chromatic_index":{"wt":""},"properties":{"wt":""}},"i":0}}]}"> En teoría de grafos , un árbol es un grafo no dirigido en el que cada par de vértices distintos está conectad...

Hispanopedia WikiContenido en espanolLectura gratuita

En teoría de grafos , un árbol es un grafo no dirigido en el que cada par de vértices distintos está conectado por exactamente un camino , o equivalentemente, un grafo no dirigido acíclico conexo . [ 1 ] Un bosque es un grafo no dirigido en el que cualesquiera dos vértices 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 ] un árbol orientado, [ 4 ] [ 5 ] un poliárbol , [ 6 ] o una red conexa simple [ 7 ] es un grafo acíclico dirigido (DAG) cuyo grafo subyacente no dirigido es un árbol. Un polibosque (o bosque dirigido u orientado) es un grafo acíclico dirigido cuyo grafo subyacente no dirigido es un bosque.

Los distintos tipos de estructuras de datos denominadas árboles en informática tienen grafos subyacentes que son árboles en la 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 todas sus aristas apunten lejos de la raíz —en cuyo caso se llama arborescencia [ 3 ] [ 10 ] o out-tree [ 11 ] [ 12 ] — o haciendo que todas sus aristas apunten hacia la raíz —en cuyo caso se llama antiarborescencia [ 13 ] o in-tree. [ 11 ] [ 14 ] Algunos autores han definido un árbol con raíz como un grafo dirigido. [ 15 ] [ 16 ] [ 17 ] Un bosque con raíz es una unión disjunta de árboles con raíz. Un bosque con raíces puede ser dirigido, denominándose bosque con raíces dirigido, ya sea haciendo que todos sus bordes apunten en dirección opuesta a la raíz de cada árbol enraizado (en cuyo caso se denomina bosque ramificado o externo) o haciendo que todos sus bordes apunten hacia la raíz de cada árbol enraizado (en cuyo caso se denomina bosque antiramificado o 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 grafo no dirigido G que satisface cualquiera de las siguientes condiciones equivalentes:

Si G tiene un número finito de vértices, digamos n , 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 una arista incidente. (Es decir, G es conexo y 1-degenerado ).
  • G no tiene ciclos simples y tiene n − 1 aristas.

Como en otros ámbitos de la teoría de grafos, el grafo de orden cero (grafo sin vértices) generalmente no se considera un árbol: si bien es vacuamente conexo como grafo (cualquier par de vértices puede conectarse mediante un camino), no es 0-conexo (ni siquiera (−1)-conexo) en topología algebraica, a diferencia de los árboles no vacíos, e incumple la relación de "un vértice más que aristas". Sin embargo, puede considerarse como un bosque compuesto por 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 el OEIS ). [ 20 ]

Bosque

Un bosque es un grafo acíclico no dirigido o, equivalentemente, una unión disjunta de árboles. Obviamente, cada componente conexa de un bosque es un árbol. Como casos especiales, el grafo de orden cero (un bosque que consta de cero árboles), un solo árbol y un grafo 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 en un bosque restando la diferencia entre el total de vértices y el total de aristas. V − E = número de árboles en un bosque.

Polytree

Un poliárbol [ 6 ] (o árbol dirigido [ 3 ] , á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 conexo y acíclico.

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

Polibosque

Un polibosque (o bosque dirigido u orientado) es un grafo dirigido acíclico 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 que las aristas de cada componente conexa están todas dirigidas hacia un vértice particular, o todas dirigidas en dirección opuesta a un vértice particular (véase 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 las aristas de un árbol enraizado se les puede asignar una orientación natural, ya sea alejándose o acercándose a la raíz, en cuyo caso la estructura se convierte en un árbol enraizado dirigido. Cuando un árbol enraizado dirigido tiene una orientación alejándose de la raíz, se le llama arborescencia [ 3 ] o out-tree ; [ 11 ] cuando tiene una orientación hacia la raíz, se le llama anti-arborescencia o in-tree . [ 11 ] El orden del árbol es el orden parcial en los vértices de un árbol con u < v 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 T -camino en G son comparables en este orden del árbol ( Diestel 2005 , p. 15) . Los árboles con raíz, a menudo con una estructura adicional como un ordenamiento de los vecinos en cada vértice, son una estructura de datos clave en la informática; véase 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 a cada vértice se le asigna una etiqueta única. Los vértices de un árbol etiquetado de n vértices (para enteros no negativos n ) suelen recibir las etiquetas 1, 2, …, 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 menor 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 padre. [ 24 ] Un ascendente de un vértice v es cualquier vértice que sea padre de v o sea (recursivamente) 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 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 con raíz es la longitud del camino descendente más largo desde ese vértice hasta una hoja. 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 ). La profundidad de un árbol es la profundidad máxima de cualquier vértice. La profundidad se necesita comúnmente 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, raíz y 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 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 (o árbol plano o árbol posicional [ 26 ] ) es un árbol con raíz en el que se especifica un orden para los hijos de cada vértice. [ 24 ] [ 27 ] Se le llama "árbol plano" porque un orden 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 por debajo de este. Dada una incrustación de un árbol con raíz en el plano, si se fija una dirección para los hijos, por ejemplo, de izquierda a derecha, entonces la incrustación proporciona un orden de los hijos. Por el contrario, dado un árbol ordenado, y dibujando convencionalmente la raíz en la parte superior, los vértices hijos en un árbol ordenado se pueden dibujar de izquierda a derecha, lo que produce una incrustación planar esencialmente única.

Propiedades

  • Todo árbol es un grafo bipartito . Un grafo es bipartito si y solo si no contiene ciclos de longitud impar. Dado que un árbol no contiene ningún ciclo, es bipartito.
  • Todo árbol con un número numerable de vértices es un grafo planar .
  • 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. Tipos más específicos de árboles de expansión, presentes en todo grafo finito conexo, incluyen árboles de búsqueda en profundidad y árboles de búsqueda en anchura . Generalizando la existencia de árboles de búsqueda en profundidad, todo grafo conexo con un número numerable de vértices tiene un árbol de Trémaux . [ 28 ] Sin embargo, algunos grafos de orden no numerable no tienen dicho árbol. [ 29 ]
  • Todo árbol finito con n vértices, donde n > 1 , tiene al menos dos vértices terminales (hojas). Este número mínimo de hojas es característico de los grafos de caminos ; el número máximo, n − 1 , solo se alcanza en los grafos estrella . El número de hojas es al menos igual al grado máximo de los vértices.
  • Para cualquier conjunto de tres vértices en un árbol, los tres caminos que los conectan tienen exactamente un vértice en común. En términos más generales, un vértice en un grafo que pertenece a los tres caminos más cortos entre tres vértices se denomina mediana de estos vértices. Dado que cada conjunto de tres vértices en un árbol tiene una mediana única, todo árbol es un grafo de mediana .
  • Todo árbol tiene un centro formado por un vértice o dos vértices adyacentes. El centro es el vértice central o los dos vértices centrales de cada camino más largo. De manera similar, todo árbol de n vértices tiene un centroide formado por un vértice o dos vértices adyacentes. En el primer caso, la eliminación del vértice divide el árbol en subárboles con 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 con exactamente n /2 vértices.
  • Las camarillas máximas de un árbol son precisamente sus aristas, 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 secuencias de Prüfer , que naturalmente muestran un resultado más fuerte: el número de árboles con vértices 1, 2, …, n de grados d 1 , d 2 , …, d n respectivamente, es el coeficiente multinomial.

(norte−2d1−1,d2−1,…,dnorte−1).{\displaystyle {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 grafo 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 grafo completo ). El problema similar de contar todos los subárboles independientemente de su 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 salvo isomorfismo de grafos . 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(norte)∼doαnortenorte−5/2como norte→∞,{\displaystyle t(n)\sim C\alpha ^{n}n^{-5/2}\quad {\text{cuando }}n\to \infty ,}

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

límitenorte→∞t(norte)doαnortenorte−5/2=1.{\displaystyle \lim _{n\to \infty }{\frac {t(n)}{C\alpha ^{n}n^{-5/2}}}=1.}

Esto es consecuencia de su estimación asintótica para el número r ( n ) de árboles enraizados sin etiquetar con n vértices:

r(norte)∼Dαnortenorte−3/2como norte→∞,{\displaystyle r(n)\sim D\alpha ^{n}n^{-3/2}\quad {\text{cuando }}n\to \infty ,}

con D ≈ 0,43992401257... y el mismo α que arriba (cf. Knuth (1997) , cap. 2.3.4.4 y Flajolet y Sedgewick (2009) , cap. VII.5, pág.  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 el OEIS ) .

Tipos de árboles

  • Un grafo de caminos (o grafo 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, …, n – 1 .
  • Un árbol estrellado consta de un vértice central llamado raíz y varios grafos de caminos conectados a él. Formalmente, un árbol es estrellado 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 a una distancia de 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 un árbol infinito con d aristas en cada vértice. Estos surgen como grafos de Cayley de grupos libres y en la teoría de edificios de Tits . En mecánica estadística se conocen como retículos de Bethe .

Véase también

Notas

  1. ↑ Bender & Williamson 2010 , pág. 171.
  2. ↑ Bender & Williamson 2010 , pág. 172.
  3. 1 2 3 4 Deo 1974 , pág. 206.
  4. ^ Véase Harary y Sumner (1980 ).
  5. 1 2 Véase Simion (1991) .
  6. 1 2 Véase Dasgupta (1999) .
  7. 1 2 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. 1 2 3 4 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-0Archivado (PDF) del original el 8 de septiembre de 2015 .
  15. ↑ David Makinson (2012). Conjuntos, lógica y matemáticas para la computación . Springer Science & Business Media. págs. 167–168 . ISBN  978-1-4471-2499-3.
  16. ↑ Kenneth Rosen (2011). Matemáticas discretas 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úremberg, (Alemania): Bauer und Raspe, 1847), presentó una demostración 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ó los 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" 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 (2019-10-09). "Árboles de expansión con pocos vértices de ramificación". arXiv : 1709.04937 [ math.CO ].
  20. ^ Harary y Prins 1959 , pág. 150.
  21. ↑ Chen, Wai-kai (1966). "Sobre árboles dirigidos y k- árboles dirigidos de un digrafo y su generación". SIAM Journal on Applied Mathematics . 14 (3): 550– 560. doi : 10.1137/0114048 . MR 0209064 . 
  22. 1 2 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. 1 2 3 4 5 6 7 Bender & Williamson 2010 , pág. 173.
  25. ↑ Véase Black, Paul E. (4 de mayo de 2007). "Árbol k-ario" . Instituto Nacional de Estándares y Tecnología de EE. UU. Archivado del original el 8 de febrero de 2015. Recuperado 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ág. 1174. ISBN   9780262046305Archivado del original el 16 de julio de 2023. Consultado el 20 de julio de 2023 .{{cite book}}: CS1 mantenimiento: ubicación ( enlace )
  27. ↑ Stanley, Richard P. (2012), Combinatoria enumerativa, vol. I , Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, p. 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

  • Bender, Edward A.; Williamson, S. Gill (2010), Listas, decisiones y gráficos. Con una introducción a la probabilidad.
  • Dasgupta, Sanjoy (1999), "Learning polytrees", Actas de la 15.ª Conferencia sobre Incertidumbre en 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) del original el 17/05/2019
  • 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 , MR 0603363 .
  • Kim, Jin H.; Pearl, Judea (1983), "Un modelo computacional para el razonamiento causal y diagnóstico en motores de inferencia", Actas de la 8.ª Conferencia Internacional Conjunta sobre Inteligencia Artificial (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", Matemáticas Discretas , 88 (1): 93– 104, doi : 10.1016/0012-365X(91)90061-6 , MR 1099270 .

Lecturas adicionales

  • 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 grafo 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", Annals of Mathematics , Segunda serie, 49 (3): 583– 599, doi : 10.2307/1969046 , JSTOR 1969046 .