tree - recorrido - ¿Qué significa que dos árboles binarios sean isomorfos?

recorrido de arboles

Question

¿Qué significa que dos árboles binarios sean isomorfos? He estado buscando en línea y parece que no puedo encontrar una explicación clara.

Por lo que entiendo, dos árboles son isomorfos si tienen la misma forma. Así que estoy adivinando dos árboles idénticos que pueden contener diferentes valores en los nodos.

Answer 1

Creo que su comprensión es bastante correcta. Si ignora los valores y solo mira la estructura, entonces para cada nodo en el primer árbol debe haber un nodo correspondiente en el otro árbol y viceversa.

Naturalmente, ambos árboles tendrían el mismo número de nodos. Además, podría escribir un algoritmo (super ingenuo) para confirmar este isomorfismo al intentar todas las funciones de mapeo posibles y asegurarse de que para cada nodo en el primer árbol que se asigna a un nodo en el otro, el mapeo correspondiente ocurre con el Padre y con los dos hijos. Obviamente hay algoritmos eficientes para verificar esto.

Puede beneficiarse de la lectura sobre el isomorfismo gráfico primero; Los árboles son un caso especial (y más fácil de resolver) ya que no tienen ciclos.

Answer 2

Isomórfico proviene del griego "misma forma" (como isobara es puntos con la misma presión de aire y polígono significa "muchas caras") para que su comprensión sea correcta. Pero no cometa el error de asumir que la forma en este caso es una forma física (como el árbol tiene una raíz, un nodo izquierdo y un nodo derecho; consulte a continuación, por ejemplo). Los matemáticos tienen su propio idioma, que solo a veces tiene una relación pasajera con el inglés :-)

No son solo árboles binarios. En matemáticas, dos estructuras son isomorfas si sus propiedades se conservan independientemente de su expresión (puede tener una función que traduzca de A a B y otra de B a A sin pérdida de información).

Para su caso particular, es la información en el árbol que se conserva. Por ejemplo, si esa información son los elementos ordenados {1,2,3} , entonces el árbol no tiene que tener la misma forma física en absoluto, los siguientes dos serían isomorfos:

  2      1
 / /      /
1   3      2
            /
             3

Una lista enlazada ordenada (o una matriz ordenada, para el caso) también es isomórfica para aquellos ya que, en ese caso, no se perdería información en las transformaciones entre los dos.

Si el árbol binario se usara de una manera en que el orden de clasificación fuera irrelevante (es decir, una especie de "bolsa" de contenedor), entonces la información solo sería el contenido en cualquier orden, y todo lo siguiente sería isomorfo (el segundo último) sólo una bolsa, la última es una lista):

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

Por supuesto, un árbol sin clasificar puede considerarse un desperdicio dependiendo de sus necesidades, pero eso no es relevante para esta discusión en particular.

Answer 3

Las siguientes condiciones deben cumplir dos árboles para ser isomorfos:
1. Dos árboles son isomorfos si y solo si conservan el mismo no de niveles y el mismo no de vértices en cada nivel.

2.Dos árboles son isomorfos si y solo si tienen el mismo grado de espectro.

3.Dos árboles son isomorfos si y solo si tienen el mismo grado de espectro en cada nivel.

4. El número total de descendientes de hojas de un vértice y el número de nivel de vértice son ambos árbol árbol invariante isomórfico.

En palabras simples:
Dos árboles son isomorfos si se puede obtener un árbol de otro mediante la realización de cualquier número de vueltas, es decir, intercambiando los niños de la izquierda y los de la derecha de un número de nodo.

Ejemplo de arboles isomorfos:

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