2 つの二分木が同型であるとはどういう意味ですか?

Question

2 つの二分木が同型であるとはどういう意味ですか?ネットで調べてみたのですが、明確な説明が見つからないようです。

私の理解する限り、2 本の木は同じ形であれば同形です。したがって、ノードに異なる値を含むことができる 2 つの同一のツリーがあると思います。

Answer 1

同形のでご理解が正しいか（「多面的」とは等圧線のように同じ空気圧とポリゴンとポイントです）ギリシャ語の「同じ形」から来ています。しかし、この場合の形状を想定しての間違いをしないの物理の形状（木のように1つのルート、1つの左ノードおよび1つの右のノードがあり、例えば以下を参照）です。数学は、が時々が英語に通過関係を負担する独自の言語を持っている： - ）

それはちょうどバイナリツリーではありません。そのプロパティは、（あなたが情報の損失なしにBからAにBと別の変換機能を持つことができます）にかかわらず、その発現の保存されている場合は数学では、2つの構造が同型でます。

あなたの特定のケースでは、それは保存のツリー内の情報です。その情報がソートされた要素の{1,2,3}がある場合たとえば、その後、ツリーは、は物理が全く形状が同じである必要はありません - 次の二つが同型になります：

  2      1
 / \      \
1   3      2
            \
             3

（そのことについて、またはソートされた配列）

Aソートされたリンクリストもあるため、その場合には、何の情報が2つの間の変換で失われないであろうものと同型である。

二分木は、全て同形であろう次の（そのソート順（すなわち、容器の「袋」ソート）は、その情報は、ちょうど任意の順序でコンテンツをあろう無関係であった方法で使用し、場合二最後のものはただのバッグですが、最後はリストです）：

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

もちろん、ソートされていない木は、ニーズに応じて、廃棄物のビットであるとみなすことができるが、それは、この特定の議論に関連していないのです。

Answer 2

2 つのツリーが同型であるためには、次の条件を満たす必要があります。
1.2 つのツリーは、同じレベル数と各レベルの同じ数の頂点を保持する場合に限り、同形です。

2. 2 つの木が同型であるのは、それらが同じ次数スペクトルを持っている場合に限ります。

3. 2 つの木は、各レベルで同じ次数のスペクトルを持っている場合に限り、同型です。

4. 頂点の葉の子孫の総数と頂点のレベル数は両方ともツリー同型不変です。

簡単な言葉で:
任意の数の反転、つまり多数のノードの左の子と右の子を交換することによって一方のツリーを他方のツリーから取得できる場合、2 つのツリーは同型です。

同型ツリーの例:

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

Answer 3

私はあなたの理解はかなり正しいと思います。あなたが値を無視して、構造を見れば、最初のツリー内のすべてのノードに対して、対応する他のツリー内のノードおよびその逆が存在する必要があります。

当然、両方のツリーは、ノードの数が同じであろう。 また、あなたはすべての可能なマッピング機能をしようとすると、他の中のノードにマッピングされる最初のツリー内のすべてのノードに対して、対応するマッピングがで起こることを確実にすることによって、この同型を確認するために、（超ナイーブ）アルゴリズムを書くことができます親と2人の子供を持ちます。 これをチェックするための効率的なアルゴリズムが明らかにあります。

あなたは、まずグラフ同型について読んでから利益を得ることができます。彼らはサイクルを持っていないので、木は特別な（と解決しやすい）場合があります。