Minhas árvores estão enraizadas e têm no máximo dois filhos em cada vértice. Preciso de referências que me ajudem a resolver uma ou todas as perguntas abaixo:
- Quantas classes de isomorfismo de árvores com n vértices existem?
- Quais são os algoritmos clássicos para decidir se duas árvores dadas são isomórficas?
- Existe um isomorfismo agradável (computável?) Invariável?
Obviamente, as respostas podem depender da estrutura usada para definir as árvores, mas acho que a escolha correta da estrutura faz parte da resposta que estou procurando.
algorithms
graph-theory
reference-request
combinatorics
trees
Rodrigo A. Pérez
fonte
fonte
Respostas:
Existe um algoritmo de tempo linear clássico para isomorfismo de árvore enraizada devido a Aho, Hopcroft e Ullman. O algoritmo realmente usa um isomorfismo simples invariável. Veja, por exemplo, notas de aula de Vikram Sharma . Com isso, você pode resolver o isomorfismo de árvore não raiz em tempo linear, conforme descrito, por exemplo, nos slides de Smal . Outro algoritmo clássico é devido ao Buss .
fonte