Enumeración de grafos

La lista completa de todos los árboles libres en los vértices 2,3,4: $2^{2-2}=1$ árbol con 2 vércies, $3^{3-2}=3$ árboles con 3 vértices y $4^{4-2}=16$ árboles con 4 vértices.

En la teoría de combinatoria, un área de las matemáticas, la enumeración de grafos describe una clase de problemas de enumeración combinatoria en la que se debe contar grafos dirigidos o no dirigidos de un tipo determinado, usualmente como función del número de vértices del grafo.​ Los pioneros en esta área de las matemáticas fueron Pólya, Cayley y Redfield.

En ciertos problemas de enumeración de grafos se consideran a los vértices del grafo como etiquetados de tal manera que se distingan entre sí mientras que en otros problemas cualquier permutación de los vértices se considera parte del mismo grafo. En general, los problemas etiquetados tienden a ser de más fácil resolución que los problemas no etiquetados.​

Algunos resultados importantes en esta área:

• El número de grafos no dirigidos con n vértices etiquetados es 2^{n(n − 1)/2}.​
• El número de grafos dirigidos con n vértices etiquetados es 2^n(n − 1).​
• El número C_n de grafos conectados no dirigidos de n vértices etiquetados satisface la relación de recurrencia​

$C_{n}=2^{n \choose 2}-{\frac {1}{n}}\sum _{k=1}^{n-1}k{n \choose k}2^{n-k \choose 2}C_{k}.$

de lo que se puede calcular con facilidad, para n = 1, 2, 3, ..., que los valores para C_n son

1, 1, 4, 38, 728, 26704, 1866256, ...(sucesión A001187 en OEIS)

• El número de árboles libres con n vértices etiquetados es n^n − 2 (Fórmula de Cayley).
• El número de caterpilars de n vértices no etiquetadas es

$2^{n-4}+2^{\lfloor (n-4)/2\rfloor }.$

Referencias

• Datos: Q5597086