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]
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 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]
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.
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 ).
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 ).
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 externo ; [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 enteros no negativos n ) generalmente reciben 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 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 .
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.
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,…, 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 , 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)).
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
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 para el número r ( n ) de árboles enraizados sin etiquetar 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 [27]
{{cite book}}
: Mantenimiento CS1: ubicación ( enlace )