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.
Dado n vértices etiquetados, hay n n−2 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 d1,d2,...,dn
es:
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 entederse 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
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:
No hay comentarios:
Publicar un comentario