Árbol (teoría de grafos)

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 de manera equivalente, un grafo no dirigido acíclico conectado. Un bosque es un gráfico no dirigido en el que dos vértices cualesquiera están conectados por como máximo camino, o de manera equivalente un gráfico no dirigido acíclico, o de manera equivalente una unión disjunta de árboles.

Un poliárbol (o árbol dirigido o árbol orientado o red conectada individualmente) es un gráfico acíclico dirigido (DAG) cuyo gráfico subyacente no dirigido 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 diversos tipos de estructuras de datos denominadas á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, ya sea haciendo que todos sus bordes apunten lejos de la raíz, en cuyo caso se llama arborescencia o out-tree, o hacer que todos sus bordes apunten hacia la raíz, en cuyo caso se denomina anti-arborescence o in-tree. Algunos autores han definido un árbol enraizado como un gráfico dirigido. Un bosque enraizado es una unión inconexa de árboles enraizados. 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 denomina ramificado o fuera del bosque, o hacer que todos sus bordes apunten hacia la raíz en cada árbol enraizado, en cuyo caso se denomina anti-ramificación o dentro del bosque .

El término "árbol" fue acuñado en 1857 por el matemático británico Arthur Cayley.

Definiciones

Árbol

Un árbol es un gráfico no dirigido G que satisface cualquiera de las siguientes condiciones equivalentes:

• G está conectado y acíclico (no contiene ciclos).
• G es acíclico, y se forma un ciclo simple si se añade a cualquier borde G.
• G está conectado, pero se desconectaría si cualquier borde se quita de G.
• G está conectado y el gráfico completo 3-vertex K₃ no es un menor de edad G.
• Cualquier dos vértices en G se puede conectar por un único camino simple.

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

• G está conectado y ha n − 1 bordes.
• G está conectado, y cada subgrafo de G incluye al menos un vértice con cero o uno de los bordes del incidente. (Eso es, G está conectado y 1 degenerado.)
• G no tiene ciclos simples y tiene n − 1 bordes.

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: mientras que está conectado de forma vacía como un gráfico (cualquiera de los dos vértices pueden estar conectados por un camino), no está conectado a 0 (ni siquiera a (-1)) en la topología algebraica, a diferencia de los árboles no vacíos, y viola el "un vértice más que los bordes" relación. Sin embargo, puede ser considerado como un bosque que consta de 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 exterior, vértice terminal o 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.

Un árbol irreducible (o árbol reducido en serie) es un árbol en el que no existe un vértice de grado 2 (enumerado en la secuencia A000014 en el OEIS).

Bosque

Un bosque es un grafo no dirigido en el que dos vértices cualesquiera están conectados como máximo por 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 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 árbol único y un gráfico sin bordes son ejemplos de bosques. Dado que para cada árbol V − E = 1, podemos contar fácilmente la cantidad de árboles que hay dentro de un bosque por restando la diferencia entre el total de vértices y el total de aristas. TV − TE = número de árboles en un bosque.

Polytree

Un poliárbol (o árbol dirigido o árbol orientado o red conectada individualmente) 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 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 donde los bordes están todos dirigidos hacia un vértice particular, o todos dirigidos lejos de un vértice particular (ver arborescencia).

Polybosque

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

Algunos autores restringen la frase "bosque dirigido" al caso donde 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 bifurcación).

Árbol enraizado

Un árbol con raíz es un árbol en el que un vértice ha sido designado como raíz. A los bordes de un árbol con raíces se les puede asignar una orientación natural, ya sea lejos de o hacia la raíz, en cuyo caso la estructura se convierte en un árbol con raíces dirigidas. Cuando un árbol con raíz dirigida tiene una orientación que se aleja de la raíz, se denomina arborescencia o árbol exterior; cuando tiene una orientación hacia la raíz, se denomina antiarborescencia o in-tree. El orden del árbol es el ordenamiento 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 < span class="texhtml mvar" style="font-style:italic;">u. Un árbol con raíz T que es un subgrafo de algún gráfico G es un árbol normal si los extremos de cada ruta 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 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 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 enraizado etiquetado donde las etiquetas de los vértices respetan el orden del árbol (es decir, si u < v< /i> 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 < span class="texhtml mvar" style="font-style:italic;">v en la ruta a la raíz; cada vértice tiene un padre único excepto la raíz que no tiene padre. Un hijo de un vértice v es un vértice del cual v es el padre. Un ascendente de un vértice v es cualquier vértice que sea 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 v o es (recursivamente) el descendiente de cualquiera de los hijos de v. Un hermano de un vértice v es cualquier otro vértice del árbol que tiene el mismo padre que < span class="texhtml mvar" style="font-style:italic;">v. Una hoja es un vértice sin hijos. Un vértice interno es un vértice que no es una hoja.

La altura de un vértice en un árbol con raíz 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 a su raíz (ruta raíz). Esto suele ser necesario 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, una raíz y 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 es un árbol enraizado en el que cada vértice tiene como máximo k niños. 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) es un árbol con raíz en el que se especifica un orden para los hijos de cada vértice. Esto se llama un "árbol plano" porque un ordenamiento de los hijos equivale a una incrustación del árbol en el plano, con la raíz arriba y los hijos de cada vértice por debajo de 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 una ordenación 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 no contiene ciclos de longitud extraña. Como un árbol no contiene ciclos, es bipartito.
• Cada árbol con sólo muchos vértices es un gráfico plano.
• Cada gráfico conectado G admite un árbol de azotes, que es un árbol que contiene cada vértice de G y cuyos bordes son bordes de G. Los tipos más específicos que abarcan árboles, existentes en cada gráfico finito conectado, incluyen los árboles de búsqueda de profundidad y los primeros árboles de búsqueda. Generalizando la existencia de árboles de investigación de profundidad, cada gráfico conectado con sólo muchos vértices tiene un árbol de Trémaux. Sin embargo, algunos gráficos incontables no tienen tal árbol.
• Cada árbol finito con n vertices, con n ■ 1, tiene al menos dos vértices terminales (leaves). Este número mínimo de hojas es característico de los gráficos del camino; el número máximo, n − 1, se alcanza sólo por gráficos estrella. El número de hojas es al menos el grado máximo de vértice.
• Para cualquier tres vértices en un árbol, los tres caminos entre ellos tienen exactamente un vértice en común. Más generalmente, 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. Porque cada tres vértices en un árbol tienen una mediana única, cada árbol es un gráfico medio.
• Cada árbol tiene un centro compuesto por un vértice o dos vértices adyacentes. El centro es el vértice medio o dos vértices en cada camino más largo. Del mismo modo, todos n- árbol de vertex tiene un centroide que consiste en 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 que 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ⁿ⁻² árboles en n vértices etiquetados. Una prueba 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,ldotsd_{n}-1}$

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 matriz. (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 hay fórmula cerrada para el número t(n) de árboles con n vértices hasta que se conoce 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,... A000055 en el OEIS).

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

${displaystyle t(n)sim Calpha ^{n}n^{-5/2}quad {text{as }nto infty}$

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

${displaystyle lim _{nto infty}{frac {t(n)}{Calpha ^{n}n^{-5/2}}}=1.}$

Esta es una consecuencia de su estimación asintótica del número r(n) de árboles enraizados no etiquetados con < span class="texhtml mvar" style="font-style:italic;">n vértices:

${displaystyle r(n)sim Dalpha ^{n}n^{-3/2}quad {text{as }nto infty}$

con D ≈ 0.43992401257... y el mismo α que 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

1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, 32973,... A000081 en el OEIS)

Tipos de árboles

• A ruta gráfica (o gráfico lineal) consta de n vértices dispuestos en una línea, así que vértices i y i + 1 están conectados por un borde para i = 1,... n – 1.
• A árbol estrella consiste en un vértice central llamado root y varios gráficos de ruta adjuntas a él. Más formalmente, un árbol es estrellado si tiene exactamente un vértice de grado mayor que 2.
• A árbol estrella es un árbol que consiste en 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.
• A Árbol de orugas es un árbol en el que todos los vértices están a la distancia 1 de un subgrafo del sendero central.
• A árbol de langosta es un árbol en el que todos los vértices están a la distancia 2 de un subgrafo del camino central.
• A árbol regular grado d es el árbol infinito con d bordes 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.