Árbol (teoría de grafos)

En teoría de grafos, un árbol es un grafo en el que cualquier par de vértices están conectados por exactamente un camino, o alternativamente, es un grafo conexo acíclico.^[1]​

Un bosque es un grafo disconexo acíclico. Alternativamente, se puede definir como una unión disjunta de árboles, es decir, es un grafo disconexo cuyas componentes son árboles.^[1]​

Un árbol es un grafo simple no dirigido G que satisface cualquiera de estas condiciones alternativas:

Las condiciones anteriores son todas equivalentes, es decir, si se cumple una de ellas otras también se cumplen. Para árboles finitos además se cumple que: Si un árbol G tiene un número finito de vértices, n, entonces tiene n − 1 aristas.

Algunas definiciones relacionadas con los árboles son:

Un árbol es llamado k-ario si cada nodo tiene, como máximo, k hijos. Un caso particularmente importante es el de un árbol 2-ario, al cual se denomina árbol binario.

Si todos los nodos del árbol exceptuando las hojas, poseen exactamente k hijos, ese árbol además de ser k-ario es completo.

Otro caso particular es el del árbol estrella, el cual consiste de un único nodo, que es la raíz. El resto de sus vértices son hojas. Todo árbol estrella de k vértices tiene un único nodo con k-1 hijos, por lo tanto, todo árbol estrella de k vértices es (k-1)-ario.

Los árboles son grafos mínimamente conexos, ya que todas sus aristas son puentes o aristas de corte. Por lo tanto, se consideran grafos poco cohesivos.^[1]​

Un árbol de n vértices tiene n-1 aristas. En general, un bosque de m componentes tiene n-m aristas.^[1]​

Todo árbol es a su vez un grafo con sólo un conjunto numerable de vértices es además un grafo plano.

Todo grafo conexo G admite un árbol de expansión, que es un árbol que contiene cada vértice de G y cuyas aristas son aristas de G.

Todo árbol k-ario completo de altura h tiene k^h hojas.

Dado n vértices etiquetados, hay n ⁿ⁻² maneras diferentes de conectarlos para construir un grafo. El resultado se llama fórmula de Cayley. El número de árboles con n vértices de grado d₁,d₂,...,d_n es:

${displaystyle {n-2 choose d_{1}-1,d_{2}-1,ldots ,d_{n}-1},}$

que es un coeficiente multinomial.

Contar el número de árboles no etiquetados es un problema complicado. De hecho, no se conoce ninguna fórmula para el número de árboles t(n) con n vértices (debe entenderse aquí el número de árboles diferentes 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, ... (sucesión A000055 en OEIS). Otter (1948) probó que

${displaystyle {t(n)sim Calpha ^{n}n^{-5/2}quad { ext{as }}n o infty ,}}$

Una fórmula más exacta para el comportamiento asintótico de t(n) implica que hay dos números α y β (α ≈ 3 y β ≈ 0.5) tales que:

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