木構造（グラフ理論）

グラフ理論において、木とは、異なる頂点の任意のペアがちょうど 1 つのパスで接続されている無向グラフ、または同等に、連結された非巡回無向グラフである。^[¹^]森とは、任意の 2 つの頂点が最大 1 つのパスで接続されている無向グラフ、または同等に、非巡回無向グラフ、または同等に、木の非交和である。^[²^]

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

コンピュータサイエンスでツリーと呼ばれるさまざまなデータ構造は、グラフ理論ではツリーである基となるグラフを持ちますが、そのようなデータ構造は一般的にルート付きツリーです。ルート付きツリーは、有向ルート付きツリーと呼ばれる有向ルート付きツリー^[⁸^]^[⁹^]、またはすべてのエッジがルートから離れる方向を向いている場合（この場合、アーボレッセンス^[³^]^[¹⁰^]またはアウトツリー^[¹¹^]^[¹²^]と呼ばれます）、またはすべてのエッジがルートに向かう方向を向いている場合（この場合、アンチアーボレッセンス^[¹³^]またはインツリー^[¹¹^]^[¹⁴^]と呼ばれます）のいずれかです。ルート付きツリー自体は、一部の著者によって有向グラフとして定義されています。^[¹⁵^]^[¹⁶^]^[¹⁷^]ルート付きフォレストは、ルート付きツリーの非交和です。根付き林は、方向性を持たせる場合と、方向性を持たせる場合があり、方向性を持たせる場合では、各根付き木の根からすべての縁が離れる方向を向いている場合（この場合、分岐林または外向き林と呼ばれる）、または各根付き木の根に向かってすべての縁が向いている場合（この場合、反分岐林または内向き林と呼ばれる）がある。

「木」という用語は、1857年にイギリスの数学者アーサー・ケイリーによって造語された。^{[ 18 ]}

定義

木

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

$G$ は連結であり、非巡回的である（サイクルを含まない）。
$Gは非巡回グラフであり、$ $Gに$ 辺を追加すると単純サイクルが形成される。
$G$ は連結しているが、 $G$ からいずれかの辺が1つでも取り除かれると、連結が切断される。
$G$ は連結であり、完全グラフ $K3 は$ $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に列挙されている）。^[²⁰^]

森

森は、無向非巡回グラフ、または同等に木の非交和です。当然のことながら、森の各連結成分は木です。特殊なケースとして、次数ゼロのグラフ（木がゼロ個で構成される森）、単一の木、および辺のないグラフは森の例です。すべての木について $V - E = 1であるため、総頂点数と総辺数の差を引くことで、森$ $に$ 含まれる木の数を簡単に数えることができます。V $-$ $E$ $=$ 森に含まれる木の数。

ポリツリー

ポリツリー^[⁶^]（または有向木^[³^]、方向付き木^[⁴^]^[⁵^]、単連結ネットワーク^[⁷^]）は、基となる無向グラフが木である有向非巡回グラフ（DAG）です。言い換えれば、その有向エッジを無向エッジに置き換えると、連結かつ非巡回な無向グラフが得られます。

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

ポリフォレスト

ポリフォレスト（または有向フォレスト、方向付きフォレスト）とは、基となる無向グラフがフォレストである有向非巡回グラフのことである。言い換えれば、有向エッジを無向エッジに置き換えると、非巡回的な無向グラフが得られる。

有向木と同様に、一部の著者は「有向森」という表現を、各連結成分の辺がすべて特定の頂点に向かっている場合、またはすべて特定の頂点から離れる方向に向いている場合（分岐を参照）に限定している。^{[ 22 ]}

根付いた木

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

一般的に木には根があるという文脈において、特定の根を持たない木は自由木と呼ばれる。

ラベル付き木とは、各頂点に一意のラベルが付けられた木のことです。n 個の頂点 (n は非負整数 $)$ $を持つラベル付き木の頂点には、通常$ $1、2、\dots、 n$ というラベルが付けられます。再帰木とは、頂点ラベルが木の順序を尊重するラベル付き根付き木のことです (つまり、2 つの頂点 $u$ と $vについて$ $u < v$ $の場合、 u$ のラベルは $v$ のラベルよりも小さくなります)。

根付き木では、頂点 $vの$ 親は、根へのパスで $v$ に接続されている頂点です。根には親がいませんが、すべての頂点には一意の親があります。 ^[²⁴^]頂点 $v$ の子は、 $v$ が親である頂点です。 ^[²⁴^]頂点 $v$ のアセンダントは、 $v$ の親であるか、または (再帰的に) $v$ の親のアセンダントである任意の頂点です。頂点 $vの$ 子孫は、 $v$ の子であるか、または (再帰的に) $v$ の子の子孫である任意の頂点です。頂点 $vの$ 兄弟は、 $v$ と親を共有する木上の他の任意の頂点です。^[²⁴^]葉は、子を持たない頂点です。^[²⁴^]内部頂点は、葉ではない頂点です。^[²⁴^]

根付き木の頂点の高さは、その頂点から葉までの最長下降パスの長さです。木の高さは根の高さです。頂点の深さは、その根までのパスの長さです（根パス）。木の深さは、任意の頂点の最大深さです。深さは、さまざまな自己平衡木、特にAVL 木を操作する際によく必要になります。根の深さは 0、葉の高さは 0、頂点が 1 つしかない木（つまり根と葉の両方がある木）の深さと高さは 0 です。慣例として、空の木（頂点がない木、そのような木が許される場合）の深さと高さは -1 です。

$k$ 進木( $k$ は非負整数)は $、各頂点が最大でk 個$ の子を持つ根付き木です。^{[ 25 ]} 2 進木はバイナリツリーと呼ばれることが多く、3 進木は三進木と呼ばれることもあります。

注文した木

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

物件

すべての木は二部グラフである。グラフが二部グラフであるのは、奇数長のサイクルを一切含まない場合のみである。木はサイクルを全く含まないため、二部グラフである。
頂点数が可算個しかない木はすべて平面グラフである。
すべての連結グラフGは全域木を持ちます。全域木とは、 Gのすべての頂点を含み、その辺がGの辺である木のことです。すべての連結有限グラフに存在するより具体的な全域木の種類には、深さ優先探索木と幅優先探索木があります。深さ優先探索木の存在を一般化すると、可算個の頂点のみを持つすべての連結グラフはトレモー木を持ちます。^{[ 28 ]}ただし、非可算次数のグラフの中には、そのような木を持たないものもあります。^{[ 29 ]}
n > 1であるn個の頂点を持つ有限木は、少なくとも 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, \dots,$ $n$ の次数がそれぞれ $d$ $1$ $,$ $d$ $2$ $, \dots,$ $d$ $n$ である木の数は、多項係数です。

{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）は漸近推定を証明した

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

$C \approx 0.534949606...$ 、 $α \approx 2.95576528565...$ ( OEISの配列A051491 )である。ここで、 $~$ 記号は、

\lim_{n\to\infty}{t(n)}{C\alpha^nn^{-5/2}}}=1.}

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

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

$D \approx 0.43992401257...$ で、 $αは$ 上記と同じである（ Knuth (1997)、第2.3.4.4章およびFlajolet & Sedgewick (2009)、第VII.5章、p. 475を参照）。

$r (n)$ の最初のいくつかの値は^[³⁰^]です

1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, 32973, … ( OEISのシーケンスA000081 )。

樹木の種類

パスグラフ（または線形グラフ）は、n $個の$ 頂点が直線上に配置され、頂点 $i$ と $i$ $+ 1が$ $i$ $= 1, \dots,$ $n$ $- 1$ に対して辺で接続されているものです。
星型ツリーは、ルートと呼ばれる中心頂点と、それに接続された複数のパスグラフから構成されます。より厳密に言えば、次数が2より大きい頂点がちょうど1つだけ存在するツリーは、星型ツリーと呼ばれます。
スターツリーとは、単一の内部頂点（および $n -1個の$ 葉）からなる木のことです。言い換えれば、 $n$ 次のスターツリーとは、可能な限り多くの葉を持つ $n$ 次の木のことです。
キャタピラーツリーとは、すべての頂点が中心パス部分グラフから距離1以内にある木のことである。
ロブスターツリーとは、すべての頂点が中心パス部分グラフから距離2以内にある木のことである。
$次数d$ の正則木とは、各頂点に $d$ 本の辺を持つ無限木のことである。これらは自由群のケイリーグラフやティッツビルディングの理論において現れる。統計力学においては、ベテ格子として知られている。

注記

↑ベンダー＆ウィリアムソン 2010、p. 171。
↑ベンダー＆ウィリアムソン 2010、p. 172。
1 2 3 4 Deo 1974、p. 206。
1 2ハラリーとサムナー (1980)を参照。
1 2シモン（1991）を参照。
1 2 Dasgupta (1999)を参照。
1 2キム＆パール（1983）を参照。
↑スタンリー・ギル・ウィリアムソン (1985).コンピュータサイエンスのための組み合わせ論. クーリエ・ドーバー出版. p. 288. ISBN 978-0-486-42076-9。
↑ Mehran Mesbahi; Magnus Egerstedt (2010). Graph Theoretic Methods in Multiagent Networks . Princeton University Press. p. 38. ISBN 978-1-4008-3535-5。
↑杜丁珠、高克一、胡暁東 (2011).近似アルゴリズムの設計と分析. Springer Science & Business Media. p. 108. ISBN 978-1-4614-1701-9。
1 2 3 4 Deo 1974、p. 207。
↑ Jonathan L. Gross; Jay Yellen; Ping Zhang (2013). Handbook of Graph Theory, Second Edition . CRC Press. p. 116. ISBN 978-1-4398-8018-0。
↑ Bernhard Korte ; Jens Vygen (2012). Combinatorial Optimization: Theory and Algorithms (5th ed.). Springer Science & Business Media. p. 28. ISBN 978-3-642-24488-9。
↑ Kurt Mehlhorn ; Peter Sanders (2008). Algorithms and Data Structures: The Basic Toolbox (PDF) . Springer Science & Business Media. p. 52. ISBN 978-3-540-77978-02015年9月8日にオリジナルからアーカイブされた（PDF）。
↑ David Makinson (2012). Sets, Logic and Maths for Computing . Springer Science & Business Media. pp. 167–168 . ISBN 978-1-4471-2499-3。
↑ Kenneth Rosen ( 2011).離散数学とその応用、第7版。McGraw-Hill Science。p. 747。ISBN 978-0-07-338309-5。
↑アレクサンダー・シュライバー (2003)。組み合わせ最適化: 多面体と効率。スプリンガー。 p. 34.ISBN 3-540-44389-4。
↑ケイリー (1857)「木と呼ばれる解析形式の理論について」『フィロソフィカル・マガジン』第4シリーズ、 13 : 172–176。ただし、1847年にKGCフォン・シュタウトが著書『位置の幾何学』（ニュルンベルク、ドイツ：バウアー・ウント・ラスペ、1847年）の20–21ページで、木に依拠したオイラーの多面体定理の証明を示したことは言及して。また、1847年にドイツの物理学者グスタフ・キルヒホフは電気回路を調査し、回路内のワイヤ/抵抗器（枝）の数（n）、接合点（頂点）の数（m）、ループ（面）の数（μ）の間の関係を発見した。彼は木に依拠した議論によってその関係を証明した。参照: Kirchhoff, GR (1847) "Ueber die Auflösung der Gleichungen, auf welche man bei der Untersubung der lineen Vertheilung galvanischer Ströme geführt wird" 2023-07-20ウェイバックマシンにアーカイブ(ガルバニ電流の線形分布の研究によって導かれる方程式の解法について)電流)、 Annalen der Physik und Chemie、 72 (12): 497–508。
↑ DeBiasio, Louis; Lo, Allan (2019-10-09). "Spanning trees with few branch vertices". arXiv : 1709.04937 [ math.CO ].
↑ハラリーとプリンス、1959 年、p. 150。
↑ Chen, Wai-kai (1966). "On directed trees and directed $k$ -trees of a digraph and their generation". SIAM Journal on Applied Mathematics . 14 (3): 550– 560. doi : 10.1137/0114048 . MR 0209064 .
1 2 Kozlov, Dmitry N. (1999). "有向木の複合体". Journal of Combinatorial Theory . Series A. 88 (1): 112– 122. doi : 10.1006/jcta.1999.2984 . MR 1713484 .
↑ Tran, Ngoc Mai; Buck, Johannes; Klüppelberg, Claudia (2024年2月)、「極値に対する有向木の推定」、Journal of the Royal Statistical Society Series B: Statistical Methodology、86 (3): 771–792、arXiv : 2102.06197、doi : 10.1093/jrsssb/qkad165
1 2 3 4 5 6 7 Bender & Williamson 2010、p. 173。
↑ Black, Paul E. (2007年5月4日) 「k-ary tree」を参照。米国国立標準技術研究所。2015年2月8日のオリジナルからアーカイブ済み。2015年2月8日に取得。
↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2022). Introduction to Algorithms (4th ed.). Section B.5.3, Binary and positional trees : MIT Press. p. 1174. ISBN 97802620463052023年7月16日にオリジナルからアーカイブされました。2023年7月20日に取得されました。{{cite book}}: CS1メンテナンス: 場所 (リンク)
↑スタンレー、リチャード P. (2012)、『列挙的組合せ論』第 I 巻、ケンブリッジ高等数学研究、第49 巻、ケンブリッジ大学出版局、573 ページ、ISBN 9781107015425
↑ Diestel (2005)、提案 8.2.4。
↑ Diestel (2005)、提案 8.5.2。
↑ Li (1996)を参照。

参考文献

ベンダー、エドワード A.、ウィリアムソン、S. ギル (2010)、『リスト、決定、グラフ：確率入門付き』
Dasgupta, Sanjoy (1999)、「ポリツリーの学習」、第15回人工知能における不確実性に関する会議（UAI 1999）議事録、ストックホルム、スウェーデン、1999年7月～8月 （PDF）、pp. 134–141 。
Deo, Narsingh (1974), Graph Theory with Applications to Engineering and Computer Science (PDF) , Englewood, New Jersey: Prentice-Hall, ISBN 0-13-363473-62019年5月17日にオリジナルからアーカイブされた（PDF）。
フランク・ハラリー; Prins, Geert (1959)、「同相既約木およびその他の種の数」、Acta Mathematica、101 ( 1–2 ): 141–162、doi : 10.1007/BF02559543、ISSN 0001-5962
Harary, Frank ; Sumner, David (1980)、「有向木の二色数」、Journal of Combinatorics, Information & System Sciences、5 (3): 184–187、MR 0603363 。
Kim, Jin H.; Pearl, Judea (1983)、「推論エンジンにおける因果的および診断的推論のための計算モデル」、第8回国際人工知能合同会議（IJCAI 1983）議事録、ドイツ、カールスルーエ、1983年8月（PDF）、pp. 190–193 。
Li, Gang (1996)、「根付き木と自由木の生成」、修士論文、ビクトリア大学コンピュータサイエンス学部、ブリティッシュコロンビア州、カナダ(PDF)、p. 9。
Simion, Rodica (1991)、「1因子を持つ木と有向木」、離散数学、88 (1): 93–104、doi : 10.1016/0012-365X(91)90061-6、MR 1099270 。

さらに読む

Diestel、Reinhard (2005)、グラフ理論(第 3 版)、ベルリン、ニューヨーク: Springer-Verlag、ISBN 978-3-540-26183-4。
フラジョレ、フィリップ；セッジウィック、ロバート（2009）、『解析的組み合わせ論』、ケンブリッジ大学出版局、ISBN 978-0-521-89806-5
「木」、数学百科事典、EMS Press、2001年 [1994年]
ドナルド・E・クヌース（1997年11月14日）『コンピュータプログラミングの技法第1巻：基本アルゴリズム』（第3 版）、アディソン・ウェスリー・プロフェッショナル
Jerrum, Mark (1994)、「グラフ内の木の数を数えることは#P完全である」、Information Processing Letters、51 (3): 111– 116、doi : 10.1016/0020-0190(94)00085-9、ISSN 0020-0190 。
オッター、リチャード（1948）「木の数」、Annals of Mathematics、第2シリーズ、49（3）：583–599、doi：10.2307/1969046、JSTOR 1969046 。

[FOOTNOTEBenderWilliamson2010171-1] ベンダー＆ウィリアムソン 2010、p. 171。

[FOOTNOTEBenderWilliamson2010172-2] ベンダー＆ウィリアムソン 2010、p. 172。

[FOOTNOTEDeo1974206-3] 1 2 3 4 Deo 1974、p. 206。

[Harary_1980-4] 1 2ハラリーとサムナー (1980)を参照。

[s91-5] 1 2シモン（1991）を参照。

[d99-6] 1 2 Dasgupta (1999)を参照。

[kp83-7] 1 2キム＆パール（1983）を参照。

[Williamson1985-8] スタンリー・ギル・ウィリアムソン (1985).コンピュータサイエンスのための組み合わせ論. クーリエ・ドーバー出版. p. 288. ISBN 978-0-486-42076-9。

[multi-9] Mehran Mesbahi; Magnus Egerstedt (2010). Graph Theoretic Methods in Multiagent Networks . Princeton University Press. p. 38. ISBN 978-1-4008-3535-5。

[DuKo2011-10] 杜丁珠、高克一、胡暁東 (2011).近似アルゴリズムの設計と分析. Springer Science & Business Media. p. 108. ISBN 978-1-4614-1701-9。

[FOOTNOTEDeo1974207-11] 1 2 3 4 Deo 1974、p. 207。

[GrossYellen2013-12] Jonathan L. Gross; Jay Yellen; Ping Zhang (2013). Handbook of Graph Theory, Second Edition . CRC Press. p. 116. ISBN 978-1-4398-8018-0。

[KorteVygen2012b-13] Bernhard Korte ; Jens Vygen (2012). Combinatorial Optimization: Theory and Algorithms (5th ed.). Springer Science & Business Media. p. 28. ISBN 978-3-642-24488-9。

[MehlhornSanders2008-14] Kurt Mehlhorn ; Peter Sanders (2008). Algorithms and Data Structures: The Basic Toolbox (PDF) . Springer Science & Business Media. p. 52. ISBN 978-3-540-77978-02015年9月8日にオリジナルからアーカイブされた（PDF）。

[Makinson2012-15] David Makinson (2012). Sets, Logic and Maths for Computing . Springer Science & Business Media. pp. 167–168 . ISBN 978-1-4471-2499-3。

[16] Kenneth Rosen ( 2011).離散数学とその応用、第7版。McGraw-Hill Science。p. 747。ISBN 978-0-07-338309-5。

[Schrijver2003-17] アレクサンダー・シュライバー (2003)。組み合わせ最適化: 多面体と効率。スプリンガー。 p. 34.ISBN 3-540-44389-4。

[18] ケイリー (1857)「木と呼ばれる解析形式の理論について」『フィロソフィカル・マガジン』第4シリーズ、 13 : 172–176。ただし、1847年にKGCフォン・シュタウトが著書『位置の幾何学』（ニュルンベルク、ドイツ：バウアー・ウント・ラスペ、1847年）の20–21ページで、木に依拠したオイラーの多面体定理の証明を示したことは言及して。また、1847年にドイツの物理学者グスタフ・キルヒホフは電気回路を調査し、回路内のワイヤ/抵抗器（枝）の数（n）、接合点（頂点）の数（m）、ループ（面）の数（μ）の間の関係を発見した。彼は木に依拠した議論によってその関係を証明した。参照: Kirchhoff, GR (1847) "Ueber die Auflösung der Gleichungen, auf welche man bei der Untersubung der lineen Vertheilung galvanischer Ströme geführt wird" 2023-07-20ウェイバックマシンにアーカイブ(ガルバニ電流の線形分布の研究によって導かれる方程式の解法について)電流)、 Annalen der Physik und Chemie、 72 (12): 497–508。

[19] DeBiasio, Louis; Lo, Allan (2019-10-09). "Spanning trees with few branch vertices". arXiv : 1709.04937 [ math.CO ].

[FOOTNOTEHararyPrins1959150-20] ハラリーとプリンス、1959 年、p. 150。

[21] Chen, Wai-kai (1966). "On directed trees and directed $k$ -trees of a digraph and their generation". SIAM Journal on Applied Mathematics . 14 (3): 550– 560. doi : 10.1137/0114048 . MR 0209064 .

[kozlov-22] 1 2 Kozlov, Dmitry N. (1999). "有向木の複合体". Journal of Combinatorial Theory . Series A. 88 (1): 112– 122. doi : 10.1006/jcta.1999.2984 . MR 1713484 .

[23] Tran, Ngoc Mai; Buck, Johannes; Klüppelberg, Claudia (2024年2月)、「極値に対する有向木の推定」、Journal of the Royal Statistical Society Series B: Statistical Methodology、86 (3): 771–792、arXiv : 2102.06197、doi : 10.1093/jrsssb/qkad165

[FOOTNOTEBenderWilliamson2010173-24] 1 2 3 4 5 6 7 Bender & Williamson 2010、p. 173。

[25] Black, Paul E. (2007年5月4日) 「k-ary tree」を参照。米国国立標準技術研究所。2015年2月8日のオリジナルからアーカイブ済み。2015年2月8日に取得。

[26] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2022). Introduction to Algorithms (4th ed.). Section B.5.3, Binary and positional trees : MIT Press. p. 1174. ISBN 97802620463052023年7月16日にオリジナルからアーカイブされました。2023年7月20日に取得されました。{{cite book}}: CS1メンテナンス: 場所 (リンク)

[27] スタンレー、リチャード P. (2012)、『列挙的組合せ論』第 I 巻、ケンブリッジ高等数学研究、第49 巻、ケンブリッジ大学出版局、573 ページ、ISBN 9781107015425

[FOOTNOTEDiestel2005Prop._8.2.4-28] Diestel (2005)、提案 8.2.4。

[FOOTNOTEDiestel2005Prop._8.5.2-29] Diestel (2005)、提案 8.5.2。

[30] Li (1996)を参照。

[

[

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[

[

[

[

[

[

[

[

[

[

[ 18 ]

[ 19 ]

[

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]

[ 26 ]

[ 27 ]

[ 28 ]

[ 29 ]

[