Algoritmos para gráfico poliédral (gráfico planar 3-conectado) isomorfismo?

Question

Eu coloquei alguma pesquisa sobre o tema do isomorfismo do gráfico para gráficos planários conectados, mas há uma abundância de algoritmos de diferentes restrições, complexidade teórica e frequência de uso e estou tendo problemas para encontrar um que sejacomo:

• fácil de entender
• pode ser implementado com clareza máxima
• bom desempenho prático em pequenos gráficos (até vértices nas dezenas)

É difícil saber sem entender os diferentes algoritmos se estou melhor com um dos algoritmos mais antigos e mais especializados para este problema ou os mais novos, mais gerais. Entre todos os candidatos possíveis, qual é o / uns é o melhor ajuste?

Answer 1

Eu acho que o algoritmo de Weinberg se encaixa na conta.

• fácil de entender: compute sistemas de rotação para g e h como subprodutos de um Algoritmo de teste de planaridade. Como G e H são 3-conectados, esses sistemas de rotação são isomorfos para trocar no sentido horário e no sentido anti-horário, e somente se G e H são isomórficos. Escolha um dardo (= borda com uma direção indicada) d em g e tente mapeando-o a todos os dardos e em H (e repita para a outra orientação de H). Desde que G é conectado, todos os outros dardos D 'podem ser alcançados a partir de D, compondo as duas operações do sistema de rotação para G. Aplicar as operações correspondentes e verificar se há isomorfismo.

• Clareza máxima: Além do teste de planaridade, o acima é uma página de código. Talvez você possa reutilizar o teste de planaridade de outra pessoa? Há um em impulso, por exemplo. Se não, eu ainda acho que a implementação é mais fácil do que reescrever na náutica.

• Bom desempenho prático em pequenos gráficos: Após o teste de planaridade, o algoritmo de Weinberg é basicamente duas travessuras de profundidade sincronizada para cada dardo. O tempo total de funcionamento é O (| v | ^{2 ) sem grandes constantes à espreita.}