Cuántos posibles grafos simples diferentes hay con un conjunto de vértices V de n elementos

Question

Si V es un conjunto con n elementos, ¿cuántos grafos simples y no dirigidos diferentes hay con el conjunto de vértices V?

Answer 1

Si considera que los gráficos isomórficos son diferentes, entonces obviamente la respuesta es $2^{n\choose 2}$ . La mayoría de los grafos no tienen automorfismos no triviales, por lo que hasta el isomorfismo el número de grafos diferentes es asintóticamente $2^{n\choose 2}/n!$ . Esto se remonta a un famoso método de Pólya (1937), véase este documento para más información. Puede encontrar el documento original de Pólya aquí .

Answer 2

Ver http://oeis.org/A000088 . Esta es la secuencia que da el número de clases de isomorfismo de los grafos simples en n vértices, también llamado número de grafos en n nodos no etiquetados. Aquí también encontrarás muchas referencias relevantes.