Árbol (teoría de grafos)

[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.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.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.En general, un bosque de m componentes tiene n-m aristas.El resultado se llama fórmula de Cayley.Contar el número de árboles no etiquetados es un problema complicado.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).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: