根なし二分木

数学とコンピュータ サイエンスにおいて、根なし二分木は、各頂点に1 つまたは 3 つの隣接頂点がある 根なし木です。

自由木または根なし木は、サイクルのない接続された 無向グラフです。 1 つの隣接頂点を持つ頂点は木の葉であり、残りの頂点は木の内部ノードです。 頂点の次数は、その隣接頂点の数です。複数のノードを持つ木では、葉は次数 1 の頂点です。 根なし二分木は、すべての内部ノードの次数がちょうど 3 である自由木です。

いくつかのアプリケーションでは、根なし二分木のサブタイプを区別することが意味をなす場合があります。木の平面埋め込みは、各頂点の辺の循環順序を指定することによって固定され、平面木になります。コンピューターサイエンスでは、二分木はデータ構造として使用される場合、根付きで順序付けされていることがよくありますが、階層的クラスタリングや進化的樹形図の再構築における根なし二分木のアプリケーションでは、順序付けされていない木の方が一般的です。^[1]

さらに、すべての頂点に異なるラベルが付けられている木、葉だけにラベルが付けられている木、ノードにラベルが付けられていない木を区別することができます。n個の葉を持つ根なし二分木では、 n − 2 個の内部ノードがある ため、すべてのノードにラベルを付ける場合は 1 から 2 n − 1 までの整数の集合からラベルが付けられ、葉だけにラベルを付ける場合は 1 からn までの整数の集合からラベルが付けられます。^[1]

根無し二分木Tは、 Tの根辺eを選択し、 e の中央に新しい根ノードを配置し、結果として得られる細分化された木のすべての辺を根ノードから遠ざけることで、完全根付き二分木 (つまり、各非葉ノードが正確に 2 つの子を持つ根付き木) に変換できます。逆に、任意の完全根付き二分木は、根ノードを削除し、その 2 つの子の間のパスを単一の無向辺に置き換え、グラフ内の残りの辺の方向を抑制することで、非根付き二分木に変換できます。このため、n 個の葉を持つ完全根付き二分木の数は、 n 個の葉を持つ非根付き二分木の数のちょうど 2 n  −3 倍になります。^[1]

オブジェクトのコレクションの階層的クラスタリングは、 2 つのセットが交差しないオブジェクトのセットの最大 ファミリとして形式化できます。つまり、ファミリ内の2 つのセットSとTごとに、 SとT は互いに素であるか、一方が他方のサブセットであり、このプロパティを維持しながらファミリにセットを追加することはできないということです。T が根なし二分木の場合、その葉の階層的クラスタリングが定義されます。T 内の各エッジ ( u 、 v ) に対して、vよりもuに近い葉で構成されるクラスターがあり、これらのセットは空セットおよびすべての葉のセットとともに、最大の非交差ファミリを形成します。逆に、n要素のセット上の任意の最大の非交差ファミリから、ファミリ内の素なセットの各トリプル ( A、B、C )をノードとして持つ一意の根なし二分木を形成できます。これらのトリプルは、すべての要素をカバーします。^[2]

進化論の単純な形式によれば、生命の歴史は系統樹として要約することができ、各ノードは種を表し、葉は現在存在する種を表し、エッジは種間の祖先と子孫の関係を表します。このツリーは祖先から子孫への自然な方向と種の共通祖先に根があるため、根付きツリーです。ただし、バイナリツリーを再構築する一部の方法では、このツリーのノードとエッジのみを再構築できますが、それらの方向は再構築できません。

たとえば、最大節約法などの分岐論的手法では、種の特徴を記述するバイナリ属性のセットをデータとして使用します。これらの手法では、特定の種を葉として、内部ノードにも特徴がラベル付けされたツリーを探し、ツリー内のエッジの 2 つのエンドポイントの 1 つにのみ特徴が存在する回数を最小化しようとします。理想的には、各特徴には、このようなエッジが 1 つだけある必要があります。ツリーのルートを変更しても、このエッジの違いの数は変わりません。そのため、節約法に基づく手法ではツリーのルートの位置を決定できず、ルートのないツリー、多くの場合はルートのないバイナリ ツリーが生成されます。^[3]

根無し二分木は、4つの葉を持つ種ごとに、その4つの種の進化を記述する根無し二分木を指定するカルテットデータに基づいて進化木を推測する方法や、カルテット距離を使用して木間の距離を測定する方法によっても生成されます。^[4]

根無し二分木は、グラフの枝分かれを定義するためにも使われます。これは、葉がグラフの辺を表す根無し二分木を形成することによって行われます。つまり、枝分かれはグラフの辺の階層的クラスタリングと見なすことができます。枝分かれとそれに関連する数値である枝幅は、木幅と密接に関連しており、グラフ上の効率的な動的計画法アルゴリズムの基礎を形成します。 ^[5]

階層的クラスタリングへの応用のため、根なし二分木における最も自然なグラフ列挙問題は、 n個のラベル付き葉とラベルなし内部ノードを持つ木の数を数えることである。n 個のラベル付き葉を持つ根なし二分木は、 n − 1 個のラベル付き葉を持つ根なし二分木のいずれかの辺の中央にある新しいノードにn番目の葉を接続することによって形成できる。n 番目のノードを接続できる 辺は2 n − 5 個 あるため、 n個の葉を持つ木の数はn  − 1 個の葉を持つ木の数の 2 n − 5 倍になる。したがって、 n 個のラベル付き葉 を持つ木の数は、二重階乗である。

${\displaystyle (2n-5)!!={\frac {(2n-4)!}{(n-2)!2^{n-2}}}.}$^[6]

2、3、4、5、…のラベルが付いた葉の木の数は

1、1、3、15、105、945、10395、135135、2027025、34459425、...（OEISの配列A001147）。

固定された根なし二分木 (UBT) T 上の葉から葉へのパス長は、T 内の特定の葉を別の葉に接続する一意のパスに属するエッジの数をエンコードします。たとえば、右の図に示す UBT を参照すると、葉 1 と 2 の間のパス長は 2 に等しく、葉 1 と 3 の間のパス長は 3 に等しくなります。固定された UBT T 上の特定の葉からのパス長シーケンスは、特定の葉から残りのすべての葉までのパスの長さをエンコードします。たとえば、右の図に示す UBT を参照すると、葉 1 からのパス長シーケンスは です。T の葉に関連付けられたパス長シーケンスの集合は、通常、 T のパス長シーケンス コレクションと呼ばれます^[7] 。 ${\displaystyle p_{1,2}}$${\displaystyle p_{1,3}}$${\displaystyle p_{1}=(p_{1,2},p_{1,3},p_{1,4})=(2,3,3)}$

ダニエル・カタンツァーロ、ラファエレ・ペセンティ、ローレンス・ウォルジーは^[7]、 n個の葉を持つUBTをエンコードするパス長シーケンスコレクションが特定の等式を満たさなければならないことを 示した。

• ${\displaystyle p_{i,i}=0}$全ての${\displaystyle i\in [1,n]}$
• ${\displaystyle p_{i,j}=p_{j,i}}$全ての${\displaystyle i,j\in [1,n]:i\neq j}$
• ${\displaystyle p_{i,j}\leq p_{i,k}+p_{k,j}}$全ての${\displaystyle i,j,k\in [1,n]:i\neq j\neq k}$
• ${\displaystyle \sum _{j=1}^{n}1/2^{p_{i,j}}=1/2}$（クラフト・マクミラン不等式の応用である）${\displaystyle i\in [1,n]}$
• ${\displaystyle \sum _{i=1}^{n}\sum _{j=1}^{n}p_{i,j}/2^{p_{i,j}}=2n-3}$系統多様体とも呼ばれる。^[7]

これらの等式は、パス長コレクションがn個の葉を持つUBTをエンコードするために必要かつ独立であることが証明されています。^[7]これらが十分であるかどうかは現在不明です。

根無し二分木は、自由二分木^[8] 、三次木^{[9] 、} 三分木^[5]、根無し三分木^[10]とも呼ばれています。しかし、「自由二分木」という名前は、次数が2のノードを持つ可能性のある根無し木^[11]や、順序付けられていない子を持つ根有り二分木^{[12]にも適用されており、「三分木」という名前は}、ノードごとに3つの子を持つ根有り木を意味するためによく使用されています。

• Balding, DJ; Bishop, Martin J.; Cannings, Christopher (2007)、統計遺伝学ハンドブック、第 1 巻 (第 3 版)、Wiley-Interscience、p. 502、ISBN 978-0-470-05830-5。
• チリブラシ、ルディ。ヴィタニー、ポール MB (2006)。 「階層的クラスタリングのための新しいカルテットツリーヒューリスティック」。arXiv : cs/0606048。。
• Czumaj, Artur; Gibbons, Alan (1996)、「ガスリーの問題: 新しい同値性と急速な縮小」、理論計算機科学、154 (1): 3–22、doi : 10.1016/0304-3975(95)00126-3。
• エップスタイン、デイビッド（2009）、「ツリー内のスクエアパンツ：サブツリークラスタリングと双曲パンツ分解の合計」、ACM Transactions on Algorithms、5（3）：1–24、arXiv：cs.CG / 0604034、doi：10.1145 / 1541885.1541890、S2CID  2434。
• Exoo, Geoffrey (1996)、「内周 14、15、16 の小さな立方グラフを作成するための簡単な方法」(PDF)、Electronic Journal of Combinatorics、3 (1): R30、doi : 10.37236/1254。
• ファーナス、ジョージ W. (1984)、「ランダムなバイナリ順序なしツリーの生成」、分類ジャーナル、1 (1): 187–233、doi :10.1007/BF01890123、S2CID  121121529。
• Harary, Frank ; Palmer, EM; Robinson, RW (1992)、「与えられた高さを受け入れる自由二分木のカウント」(PDF)、Journal of Combinatorics, Information, and System Sciences、17 : 175–181。
• ヘンディ、マイケル D.; ペニー、デイビッド (1989)、「進化樹の定量的研究のための枠組み」、系統生物学、38 (4): 297–309、doi :10.2307/2992396、JSTOR  2992396
• Przytycka, Teresa M. ; Larmore, Lawrence L. (1994)、「最適アルファベット木問題の再考」、Proc. 21st International Colloquium on Automata, Languages and Programming (ICALP '94)、Lecture Notes in Computer Science、vol. 820、Springer-Verlag、pp. 251–262、doi :10.1007/3-540-58201-0_73。
• ロバートソン、ニール;シーモア、ポール D. (1991)、「グラフマイナー。X.ツリー分解の障害」、組み合わせ理論ジャーナル、52 (2): 153–190、doi : 10.1016/0095-8956(91)90061-N。
• セントジョン、キャサリン;ウォーノウ、タンディ;モレット、バーナード ME ; ヴォータード、リサ (2003)、「系統分類法のパフォーマンス研究: (重み付けなし) カルテット法と近隣結合」(PDF)、アルゴリズムジャーナル、48 (1): 173–193、doi :10.1016/S0196-6774(03)00049-X、S2CID  5550338。