19

2 つの二分木が同形であるとはどういう意味ですか? 私はオンラインで探していましたが、明確な説明が見つからないようです。

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

4

3 に答える 3

40

同形はギリシャ語の「同じ形」に由来するため（アイソバーは同じ気圧の点であり、ポリゴンは「多面」を意味するように）、あなたの理解は正しいです。ただし、この場合の形状が物理的な形状であると仮定するのを間違えないでください(ツリーには 1 つのルート、1 つの左ノード、および 1 つの右ノードがあるように、たとえば以下を参照してください)。数学者には独自の言語があり、英語とは一時的な関係しか持たないことがあります :-)

二分木だけではありません。数学では、式に関係なくプロパティが保持されている場合、2 つの構造は同形です (情報を失うことなく、A を B に、別の B を A に変換する関数を使用できます)。

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

  2      1
 / \      \
1   3      2
            \
             3

並べ替えられた連結リスト (または並べ替えられた配列) もそれらと同形です。その場合、2 つの間の変換で情報が失われないためです。

二分木が、ソート順序が無関係な方法で使用された場合 (つまり、コンテナの「バッグ」ソート)、情報は任意の順序の内容であり、以下のすべては同形 (最後から 2 番目のもの) になります。ちょうどバッグ、最後はリストです):

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

もちろん、ソートされていないツリーは、ニーズによっては少し無駄であると見なされる場合がありますが、それはこの特定の議論には関係ありません。

于 2009-04-13T00:23:32.483 に答える
5

2 つのツリーが同形であるためには、次の条件を満たす必要があり
ます。

2. 2 つのツリーが同形であるのは、それらが同じ次数スペクトルを持っている場合のみです。

3.2 つのツリーは、各レベルで同じ次数のスペクトルを持つ場合にのみ同形です。

  1. 頂点のリーフ子孫の総数と頂点のレベル数は、どちらもツリー ツリー同形不変量です。

IN 簡単な言葉:
任意の数のフリップを実行することによって、1 つのツリーが他のツリーから取得できる場合、つまり、多数のノードの左の子と右の子を交換することができる場合、2 つのツリーは同形です。

同型木の例: 同型木

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

于 2014-09-21T12:12:48.910 に答える
1

あなたの理解はおおむね正しいと思います。値を無視して構造だけを見ると、最初のツリーのすべてのノードに対して、他のツリーに対応するノードが存在する必要があり、その逆も同様です。

当然、両方のツリーのノード数は同じになります。さらに、可能なすべてのマッピング関数を試行し、最初のツリーのすべてのノードが他のノードにマッピングされることを確認することで、この同型性を確認する (非常に単純な) アルゴリズムを作成できます。親と 2 人の子供と。これをチェックするための明らかに効率的なアルゴリズムがあります。

最初にグラフ同型について読むと役立つ場合があります。木は循環を持たないため、特別な (そして解決しやすい) ケースです。

于 2009-04-12T23:14:30.310 に答える