ツリー（グラフ理論）

木々
6 つの頂点と 5 つの辺を持つラベル付きツリー。
頂点	ヴ
エッジ	v  − 1
彩度数	2 （v > 1の場合）
グラフとパラメータの表

グラフ理論では、木は、任意の2つの頂点が正確に1つのパスで接続されている無向グラフ、またはそれと同等に接続された非巡回無向グラフです。^[1]森は、任意の2つの頂点が最大で1つのパスで接続されている無向グラフ、またはそれと同等の非巡回無向グラフ、またはそれと同等のツリーの非結合です。^[2]

有向木^[3]、指向木^[4]、[5] 、ポリツリー^[6]、または単連結ネットワーク^{[7]は、基となる無向グラフが木である}有向非巡回グラフ（DAG）です。ポリフォレスト（または有向フォレスト、指向フォレスト）は、基となる無向グラフがフォレストである有向非巡回グラフです。

コンピュータサイエンスで木と呼ばれるさまざまな種類のデータ構造は、グラフ理論における木である基礎グラフを持っていますが、そのようなデータ構造は一般的に根付き木です。根付き木は有向である場合があり、有向根付き木と呼ばれます^{[8] [9]}すべての辺がルートから遠ざかるようにするか（その場合は樹状突起^{[3] [10]}またはアウトツリー^{[11] [12]}と呼ばれます）、すべての辺がルートに向くようにするか（その場合は反樹状突起^[13]またはインツリーと呼ばれます）。^{[11] [14]}根付き木自体は、一部の著者によって有向グラフとして定義されています。^{[15] [16] [17]}根付きフォレストは、根付き木の非結合和集合です。根付きフォレストは、有向根付きフォレストと呼ばれる有向型にすることができ、各根付きツリーのすべてのエッジがルートから遠ざかるようにするか (その場合は分岐フォレストまたはアウトフォレストと呼ばれます)、各根付きツリーのすべてのエッジがルートに近づくようにするか (その場合は反分岐フォレストまたはインフォレストと呼ばれます) のいずれかになります。

ツリーという用語は1857年にイギリスの数学者アーサー・ケイリーによって造られた。^[18]

木とは、以下の同等の条件のいずれかを満たす 無向グラフGです。

• G は連結されており、非巡回的です（サイクルが含まれていません）。
• G は非巡回であり、Gに任意の辺が追加されると単純巡回が形成されます。
• Gは接続されていますが、Gから 1 つのエッジが削除されると切断されます。
• Gは連結であり、完全グラフ K _{3 は}Gのマイナーではありません。
• G内の任意の 2 つの頂点は、一意の単純なパスによって接続できます。

Gに有限個の頂点、たとえばn個がある場合、上記のステートメントは次の条件のいずれとも同等になります。

• Gは連結しており、n − 1 個の辺を持ちます。
• Gは連結であり、Gのすべてのサブグラフには、0 個または 1 個の接続辺を持つ頂点が少なくとも 1 つ含まれます。(つまり、G は連結であり、1 退化しています。)
• Gには単純なサイクルはなく、n − 1個の辺があります。

グラフ理論の他の部分と同様に、ゼロ次グラフ(頂点のないグラフ) は一般に木とは見なされません。グラフとしては空連結 (任意の 2 つの頂点をパスで連結可能) ですが、空でない木とは異なり、代数位相では0 連結(または (-1) 連結) ではなく、「頂点が辺より 1 つ多い」という関係に違反します。ただし、ゼロの木からなる森と見なすことができます。

内部頂点（または内側頂点）は、少なくとも次数が2の頂点です。同様に、外部頂点（または外側頂点、終端頂点、葉）は、次数が1の頂点です。木の枝頂点は、少なくとも次数が3の頂点です。^[19]

既約木（または級数縮小木）は、次数2の頂点が存在しない木である（OEISのシーケンスA000014に列挙されている）。^[20]

フォレストは、無向非巡回グラフ、または同等に、ツリーの非結合和集合です。当然のことながら、フォレストの各接続コンポーネントはツリーです。特殊なケースとして、順序ゼロのグラフ (ツリーが 0 本で構成されるフォレスト)、単一のツリー、およびエッジのないグラフは、フォレストの例です。すべてのツリーについてV − E = 1であるため、頂点の総数とエッジの総数の差を減算することで、フォレスト内にあるツリーの数を簡単に数えることができます。V − E =フォレスト内のツリーの数。

ポリツリー^[6]（または有向木^[3]、有向木^{[4] [5]}、単連結ネットワーク^[7]）は、有向非巡回グラフ（DAG）であり、その基礎となる無向グラフは木である。言い換えれば、有向辺を無向辺に置き換えると、連結かつ非巡回である無向グラフが得られる。

一部の著者は、「有向木」という語句を、すべての辺が特定の頂点に向かっている場合、またはすべての辺が特定の頂点から離れて向いている場合（樹状突起を参照）に限定している。^{[21] [22] [23]}

ポリフォレスト(または有向フォレスト、または指向フォレスト) は、基になる無向グラフがフォレストである有向非巡回グラフです。言い換えると、有向エッジを無向エッジに置き換えると、非巡回である無向グラフが得られます。

有向木と同様に、一部の著者は「有向フォレスト」という語句を、各接続コンポーネントのエッジがすべて特定の頂点に向けられている場合、またはすべて特定の頂点から遠ざかっている場合（分岐を参照）に限定しています。^[22]

根付き木とは、1つの頂点が根に指定されている木である。^[24]根付き木の辺には、根から離れる方向か根に近づく方向のどちらかの自然な向きを割り当てることができ、その場合、構造は有向根付き木となる。有向根付き木が根から離れる方向を持つ場合、それは樹状突起^[3]または外木と呼ばれ、^[11]根に向かう方向を持つ場合、それは反樹状突起または内木と呼ばれる。^[11]木順序は、根からvへの唯一のパスがu を通過する場合のみ、 u < vである木の頂点上の部分順序である。あるグラフGのサブグラフである根付き木Tは、 G内のすべてのTパスの端がこの木順序で比較可能な場合、通常の木である(Diestel 2005、p. 15)。ルート付きツリーは、各頂点の隣接ノードの順序付けなどの追加の構造を持つことが多く、コンピューター サイエンスにおける重要なデータ構造です。ツリー データ構造を参照してください。

通常、木にはルートがありますが、指定されたルートを持たない木は自由木と呼ばれます。

ラベル付きツリーは、各頂点に一意のラベルが付けられたツリーです。n頂点 ( nは非負の整数) のラベル付きツリーの頂点には、通常、ラベル1、2、…、nが付けられます。再帰ツリーは、頂点ラベルがツリーの順序を尊重するラベル付きルート付きツリーです (つまり、2 つの頂点uとvに対してu < vの場合、 uのラベルはvのラベルよりも小さくなります)。

根付き木では、頂点vの親は、ルートへのパス上でvに接続されている頂点です。ルートに親がない場合は別ですが、すべての頂点には一意の親があります。 ^[24]頂点vの子は、 vが親である頂点です。 ^[24]頂点 v の先祖は、vの親であるか、（再帰的に） vの親の先祖である頂点です。頂点vの子孫は、 vの子であるか、（再帰的に） vの子の子孫である頂点です。頂点vの兄弟は、 vと親を共有する木上の他の頂点です。^[24]葉は子を持たない頂点です。^[24]内部頂点は葉ではない頂点です。^[24]

根付きツリーの頂点の高さは、その頂点から葉までの最長の下向きのパスの長さです。ツリーの高さはルートの高さです。頂点の深さは、そのルートへのパス (ルート パス) の長さです。ツリーの深さは、任意の頂点の最大深さです。深さは、さまざまな自己バランス ツリー、特にAVL ツリーの操作で一般的に必要になります。ルートの深さは 0、葉の高さは 0、頂点が 1 つだけのツリー (つまりルートと葉の両方) の深さと高さは 0 です。慣例的に、空のツリー (頂点がないツリー (許可されている場合)) の深さと高さは -1 です。

k分木（非負の整数k）は、各頂点が最大でk個の子を持つ根付き木です。^[25] 2分木は二分木と呼ばれることが多く、3分木は三分木と呼ばれることもあります。

順序付き木（または平面木または位置木^[26]）は、各頂点の子に対して順序が指定されている根付き木です。^{[24] [27]}これは「平面木」と呼ばれます。子の順序は、ルートを最上位に置き、各頂点の子をその頂点より下位に置く、平面への木の埋め込みと同等であるためです。平面への根付き木の埋め込みが与えられた場合、子の方向を固定すると（たとえば左から右）、埋め込みによって子の順序が与えられます。逆に、順序付き木が与えられ、慣例的にルートを最上位に描くと、順序付き木の子頂点は左から右に描くことができ、本質的に一意の平面埋め込みが得られます。

• すべての木は二部グラフです。グラフが二部グラフであるのは、奇数の長さのサイクルを含まない場合のみです。木にはサイクルがまったく含まれていないため、二部グラフです。
• 頂点が可算な数だけある木はすべて平面グラフです。
• 連結グラフGには全域木が存在する。全域木とは、 Gのすべての頂点を含み、その辺がGの辺である木である。連結有限グラフに存在するより具体的な全域木の種類には、深さ優先探索木と幅優先探索木がある。深さ優先探索木の存在を一般化すると、頂点が可算な数だけある連結グラフには、トレモー木が存在する。^[28]ただし、可算でない順序のグラフには、そのような木が存在しない。^[29]
• n頂点（n > 1 ）を持つすべての有限木には、少なくとも 2 つの終端頂点（葉）があります。この最小の葉の数はパス グラフの特徴です。最大数n − 1は、スター グラフでのみ達成されます。葉の数は、少なくとも最大頂点次数です。
• ツリー内の任意の 3 つの頂点について、それらの間の 3 つのパスには、ちょうど 1 つの頂点が共通しています。より一般的には、3 つの頂点間の 3 つの最短パスに属するグラフ内の頂点は、これらの頂点の中央値と呼ばれます。ツリー内の 3 つの頂点ごとに一意の中央値があるため、すべてのツリーは中央値グラフです。
• すべてのツリーには、1 つの頂点または 2 つの隣接する頂点で構成される中心があります。中心は、すべての最長パスの中央の頂点または中央の 2 つの頂点です。同様に、すべてのn頂点ツリーには、1 つの頂点または 2 つの隣接する頂点で構成される重心があります。最初のケースでは、頂点を削除すると、ツリーはn /2未満の頂点のサブツリーに分割されます。2 番目のケースでは、2 つの重心頂点間のエッジを削除すると、ツリーはちょうどn /2 の頂点の 2 つのサブツリーに分割されます。
• 木の最大クリークはまさに​​そのエッジであり、木のクラスにはクリークがほとんどないことを意味します。

ケーリーの公式は、 n個のラベル付き頂点にn ^{n −2}本のツリーが存在することを述べている。古典的な証明ではプリューファー列が使用され、これは当然より強い結果を示している。頂点1、2、…、nの次数がそれぞれd ₁、d ₂、…、d _nのツリーの数は、多項式係数である。

${\displaystyle {n-2 \choose d_{1}-1,d_{2}-1,\ldots ,d_{n}-1}.}$

より一般的な問題は、無向グラフ内の全域木を数えることです。これは、行列木定理によって解決されます。(ケイリーの公式は、完全グラフ内の全域木の特殊なケースです。) サイズに関係なくすべての部分木を数える同様の問題は、一般的なケースでは#P 完全です(Jerrum (1994))。

ラベルのない自由木の数を数えることはより難しい問題である。グラフ同型性までのn頂点の木の数t(n)に対する閉じた公式は知られていない。t ( n )の最初のいくつかの値は

1、1、1、1、2、3、6、11、23、47、106、235、551、1301、3159、…（OEISのシーケンスA000055）。

オッター（1948）は漸近推定値を証明した。

${\displaystyle t(n)\sim C\alpha ^{n}n^{-5/2}\quad {\text{as }}n\to \infty ,}$

ここで、C ≈ 0.534949606...、α ≈ 2.95576528565... （ OEISの配列A051491）。ここで、~記号は

${\displaystyle \lim _{n\to \infty}{\frac {t(n)}{C\alpha ^{n}n^{-5/2}}}=1.}$

これは、 n個の頂点を持つラベルなし根付き木の数r ( n )に対する漸近推定の結果である。

${\displaystyle r(n)\sim D\alpha ^{n}n^{-3/2}\quad {\text{as }}n\to \infty ,}$

D ≈ 0.43992401257...であり、αは上記と同じです（Knuth（1997）、第2.3.4.4章およびFlajolet＆Sedgewick（2009）、第VII.5章、475ページを参照）。

r ( n )の最初のいくつかの値は^[30]

1、1、2、4、9、20、48、115、286、719、1842、4766、12486、32973、…（OEISの配列A000081）。

• パスグラフ（または線形グラフ）は、一直線に並んだ n 個の頂点で構成され、頂点 i と i + 1 は、i = 1 、 … 、 n – 1に対して辺で接続されます。
• 星型ツリーは、ルートと呼ばれる中心の頂点と、それに接続された複数のパス グラフで構成されます。より正式には、ツリーに次数が 2 より大きい頂点が 1 つだけある場合、そのツリーは星型です。
• スターツリーは、1 つの内部頂点 (およびn – 1 個の葉)で構成されるツリーです。言い換えると、順序nのスター ツリーは、可能な限り多くの葉を持つ順序nのツリーです。
• キャタピラー ツリーは、すべての頂点が中心パス サブグラフから距離 1 以内にあるツリーです。
• ロブスター ツリーは、すべての頂点が中心パス サブグラフから距離 2 以内にあるツリーです。
• 次数dの正規木は、各頂点にd個の辺を持つ無限木です。これらは、自由群のケーリー グラフとして、また、ティッツ ビルディングの理論で発生します。統計力学では、これらはベーテ格子として知られています。

• 決定木
• ハイパーツリー
• マルチツリー
• 擬似森林
• ツリー構造（一般）
• ツリー（データ構造）
• 根なし二分木

• ベンダー、エドワード A.、ウィリアムソン、S. ギル (2010)、リスト、決定、グラフ。確率入門付き
• Dasgupta, Sanjoy (1999)、「ポリツリーの学習」、第 15 回人工知能における不確実性に関する会議 (UAI 1999)、スウェーデン、ストックホルム、1999 年 7 月～8 月(PDF)、pp. 134～141。
• Deo, Narsingh (1974)、「グラフ理論と工学およびコンピュータサイエンスへの応用」(PDF)、ニュージャージー州エングルウッド: Prentice-Hall、ISBN 0-13-363473-6、 2019年5月17日にオリジナルからアーカイブ（PDF）
• Harary, Frank ; Prins, Geert (1959)、「同相的に既約な木の数、およびその他の種」、Acta Mathematica、101 (1–2): 141–162、doi : 10.1007/BF02559543、ISSN  0001-5962
• ハラリー、フランク; サムナー、デイビッド (1980)、「有向木の二色数」、組合せ論、情報、システム科学ジャーナル、5 (3): 184–187、MR  0603363。
• Kim, Jin H.; Pearl, Judea (1983)、「推論エンジンにおける因果推論と診断推論の計算モデル」、Proc. 8th International Joint Conference on Artificial Intelligence (IJCAI 1983)、カールスルーエ、ドイツ、1983 年 8 月(PDF)、pp. 190–193。
• Li, Gang (1996)、「根付き木と自由木の生成」、修士論文、コンピュータサイエンス学部、ビクトリア大学、ブリティッシュコロンビア州、カナダ(PDF)、p. 9。
• シミオン、ロディカ(1991)、「1因子の木と有向木」、離散数学、88 (1): 93–104、doi : 10.1016/0012-365X(91)90061-6、MR  1099270。

ウィキメディア・コモンズには、ツリー (グラフ理論)に関連するメディアがあります。

• ディーステル、ラインハルト（2005）、グラフ理論（第3版）、ベルリン、ニューヨーク：シュプリンガー・フェアラーク、ISBN 978-3-540-26183-4。
• フラジョレ、フィリップ、セジウィック、ロバート（2009）、解析的組合せ論、ケンブリッジ大学出版局、ISBN 978-0-521-89806-5
• 「木」、数学百科事典、EMS Press、2001 [1994]
• Knuth, Donald E. (1997 年 11 月 14 日)、The Art of Computer Programming Volume 1: Fundamental Algorithms (第 3 版)、Addison-Wesley Professional
• ジェラム、マーク (1994)、「グラフ内の木のカウントは #P 完全である」、情報処理レター、51 (3): 111–116、doi :10.1016/0020-0190(94)00085-9、ISSN  0020-0190。
• オッター、リチャード (1948)、「木の数」、数学年報、第 2 シリーズ、49 (3): 583–599、doi :10.2307/1969046、JSTOR  1969046。