¿Por qué el número de gráficos en$n$ vértices explota tan rápido?

Question

Véase, por ejemplo aquí: https://en.wikipedia.org/wiki/Graph_enumeration

Yo habría pensado (ingenuamente) que el número de gráficos en $n$ vértices sería sólo crecer como $\mathscr{O}\left( _nC_2\right)$, pero claramente se crece mucho más rápido. Incluso el número de árboles que vuela más rápido que el factorial.

https://en.wikipedia.org/wiki/Cayley%27s_formula

¿Por qué el número de gráficos volar mucho más rápido que casi cualquier otra cosa?

Yo habría pensado que habría sido solo una cuestión de seleccionar las cuales 2 vértices de $n$ a conectar con un borde, lo que aparentemente se puede hacer con $\mathscr{O}\left( _nC_2\right)$ del tiempo. Lo que me estoy perdiendo?

Answer 1

$\binom{n}{2}$ es el número de posibles aristas en un gráfico con$n$ vértices. Cada subconjunto del conjunto de aristas crea un gráfico, por lo que hay $$ 2 ^ {\ binom {n} {2}} $$ gráficos. Eso crece bastante rápido.

Answer 2

Además de la primera respuesta, creo que vale la pena mencionar que la más significativa cantidad aquí no es el número de todos los gráficos en $n$ etiquetado de los vértices, que es $2^{{n\choose 2}}$ como ya se señaló, pero el número de no-isomorfo gráficos en $n$ vértices, ya que por ejemplo hay $n!/2$ formas en que el mismo gráfico de $\cdot\to \cdot \to \ldots\to \cdot$ puede ser realizado si a usted le preocupan las etiquetas. El número de nonisomorphic gráficos en $n$ vértices es trivialmente inferior delimitada por $$ \frac{2^{{n\choose 2}}}{n!}\approx 2^{n^2/2-n\log n}$$ (véase esta cuestión), por lo que es todavía un gran número de