O que significa para duas árvores binárias ser isomorphic?

Question

O que significa para duas árvores binárias ser isomorphic? Eu estive procurando on-line e eu não consigo encontrar uma explicação clara.

Tanto quanto eu entendo, duas árvores são isomorfos se eles têm a mesma forma. Então, eu estou supondo duas árvores idênticas que pode conter valores diferentes nos gânglios.

Answer 1

Isomorphic vem da "mesma forma" grega (como Isobar é pontos com a mesma pressão de ar e meios de polígonos "muitos lados") para que o seu entendimento está correto. Mas não cometa o erro de assumir forma, neste caso, é uma física forma (como a árvore tem uma raiz, um nó esquerda e um nó direito, veja abaixo, por exemplo). Os matemáticos têm sua própria língua que só às vezes tem uma relação de passagem para Inglês: -)

Não são apenas árvores binárias. Em matemática, duas estruturas são isomorfos se suas propriedades são preservados, independentemente da sua expressão (você pode ter uma função que traduz A para B e outro de B para A, sem perda de informação).

Para o seu caso particular, é a informação na árvore que está preservada. Por exemplo, se essa informação é o {1,2,3} elementos classificadas, em seguida, a árvore não tem que ser o mesmo física forma em tudo - os dois seguintes seriam isomorphic:

  2      1
 / \      \
1   3      2
            \
             3

A ordenadas lista ligada (ou array ordenado, para que o assunto) também é isomorfo aos já que, nesse caso, nenhuma informação seria perdida nas transformações entre os dois.

Se a árvore binária foi utilizada de uma forma onde a ordem de classificação era irrelevante (ou seja, um "saco" espécie de container), então a informação seria apenas o conteúdo em qualquer ordem, e todos os seguintes seriam isomorphic (que segundo último apenas um saco, o último é uma lista):

  2      1           2   3                   +---+  +---+  +---+
 / \      \         /     \      +-------+   | 3 |->| 1 |->| 2 |
1   3      2       1       2     | 1,3,2 |   +---+  +---+  +---+
            \     /         \    +-------+
             3   3           1

É claro que uma árvore não ordenada pode ser considerado um pouco de um desperdício dependendo de suas necessidades, mas isso não é relevante para esta discussão particular.

Answer 2

seguintes condições devem cumprir a duas árvores para ser isomorphic:
1. Two Tree são isomorfos se e somente se eles preservam mesmo, não de níveis e mesmo, não de vértices em cada nível.

2.Two árvores são isomorfos se e somente se eles têm mesmo espectro grau.

3.Dois árvores são isomorfos se e somente se eles têm o mesmo grau de espectro em cada nível.

4. Nº total de descendente folha de um vértice e o número do nível de vértice são ambos invariante isomorphic árvore árvore.

Em palavras simples:
Duas árvores são isomorfos se uma árvore pode ser obtida a partir de outra através da realização de qualquer número de flips ou seja trocando crianças esquerda e crianças direita de um número de nó.

Exemplo de árvores isomórficas:

Ref: 1. http://www14.in.tum.de/konferenzen/ Jass03 / apresentações / eterevsky.pdf 2. http://www.geeksforgeeks.org/tree-isomorphism-problem/

Answer 3

Eu acho que sua compreensão é bastante correta. Se você ignorar os valores e basta olhar para a estrutura, em seguida, para cada nó na primeira árvore deve haver um nó correspondente na outra árvore e vice-versa.

Naturalmente, ambas as árvores teriam o mesmo número de nós. Além disso, você pode escrever um algoritmo (super-naive) para confirmar este isomorfismo, tentando todas as funções de mapeamento possíveis e assegurar que para cada nó na primeira árvore que é mapeado para um nó na outra, o mapeamento correspondente acontece com o pai e com os dois filhos. Há algoritmos obviamente eficientes para verificar isto.

Você pode se beneficiar de ler sobre gráfico isomorfismo primeiro; árvores são um especial (e mais fácil de resolver) caso uma vez que não têm ciclos.