¿Cuántos grafos no isomórficos con n vértices y m aristas hay?

Question

¿Podría alguien decirme cómo encontrar el número de todos los grafos no isomórficos con $m$ vértices y $n$ aristas. (El gráfico es simple, no dirigido)

En mi problema particular, $m =20, n=180$

Intento de solución:

1. Encuentra el número total posible de aristas (para que cada vértice esté conectado con todos los demás) $k = n(n-1)/2 = 20\cdot19/2 = 190$

2. Encuentra el número de todas las gráficas posibles: $s = C(n,k) = C(190, 180) = 13278694407181203$

Ahora, estoy atascado porque una gran parte del número anterior representa gráficos isomórficos, y no tengo ni idea de cómo encontrar todos los que no son isomórficos...

Answer 1

En primer lugar, permíteme decir que puedes encontrar la respuesta a esta pregunta en Sage usando el generador de nauty. Si vas a ser un estudiante serio de teoría de grafos, Sage podría ser muy útil.

count = 0
for g in graphs.nauty_geng("20 180:180"):
    count = count+1
print count

La respuesta es 4613. Pero, esto no es fácil de ver sin un programa de ordenador.

En este punto, tal vez sería bueno empezar a pensar en términos del número de conectado gráficos con un máximo de 10 aristas. Entonces, todos los gráficos que busques serán uniones de éstos. Deberías ser capaz de averiguar estos casos más pequeños. Si alguno te resulta demasiado difícil, lo más probable es que esté en alguna tabla, para que puedas buscarlo.

Gráficos conectados de orden n y k aristas es:

n = 1, k = 0: 1
n = 2, k = 1: 1
n = 3, k = 2: 1
n = 3, k = 3: 1
n = 4, k = 3: 2
n = 4, k = 4: 2
n = 4, k = 5: 1
n = 4, k = 6: 1
n = 5, k = 4: 3
n = 5, k = 5: 5
n = 5, k = 6: 5
n = 5, k = 7: 4
n = 5, k = 8: 2
n = 5, k = 9: 1
n = 5, k = 10: 1
.
.
.
n = 10, k = 9: 106
n = 10, k = 10: 657
n = 11, k = 10: 235

Reconozco que he utilizado Sage para los 3 últimos. Pero, sé que el Atlas de los Gráficos contiene todos estos excepto el último, en P7.