Isomorfismo gráfico e grupo automorfismo

Uma abordagem comum para decidir se dois gráficos dados são isomórficos é calcular o chamado rótulo canônico (alternativamente, gráfico canônico) de cada gráfico e verificar se eles correspondem ou não.

Ferramentas como o Nauty calculam o gráfico canônico através de árvores de pesquisa removidas usando algumas idéias inteligentes que dependem, entre outras, de automorfismos de gráficos. Por isso, o Nauty permite calcular um gerador do grupo automorfismo gráfico. No entanto, até onde eu entendi a idéia por trás de Nauty, o cálculo do gráfico canônico não requer que se calcule um gerador do grupo automorfismo do gráfico em geral.

Minha pergunta é, portanto: existe uma relação formal de complexidade teórica entre GI e o cálculo de um grupo gerador do grupo gráfico de automorfismo?

Muito Obrigado.

Como os comentários sugerem, pode haver confusão sobre o que você chama de "IG". Mas a ideia aqui está correta. É equivalente a tempo polinomial encontrar geradores de um grupo automorfismo, assim como encontrar um isomorfismo entre dois grupos. A idéia é "clássica", pois aparece em trabalhos iniciais, como o isomorfismo do grupo de Luks, em valência limitada, em tempo polinomial, e mesmo lá acho que a idéia foi considerada "bem conhecida".

Afirmação. Deixe e ser ligados entre si gráficos. Em seguida, se, e apenas se, a cada gerador conjunto de contém um elemento de tal modo que .$G$$H$$G\cong H$$S$$\mathrm{Aut}(G\sqcup H)$$g\in S$$G^g=H$

Observação Importante aqui é que todos os grupos geradores trocam os gráficos, caso contrário, às vezes você calcula geradores que não resolvem o problema. Assim, por exemplo, o isomorfismo de dois grupos não produz tão facilmente dessa maneira. Isso ocorre porque nem todos os grupos geradores de vai trocar e , quando . em vez disso, eles podem ir para cópias diagonais. Essa situação pode ser corrigida, mas requer um argumento mais forte. Portanto, a abordagem aqui não é aplicável a todas as categorias.$\mathrm{Aut}(G\times H)$$G$$H$$G\cong H$

Prova. Para o inverso se cada conjunto (ou mesmo um) geradora de intercâmbios e , em seguida, pela restrição de que a função de . Então, isso é tudo sobre a direção a frente. (Mas eu mencionei isso porque a prova é por contraposição, para que pareça que estou prestes a seguir a mesma direção.)$\mathrm{Aut}(G\sqcup H)$$G$$H$$G\cong H$$G$

Suponha é gerado por um conjunto , cujos elementos enviar para , e de , (nota por pressuposto conectividade se um vértice do é enviado para um vértice de , em seguida o gráfico inteiro é enviado para e, portanto, pelo buraco do pombo, algum vértice em será enviado para e, portanto, e teremos trocado os dois gráficos). Como envia para , então toda composição de funções em$\mathrm{Aut}(G\sqcup H)$$S$$G$$G$$H$$H$$G$$H$$G$$H$$H$$G$$|G|=|H|$$S$$G$$G$$S$envia para , e o inverso dessas funções também. Portanto, toda palavra em envia para (e também para ). Assim, nenhum elemento de intercâmbios e . $G$$G$$S$$G$$G$$H$$H$$\mathrm{Aut}(G\sqcup H)$$G$$H$

Finalmente, se , em seguida, um isomorfismo proporciona um automorphism de . Assim, a ausência de elementos em para trocar e implica . O resultado segue. $G\cong H$$\phi:G\to H$$\phi\sqcup \phi^{-1}$$G\sqcup H$$\mathrm{Aut}(G\sqcup H)$$G$$H$$G\not\cong H$$\Box$

Mas agora o ponto a ser esclarecido é que ir da decisão ( ?) pesquisa (Dê-me ou um certificado que ) ainda precisa ser discutido ( e pode ser). Também de um isomorfismo para geradores de automorfismos há outro argumento (individualize os gráficos e repita o teste de isomorfismo). Então, todos disseram que você tem algumas páginas de argumento para fazer essas equivalências. Nenhum mostrará rotulagem canônica. Isso é muito mais difícil (NP-difícil, se bem me lembro). Embora NAutY e Traces lidem com muitos exemplos rapidamente.$G\cong H$$\phi:G\to H$$G\not\cong H$