Cómo calcular el número de posibles conectado gráficas sencillas con $n$ vértices etiquetados

Question

Supongamos que tenemos a un conjunto de vértices etiquetados $1,2,\ldots,n$.

Hay varias formas de conectar los vértices utilizando los bordes. Suponga que la gráfica es simple y conectado.

En lo eficiente (o si no hay manera eficiente, usted puede decirle a mí cualquiera que sea el procedimiento que usted puede pensar de) manera hemos de ser capaces de calcular el número de formas posibles de la gráfica puede ser hecho? (incluso si algunos grafos son isomorfos entre sí, que son considerados como independientes de los casos.)

Answer 1

Hay $\binom{n}2=\frac12n(n-1)$ pares de puntos distintos. Si usted no permite que los bucles o varias aristas, cada uno de estos pares determina una posible ventaja, y usted puede tener cualquier subconjunto de los posibles bordes. Un conjunto con $\binom{n}2$ miembros $2^{\binom{n}2}$ subconjuntos, por lo que hay $2^{\binom{n}2}$ posible grafos sin bucles o varias aristas.

Si la demanda de que los gráficos de estar conectado, el problema se vuelve mucho más difícil. De su último comentario considero que son, en efecto, contando etiquetado de los gráficos. Esta secuencia de números se A001187 en el On-Line de la Enciclopedia de Secuencias de Enteros. Si $d_n$ es el número de etiquetado, conectado, gráficas simples en $n$ vértices, los números de $d_n$ satisfacer la recurrencia

$$\sum_k\binom{n}kkd_k2^{\binom{n-k}2}=n2^\binom{n}2\;,$$

from which it's possible to calculate $d_n$ for small values of $$ n. Esta recurrencia se deriva como la fórmula (3.10.2) en Herbert S. Wilf, generatingfunctionology, 2da edición, que está disponible para su descarga gratuita aquí.

De acuerdo a MathWorld, Brendan McKay del paquete de software nauty incluye una rutina que enumera de manera eficiente de tales gráficos, disponible aquí.

Si usted cuenta sin etiquetar los gráficos en su lugar, de modo que usted no cuente isomorfo gráficos por separado, se obtiene la secuencia mencionada por Arturo en los comentarios.

Answer 2

Usted puede utilizar exponencial de la generación de las funciones de este. La exponencial de la generación de funciones de $C(x)$ para la conexión de la etiqueta gráficos y $D(x)$ para todos los etiquetados de los gráficos están relacionados por

$$D(x)=\mathrm e^{C(x)-1}\;,$$

que se puede mostrar mediante la descomposición de una etiqueta gráfico en sus componentes conectados.

Como otros han señalado, hemos

$$ D(x)=\sum_{n=0}^\infty\frac{2^{n(n-1)/2}}{n!}x^n\;, $$

así

$$ \begin{align} C(x) &= 1+\log\sum_{n=0}^\infty\frac{2^{n(n-1)/2}}{n!}x^n \\ &= 1+\log\left(1+x+\frac2{2!}x^2+\frac8{3!}x^3+\frac{64}{4!}x^4+\dotso\right) \\ &= 1+x+\frac1{2!}x^2+\frac4{3!}x^3+\frac{38}{4!}x^4+\dotso \;. \end{align} $$

Por lo tanto, hay $1,1,1,4,38,\dotsc$ diferentes conectado gráficos en $0,1,2,3,4,\dotsc$ etiquetado de los vértices.

Answer 3

Como he indicado en el comentario, esta es la secuencia de A001349 en el On-Line de la Enciclopedia de Secuencias de Enteros. No hay ninguna cerrado fórmula de la lista, pero hay un par de referencias a la computadora cálculos y algoritmos. Yo sugiero que es el lugar donde desea iniciar.

Answer 4

SI se trata de un simple, gráfica conectada, a continuación, para el conjunto de vértices {v: v existe en V}, v es adyacente a todos los demás vértices en V. en Este tipo de gráfico se denota Kn. Por Kn, habrá n vértices y (n(n-1))/2 aristas.

Para determinar cuántos subconjuntos de los bordes de un Kn gráfico va a producir, considerar el powerset como Brian M. Scott dijo en un comentario anterior. Si S es un conjunto finito con n elementos, entonces el powerset de S tendrá 2^n elementos, donde n es el número de elementos del conjunto S.

Suponiendo que el n en Kn es cualquier entero no negativo, entonces ¿no debería el conjunto considerarse countably infinito? Si es así, esto haría que la cardinalidad de la powerset Alepha 0.