Árbol (teoría de grafos)

Gráfico no dirigido, conectado y acíclico

Árboles
Un árbol etiquetado con 6 vértices y 5 aristas.
Vértices	v
Bordes	v  - 1
Número cromático	2 si v > 1
Tabla de gráficos y parámetros

En la teoría de grafos , un árbol es un grafo no dirigido en el que dos vértices cualesquiera están conectados por exactamente una ruta , o equivalentemente un grafo no dirigido acíclico conectado . ^[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 acíclico no dirigido, o equivalentemente una unión disjunta de árboles. ^[2]

Un polytree ^[3] (o árbol dirigido ^[4] o árbol orientado ^{[5] [6]} o red conectada individualmente ^[7] ) es un gráfico acíclico dirigido (DAG) cuyo gráfico subyacente no dirigido es un árbol. A polyforest (o bosque dirigida o forestal orientada a ) es un gráfico acíclico dirigido cuyo subyacente grafo no dirigido es un bosque.

Los diversos tipos de estructuras de datos a los que se hace referencia como árboles en informática tienen gráficos subyacentes que son árboles en la teoría de gráficos, aunque tales estructuras de datos son generalmente árboles con raíces . Un árbol enraizado puede ser dirigido, llamado árbol enraizado dirigido , ^{[8] [9]} ya sea haciendo que todos sus bordes apunten en dirección opuesta a la raíz, en cuyo caso se llama arborescencia ^{[4] [10]} o fuera del árbol ^{[11 ] [12]} —o hacer que todos sus bordes apunten hacia la raíz — en cuyo caso se llama anti-arborescencia ^[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 desarticulada de árboles enraizados. Un bosque enraizado puede ser dirigido, llamado bosque enraizado dirigido , ya sea haciendo que todos sus bordes apunten hacia la raíz en cada árbol enraizado, en cuyo caso se le llama ramificación o bosque externo , o haciendo que todos sus bordes apunten hacia la raíz. en cada árbol enraizado, en cuyo caso se denomina 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 G no dirigido 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 cualquier borde se añade a G .
• G está conectado, pero sería desconectado si cualquier borde solo se elimina de G .
• G está conectado y el 3-vértice gráfico completo K ₃ no es un menor de G .
• Cualquiera de los dos vértices de G se pueden conectar mediante una ruta simple única .

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

• G está conectado y tiene n - 1 aristas.
• G está conectado, y cada subgrafo de G incluye al menos un vértice con cero o una arista incidente. (Es decir, G está conectado 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) generalmente no se considera un árbol: si bien está conectado de forma vacía como un grafo (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 bordes". Sin embargo, puede considerarse como un bosque que consta de cero árboles.

Un vértice interno (o vértice interior o vértice rama ) es un vértice de grado al menos 2. De manera similar, un vértice externo (o vértice exterior , vértice terminal de o de la hoja ) es un vértice de grado 1.

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

Bosque

Un bosque es un gráfico no dirigido en el que dos vértices cualesquiera están conectados por un camino como máximo. De manera equivalente, un bosque es un gráfico acíclico no dirigido, cuyos componentes conectados son árboles; en otras palabras, el gráfico consiste en 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 bordes 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 los vértices totales y los bordes totales. TV - TE = número de árboles en un bosque .

Polytree

Artículo principal: Polytree

Un polytree ^[3] (o árbol dirigido ^[4] o árbol orientado ^{[5] [6]} o red conectada individualmente ^[7] ) es un gráfico acíclico dirigido (DAG) cuyo gráfico subyacente no dirigido es un árbol. En otras palabras, si reemplazamos sus bordes dirigidos con bordes no dirigidos, obtenemos un gráfico no dirigido que está conectado y es acíclico.

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

Polyforest

A polyforest (o bosque dirigida o forestal orientada a ) es un gráfico acíclico dirigido cuyo subyacente grafo no dirigido es un bosque. En otras palabras, si reemplazamos sus bordes dirigidos con bordes no dirigidos, obtenemos un gráfico no dirigido que es acíclico.

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 alejados de un vértice particular (ver ramificación ).

Árbol enraizado

Un árbol enraizado es un árbol en el que un vértice se ha designado como raíz . ^[20] A los bordes de un árbol enraizado se les puede asignar una orientación natural, ya sea hacia afuera 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 alejada de la raíz, se llama arborescencia ^[4] o árbol externo ; ^[11] cuando tiene una orientación hacia la raíz, se denomina anti-arborescencia o in-tree . ^[11] El orden de los árboles es elordenamiento parcial en los vértices de un árbol con u < v si y solo si la ruta única 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 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 el orden de los vecinos en cada vértice, son una estructura de datos clave en la informática; ver estructura de datos de árbol .

En un contexto en el que se supone que los árboles 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 en n vértices normalmente reciben las etiquetas 1, 2, ..., n . Un árbol recursivo es un árbol con 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 enraizado, el padre de un vértice v es el vértice conectado av en el camino a la raíz; cada vértice tiene un padre único excepto la raíz que no tiene padre. ^[20] Un hijo de un vértice v es un vértice del cual v es el padre. ^[20] Un ascendente de un vértice v es cualquier vértice que es el padre de v o es (recursivamente) el ascendente del padre de v . Un descendiente de un vértice v es cualquier vértice que sea hijo de vo es (recursivamente) descendiente de alguno de los hijos del v . Un hermano de un vértice v es cualquier otro vértice del árbol que tiene el mismo padre que v . ^[20] Una hoja es un vértice sin hijos. ^[20] Un vértice interno es un vértice que no es una hoja. ^[20]

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 de la ruta hasta su raíz ( ruta raíz ). Esto es comúnmente necesario en la manipulación de varios árboles autoequilibrados, árboles AVL en particular. La raíz tiene profundidad cero, las hojas tienen altura cero y un árbol con un solo vértice (por lo tanto, una raíz y una hoja) tiene profundidad y altura cero. Convencionalmente, un árbol vacío (un árbol sin vértices, si está permitido) tiene profundidad y altura -1.

Un árbol k-ario es un árbol enraizado en el que cada vértice tiene como máximo k hijos. ^[21] Los árboles de 2 arios a menudo se denominan árboles binarios , mientras que los árboles de 3 arios a veces se denominan árboles ternarios .

Árbol ordenado

Un árbol ordenado (o árbol plano ) es un árbol enraizado en el que se especifica un orden para los hijos de cada vértice. ^{[20] [22]} Esto se llama "árbol plano" porque ordenar los hijos equivale a incrustar el á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 enraizado en el plano, si uno fija la 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 dibujando convencionalmente la raíz en la parte superior, los vértices secundarios en un árbol ordenado se pueden dibujar de izquierda a derecha, lo que produce una incrustación plana esencialmente única.

Propiedades

• Cada árbol es un gráfico bipartito . Un gráfico es bipartito si y solo si no contiene ciclos de longitud impar. Dado que un árbol no contiene ciclos, es bipartito.
• Cada árbol es un gráfico de mediana .
• Cada árbol con solo un número numerable de vértices es un gráfico plano .
• Cada gráfico conectado G admite un árbol de expansión , que es un árbol que contiene cada vértice de G y cuyos bordes son bordes de G .
• Cada grafo conectado con solo un número numerable de vértices admite un árbol de expansión normal ( Diestel 2005 , Prop. 8.2.4).
• Existen grafos conectados con incontables vértices que no admiten un árbol de expansión normal ( Diestel 2005 , Prop. 8.5.2).
• 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 trayectoria ; el número máximo, n - 1 , se obtiene sólo mediante gráficas de estrellas . El número de hojas es al menos el grado máximo de vértice.
• Para cualesquiera tres vértices en un árbol, los tres caminos entre ellos tienen exactamente un vértice en común (este vértice se llama la mediana de estos tres vértices).
• Cada árbol tiene un centro que consta de un vértice o dos vértices adyacentes. El centro es el vértice del medio o los dos vértices del medio 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.

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 usa 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 ₁ , d ₂ , ..., d _n respectivamente, es el coeficiente multinomial

${\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 gráfico no dirigido , que se aborda en el teorema del árbol de matrices . (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 una fórmula cerrada para el número t ( n ) de árboles con n vértices hasta el isomorfismo de la gráfica . 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

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

con los valores C y α conocidos como aproximadamente 0.534949606 ... y 2.95576528565 ... (secuencia A051491 en la OEIS ), respectivamente. (Aquí, f ~ g significa que lim _{n → ∞} f / g = 1. ) Esto es una consecuencia de su estimación asintótica para el número r ( n ) de árboles con raíces no etiquetadas con n vértices:

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

con D alrededor de 0,43992401257 ... y el mismo α que el anterior (cf. Knuth (1997) , cap. 2.3.4.4 y Flajolet & Sedgewick (2009) , cap. VII.5, p. 475).

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

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

Tipos de árboles

• 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, ..., n −1.
• Un árbol con forma de estrella consta de un vértice central llamado raíz y varios gráficos de ruta adjuntos. Más formalmente, un árbol es parecido a una estrella si tiene exactamente un vértice de grado mayor que 2.
• Un árbol estrella es un árbol que consta de un solo vértice interno (y n −1 hojas). En otras palabras, un árbol estelar 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 dentro de la distancia 1 de un subgráfico 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 subgráfico de ruta central.
• Un árbol regular de grado d es el árbol infinito con d aristas en cada vértice. Estos surgen como los gráficos de Cayley de grupos libres y en la teoría de los edificios de Tits .

Ver también

• Hypertree
• Estructura de árbol
• Árbol (estructura de datos)
• Árbol de decisión
• Pseudoforestal
• Árbol binario sin raíz

Notas

1. Bender y Williamson , 2010 , p. 171.
2. Bender y Williamson , 2010 , p. 172.
3. Véase Dasgupta (1999) .
4. Deo , 1974 , p. 206.
5. Véase Harary y Sumner (1980) .
6. Véase Simion (1991) .
7. Véase Kim y Pearl (1983) .
8. Stanley Gill Williamson (1985). Combinatoria para Ciencias de la Computación . Publicaciones de Courier Dover. pag. 288. ISBN 978-0-486-42076-9.
9. Mehran Mesbahi; Magnus Egerstedt (2010). Métodos teóricos de grafos en redes multiagente . Prensa de la Universidad de Princeton. pag. 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. pag. 108. ISBN 978-1-4614-1701-9.
11. Deo , 1974 , p. 207.
12. Jonathan L. Gross; Jay Yellen; Ping Zhang (2013). Manual de teoría de grafos, segunda edición . Prensa CRC. pag. 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. pag. 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. pag. 52. ISBN  978-3-540-77978-0.
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áticas discretas y sus aplicaciones, 7ª edición . Ciencia de McGraw-Hill. pag. 747. ISBN 978-0-07-338309-5.
17. Alexander 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" , Revista filosófica , cuarta serie, 13  : 172-176.
    Sin embargo, debe mencionarse 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 Kirchhoffinvestigó 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 a través de 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 ecuaciones a las que nos conduce la investigación de la distribución lineal de corrientes galvánicas ), Annalen der Physik und Chemie , 72 (12): 497–508.
19. Harary y Prins , 1959 , p. 150.
20. Bender y Williamson , 2010 , p. 173.
21. Véase Black, Paul E. (4 de mayo de 2007). "árbol k-ario" . Instituto Nacional de Estándares y Tecnología de EE. UU . Consultado el 8 de febrero de 2015 .
22. Stanley, Richard P. (2012), Combinatoria enumerativa, vol. I , Cambridge Studies in Advanced Mathematics, 49 , Cambridge University Press, pág. 573, ISBN 9781107015425
23. Ver 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", en Proc. 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
• Harary, Frank ; Prins, Geert (1959), "El número de árboles homeomórficamente irreductibles 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. Octava Conferencia Conjunta Internacional 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. 9.
• Simion, Rodica (1991), "Árboles con factores 1 y árboles orientados", Matemáticas discretas , 88 (1): 93-104, doi : 10.1016 / 0012-365X (91) 90061-6 , MR  1099270.

Lectura adicional

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

• Diestel, Reinhard (2005), Graph Theory (3.a 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), The Art of Computer Programming Volume 1: Fundamental Algorithms (3.a 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", Annals of Mathematics , Second Series, 49 (3): 583–599, doi : 10.2307 / 1969046 , JSTOR  1969046.