Enumerar todos los gráficos no isomórficos de cierto tamaño.

Me gustaría enumerar todos los gráficos no dirigidos de tamaño $n$ , pero solo necesito una instancia de cada clase de isomorfismo . En otras palabras, quiero enumerar todos los gráficos no isomorfos (no dirigidos) en $n$ vértices. ¿Cómo puedo hacer esto?

Más precisamente, quiero un algoritmo que genere una secuencia de gráficos no dirigidos $G_1,G_2,\dots,G_k$ , con la siguiente propiedad: por cada gráfico no dirigido $G$ en $n$ vértices, existe un índice $i$ tal que $G$ es isomorfo a $G_i$ . Me gustaría que el algoritmo sea lo más eficiente posible; en otras palabras, la métrica que me interesa es el tiempo de ejecución para generar e iterar a través de esta lista de gráficos. Un objetivo secundario es que sería bueno si el algoritmo no es demasiado complejo de implementar.

Tenga en cuenta que necesito tener al menos un gráfico de cada clase de isomorfismo, pero está bien si el algoritmo produce más de una instancia. En particular, está bien si la secuencia de salida incluye dos gráficos isomórficos, si esto ayuda a facilitar la búsqueda de dicho algoritmo o permite algoritmos más eficientes, siempre que cubra todos los gráficos posibles.

Mi aplicación es la siguiente: tengo un programa que quiero probar en todos los gráficos de tamaño $n$ . Sé que si dos gráficos son isomorfos, mi programa se comportará igual en ambos (será correcto en ambos o incorrecto en ambos), por lo que es suficiente enumerar al menos un representante de cada clase de isomorfismo, y luego probar el programa en esas entradas. En mi aplicación, $n$ es bastante pequeño.

Algunos algoritmos candidatos que he considerado:

• Podría enumerar todas las matrices de adyacencia posibles, es decir, todas las matrices simétricas $n\times n$ 0-o-1 que tienen todos los 0 en las diagonales. Sin embargo, esto requiere enumerar $2^{n(n-1)/2}$ matrices. Muchas de esas matrices representarán gráficos isomórficos, por lo que parece que está desperdiciando mucho esfuerzo.

• Podría enumerar todas las matrices de adyacencia posibles y, para cada una, probar si es isomorfo a cualquiera de los gráficos que he generado anteriormente; si no es isomorfo a nada de lo que se haya emitido anteriormente, imprímalo. Esto acortaría enormemente la lista de resultados, pero aún requiere al menos $2^{n(n-1)/2}$ pasos de cálculo (incluso si suponemos que la verificación del isomorfismo del gráfico es súper rápida), por lo que no es mucho mejor según mi métrica.

• Es posible enumerar un subconjunto de matrices de adyacencia. En particular, si es un gráfico en n vértices V = { v 1 , ... , v n } , sin pérdida de generalidad, puedo suponer que los vértices están dispuestos de modo que deg v 1 ≤ deg v 2 ≤ ⋯ ≤ deg v $G$$n$$V=\{v_1,\dots,v_n\}$$\deg v_1 \le \deg v_2 \le \cdots \le \deg v_n$. En otras palabras, cada gráfico es isomorfo a uno donde los vértices están dispuestos en orden de grado no decreciente. Por lo tanto, es suficiente enumerar solo las matrices de adyacencia que tienen esta propiedad. No sé exactamente cuántas matrices de adyacencia hay, pero son muchas menos de , y se pueden enumerar con mucho menos de 2 n ( n - 1 ) / 2 pasos de cálculo. Sin embargo, esto todavía deja mucha redundancia: muchas clases de isomorfismo se cubrirán muchas veces, por lo que dudo que esto sea óptimo.$2^{n(n-1)/2}$$2^{n(n-1)/2}$

¿Podemos hacerlo mejor? Si entiendo correctamente, ¡hay aproximadamente Clases de equivalencia de gráficos no isomórficos. ¿Podemos encontrar un algoritmo cuyo tiempo de ejecución sea mejor que los algoritmos anteriores? ¡Cuán cerca podemos llegar a ∼ 2 n ( n - 1 ) / 2 / n ! ¿límite inferior? Me preocupo principalmente por la capacidad de seguimiento para n pequeña (por ejemplo, n = 5 o n = $2^{n(n-1)/2}/n!$$\sim 2^{n(n-1)/2}/n!$$n$$n=5$$n=8$más o menos; lo suficientemente pequeño como para que se pueda ejecutar un algoritmo de este tipo hasta su finalización), no tanto sobre los asintóticos para grande .$n$

Relacionado: Construir matrices binarias no equivalentes (aunque desafortunadamente esa no parece haber recibido una respuesta válida).

Probablemente, la forma más fácil de enumerar todos los gráficos no isomórficos para recuentos de vértices pequeños es descargarlos de la colección de Brendan McKay . El algoritmo de enumeración se describe en el artículo de McKay [1] y funciona extendiendo los no isomorfos de tamaño n-1 de todas las formas posibles y verificando si el nuevo vértice era canónico. Se implementa como gengen el verificador de isomorfismo gráfico de McKay nauty.

[1]: BD McKay, Aplicaciones de una técnica para enumeración etiquetada , Congressus Numerantium, 40 (1983) 207-221.

Propongo una mejora en su tercera idea: llenar la matriz de adyacencia fila por fila, haciendo un seguimiento de los vértices que son equivalentes en cuanto a su grado y adyacencia a los vértices previamente rellenados. Entonces, inicialmente las clases de equivalencia consistirán en todos los nodos con el mismo grado.
Cuando un vértice recién llenado es adyacente solo a algunos de los nodos equivalentes, cualquier elección lleva a representantes de las mismas clases de isomrfismo. Por lo tanto, solo consideramos la asignación, donde el vértice actualmente lleno es adyacente a los vértices equivalentes con el número más alto (y dividimos la clase de equivalencia en dos para el proceso restante).

$n<6$
$(1,2)$$(3,4)$$n=6$

Una implementación ingenua de este algoritmo se encontrará en callejones sin salida, donde resulta que la matriz de adyacencia no se puede llenar de acuerdo con el conjunto dado de grados y asignaciones anteriores. Puede valer la pena detectarlos / filtrarlos temprano. Algunas ideas:

• Si la suma de grados es impar, nunca formarán un gráfico
• Rellene las entradas para vértices que deben conectarse a todos / ninguno de los vértices restantes inmediatamente.

Estos documentos pueden ser de interés.

"Sobre la representación sucinta de gráficos", Gyorgy Turan, Discrete Applied Mathematics, Volume 8, Issue 3, July 1984, pp. 289-294 http://www.sciencedirect.com/science/article/pii/0166218X84901264

"Representación sucinta de gráficos generales sin etiquetar", Moni Naor, Discrete Applied Mathematics, Volume 28, Issue 3, September 1990, pp. 303-307 http://www.sciencedirect.com/science/article/pii/0166218X9090011Z

Presentan funciones de codificación y decodificación para codificar un gráfico con etiqueta de vértice de modo que dos de estos gráficos se asignen a la misma palabra de código si y solo si uno resulta de permutar las etiquetas de vértice de la otra.

Además, se demuestra que las funciones de codificación y decodificación son eficientes.

El primer artículo trata de gráficas planas. En el segundo artículo, se elimina la restricción de planaridad.

EDITAR: Este documento también podría ser relevante:

Isomorfismo gráfico en tiempo cuasi-polinómico, Laszlo Babai, Universidad de Chicago, Preprint en arXiv, 9 de diciembre de 2015 http://arxiv.org/pdf/1512.03547v1.pdf

El anuncio de Babai de su resultado fue noticia: https://www.sciencenews.org/article/new-algorithm-cracks-graph-problem

¿Pero quizás me equivoco al combinar la pregunta de los OP con estos tres documentos? El OP desea enumerar gráficos no isomórficos, pero aún puede ser útil contar con métodos eficientes para determinar cuándo dos gráficos SON isomórficos?

Hay un artículo de principios de los noventa que trata exactamente esta pregunta:

Algoritmos eficientes para enumerar gráficos sin etiqueta de Leslie Goldberg.

El enfoque garantiza que se enumera exactamente un representante de cada clase de isomorfismo y que solo hay un retraso polinómico entre la generación de dos gráficos posteriores.

$n$