Enumere todos os gráficos não isomórficos de um determinado tamanho

Gostaria de enumerar todos os gráficos não direcionados de tamanho , mas preciso apenas de uma instância de cada classe de isomorfismo . Em outras palavras, quero enumerar todos os gráficos não isomórficos (não direcionados) em vértices. Como posso fazer isso?$n$$n$

Mais precisamente, eu quero um algoritmo que gere uma sequência de gráficos não direcionados $G_1,G_2,\dots,G_k$ , com a seguinte propriedade: para todo gráfico não direcionado $G$ em $n$ vértices, existe um índice $i$ tal que $G$ seja isomórfico para $G_i$ . Eu gostaria que o algoritmo fosse o mais eficiente possível; em outras palavras, a métrica com a qual me preocupo é o tempo de execução para gerar e iterar nesta lista de gráficos. Um objetivo secundário é que seria bom se o algoritmo não fosse muito complexo para implementar.

Observe que eu preciso ter pelo menos um gráfico de cada classe de isomorfismo, mas tudo bem se o algoritmo produzir mais de uma instância. Em particular, não há problema se a sequência de saída incluir dois gráficos isomórficos, se isso facilitar a localização de um algoritmo ou permitir algoritmos mais eficientes, desde que abranja todos os gráficos possíveis.

Minha aplicação é a seguinte: Eu tenho um programa que quero testar em todos os gráficos de tamanho $n$ . Sei que se dois gráficos são isomórficos, meu programa se comportará da mesma maneira em ambos (será correto em ambos ou incorreto em ambos), portanto, basta enumerar pelo menos um representante de cada classe de isomorfismo e testar o programa sobre essas entradas. Na minha aplicação, $n$ é bastante pequeno.

Alguns algoritmos candidatos que considerei:

• Eu poderia enumerar todas as matrizes de adjacência possíveis, ou seja, todas as matrizes simétricas $n\times n$ 0-ou-1 que possuem todos os 0 nas diagonais. No entanto, isso requer enumerar $2^{n(n-1)/2}$ matrizes. Muitas dessas matrizes representam gráficos isomórficos, então isso parece estar desperdiçando muito esforço.

• Eu poderia enumerar todas as matrizes de adjacência possíveis e, para cada uma delas, testar se é isomórfica para qualquer um dos gráficos que eu produzi anteriormente; se não for isomórfico para qualquer saída anterior, faça a saída. Isso reduziria muito a lista de saída, mas ainda requer pelo menos $2^{n(n-1)/2}$ etapas de cálculo (mesmo se assumirmos que a verificação do isomorfismo do gráfico é super rápida), por isso não é muito melhor minha métrica.

• É possível enumerar um subconjunto de matrizes de adjacência. Em particular, se é um gráfico nos vértices , sem perda de generalidade, posso assumir que os vértices estão organizados de modo que . Em outras palavras, todo gráfico é isomórfico para um onde os vértices são organizados em ordem de grau não decrescente. Portanto, basta enumerar apenas as matrizes de adjacência que possuem essa propriedade. Não sei exatamente quantas matrizes de adjacência existem, mas são muito menos que , e elas podem ser enumeradas com muito menos quen V = { v 1 , … , v n } deg v 1 ≤ deg v 2 ≤ ⋯ ≤ deg v n 2 n ( n - 1 ) / 2 2 n ( n - 1 ) /$G$$n$$V=\{v_1,\dots,v_n\}$$\deg v_1 \le \deg v_2 \le \cdots \le \deg v_n$$2^{n(n-1)/2}$$2^{n(n-1)/2}$etapas de computação. No entanto, isso ainda deixa muita redundância: muitas classes de isomorfismo ainda serão abordadas muitas vezes, então duvido que isso seja ótimo.

Podemos fazer melhor? Se bem entendi, existem aproximadamenteclasses de equivalência de gráficos não isomórficos. Podemos encontrar um algoritmo cujo tempo de execução seja melhor que os algoritmos acima? Quão perto podemos chegar alimite inferior? Preocupo-me principalmente com a rastreabilidade de pequeno (digamos, ou ou mais; pequeno o suficiente para que seja possível executar tal algoritmo até a conclusão), e não tanto com os assintóticos para grande .$2^{n(n-1)/2}/n!$$\sim 2^{n(n-1)/2}/n!$$n$$n=5$$n=8$$n$

Relacionado: Construindo matrizes binárias desigual (embora, infelizmente, não pareça ter recebido uma resposta válida).

Provavelmente, a maneira mais fácil de enumerar todos os gráficos não isomórficos para pequenas contagens de vértices é baixá-los da coleção de Brendan McKay . O algoritmo de enumeração é descrito no artigo de McKay [1] e funciona estendendo não-isomorfos do tamanho n-1 de todas as maneiras possíveis e verificando se o novo vértice era canônico. É implementado como gengno verificador de isomorfismo gráfico de McKay nauty.

[1]: BD McKay, Aplicações de uma técnica para enumeração rotulada , Congressus Numerantium, 40 (1983) 207-221.

Proponho uma melhoria em sua terceira ideia: preencha a matriz de adjacência linha por linha, mantendo o controle de vértices equivalentes em relação ao seu grau e adjacência aos vértices preenchidos anteriormente. Portanto, inicialmente as classes de equivalência consistirão em todos os nós com o mesmo grau.
Quando um vértice recém-preenchido é adjacente a apenas alguns dos nós equivalentes, qualquer opção leva a representantes das mesmas classes de isomorfismo. Portanto, consideramos apenas a atribuição, onde o vértice atualmente preenchido é adjacente aos vértices equivalentes com o número mais alto (e dividimos a classe de equivalência em duas para o processo restante).

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

Uma implementação ingênua desse algoritmo terá becos sem saída, onde acontece que a matriz de adjacência não pode ser preenchida de acordo com o conjunto de graus e atribuições anteriores. Pode valer a pena algum esforço para detectar / filtrar essas informações mais cedo. Algumas ideias:

• Se a soma dos graus for ímpar, eles nunca formarão um gráfico
• Preencha as entradas dos vértices que precisam ser conectados a todos / nenhum dos vértices restantes imediatamente.

Esses documentos podem ser interessantes.

"Sobre a representação sucinta de gráficos", Gyorgy Turan, Matemática Aplicada Discreta, Volume 8, Edição 3, Julho de 1984, pp. 289-294 http://www.sciencedirect.com/science/article/pii/0166218X84901264

"Representação sucinta de gráficos gerais não identificados", Moni Naor, Matemática Aplicada Discreta, Volume 28, Edição 3, setembro de 1990, pp. 303-307 http://www.sciencedirect.com/science/article/pii/0166218X9090011Z

Eles apresentam funções de codificação e decodificação para codificar um gráfico marcado com vértice, de modo que dois desses gráficos sejam mapeados para a mesma palavra de código se e somente se um resultar da permeação dos rótulos de vértice do outro.

Além disso, está provado que as funções de codificação e decodificação são eficientes.

O primeiro artigo trata de gráficos planares. No segundo artigo, a restrição de planaridade é removida.

EDIT: Este documento também pode ser relevante:

Isomorfismo gráfico em tempo quase polinomial, Laszlo Babai, Universidade de Chicago, pré-impressão em arXiv, 9 de dezembro de 2015 http://arxiv.org/pdf/1512.03547v1.pdf

O anúncio de seu resultado por Babai foi notícia: https://www.sciencenews.org/article/new-algorithm-cracks-graph-problem

Mas talvez eu esteja enganado em confundir a questão dos POs com esses três documentos? O PO deseja enumerar gráficos não isomórficos, mas ainda pode ser útil ter métodos eficientes para determinar quando dois gráficos SÃO isomórficos?

Há um artigo do início dos anos 90 que trata exatamente dessa questão:

Algoritmos eficientes para listar gráficos não rotulados por Leslie Goldberg.

A abordagem garante que exatamente um representante de cada classe de isomorfismo seja enumerado e que haja apenas um atraso polinomial entre a geração de dois gráficos subsequentes.

$n$