Qu'est-ce que cela signifie pour deux arbres binaires isomorphes?

Question

Qu'est-ce que cela signifie pour deux arbres binaires à isomorphe? Je cherchais semble en ligne et je ne peux pas trouver une explication claire.

Pour autant que je comprends, deux arbres sont isomorphes si elles ont la même forme. Donc, je devine deux arbres identiques qui peuvent contenir des valeurs différentes dans les noeuds.

Answer 1

Isomorphic vient du grec « même forme » (comme isobare est des points avec la même pression d'air et des moyens polygone « plusieurs côtés ») afin que votre interprétation est correcte. Mais ne faites pas l'erreur de supposer que la forme dans ce cas est une forme physique (comme l'arbre a une racine, un nœud gauche et un noeud à droite, voir ci-dessous par exemple). Mathématiciens ont leur propre langue qui ne parfois porte une relation de passage à l'anglais: -)

Il n'y a pas que les arbres binaires. En mathématiques, deux structures sont isomorphes si leurs propriétés sont conservées indépendamment de leur expression (vous pouvez avoir une fonction qui se traduit par A à B et une autre de B à A, sans perte d'information).

Pour votre cas particulier, il est l'information dans l'arbre qui est conservé. Par exemple, si ces informations sont les éléments triés {1,2,3}, l'arbre ne doit pas être le même physique forme du tout - les deux seraient isomorphe suivants:

  2      1
 / \      \
1   3      2
            \
             3

Une liste chaînée trié (ou tableau trié, pour cette matière) est aussi isomorphe à ceux puisque, dans ce cas, aucune information serait perdue dans les transformations entre les deux.

Si l'arbre binaire a été utilisé d'une manière où l'ordre de tri était hors de propos (c.-à-une sorte de « sac » du conteneur), l'information serait tout le contenu dans un ordre quelconque, et tous les éléments suivants serait isomorphe (que deuxième dernier est juste un sac, la dernière est une liste):

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

Bien sûr, un arbre peut être considéré non triés être un peu d'un déchet en fonction de vos besoins, mais ce n'est pas pertinent pour cette discussion.

Answer 2

Les conditions suivantes doivent remplir deux arbres à isomorphe:
1. Deux arbres sont isomorphes si et seulement si elles conservent même pas de niveaux et même pas de sommets dans chaque niveau.

2.Two arbres sont isomorphes si et seulement si elles ont le même spectre de degré.

3.Deux arbres sont isomorphes si et seulement si elles ont le même degré de spectre à chaque niveau.

4. Nombre total de descendant de la feuille d'un sommet et le nombre de niveau de sommet sont à la fois arbre arbre isomorphe invariant.

mots simples: Deux arbres sont isomorphes si un arbre peut être obtenu à partir d'autres en effectuant un certain nombre de flips i.e. échange pour enfants gauche et droit pour enfants d'un certain nombre de noeud.

Exemple d'arbres isomorphes:

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

Answer 3

Je pense que votre compréhension est à peu près correcte. Si vous ignorez les valeurs et regardez juste la structure, puis pour chaque noeud dans le premier arbre, il doit y avoir un noeud correspondant dans l'autre arbre et vice versa.

Bien sûr, les deux arbres auraient le même nombre de nœuds. De plus, vous pouvez écrire un algorithme (super-naïve) pour confirmer cette isomorphisme en essayant toutes les fonctions cartographiques possibles et veiller à ce que pour chaque noeud dans le premier arbre qui sera reliée à un noeud dans l'autre, le mappage correspondant se produit avec la parents et les deux enfants. Il existe des algorithmes efficaces pour vérifier évidemment pour cela.

Vous pouvez profiter de la lecture sur graphique premier isomorphisme; Les arbres sont un cas particulier (et plus facile à résoudre), car ils ne disposent pas de cycles.