樹状構造（グラフ理論）

任意の頂点 $v$ が、根頂点から自身への有向経路をちょうど1つだけ持つような、樹状構造の一例。

グラフ理論において、アーボレッセンスとは、ある頂点 $r$ (根と呼ばれる)が存在し、他の任意の頂点 $vに対して、$ $r$ から $v$ への有向ウォークがちょうど 1 つ存在するような有向グラフのことである(根 $r$ は一意であることに注意)。^[¹^]したがって、アーボレッセンスは、ここでは無向グラフとして理解される根付き木の有向グラフ形式である。^[²^]^[³^]アーボレッセンスは、すべてのエッジが根から離れる方向を向いている有向根付き木でもある。他にも同等の特徴付けがいくつか存在する。^[⁴^]^[⁵^]

すべての樹状構造は有向非巡回グラフ（DAG）であるが、すべてのDAGが樹状構造であるとは限らない。

意味

arborescenceという用語はフランス語に由来します。^{[ 6 ]}一部の著者は、綴りが面倒であるという理由でこれに反対しています。^{[ 7 ]}グラフ理論では、arborescence の同義語が多数あり、有向根付き木、^{[ 3 ]}^{[ 7 ]} out-arborescence、^{[ 8 ]} out-tree、^{[ 9 ]}などがあり、同じ概念を表すためにbranchingも使用されています。 ^{[ 9 ]}根付き木自体は、一部の著者によって有向グラフとして定義されています。^{[ 10 ]}^{[ 11 ]}^{[ 12 ]}

さらなる定義

さらに、一部の著者は、アーボレッセンスを、与えられた有向グラフの全域有向木と定義しています。^{[ 12 ]}同義語のいくつか、特に分岐についても同じことが言えます。^{[ 13 ]}他の著者は、分岐をアーボレッセンスの森を表すために使用しており、後者の概念は、この記事の冒頭でより広い意味で定義されています。 ^{[ 14 ]}^{[ 15 ]}ただし、全域のニュアンスの両方の概念を含むバリエーションも見られます。^{[ 12 ]}

また、樹状構造のすべての辺を反転させることによって、有用な概念を定義することも可能である。つまり、すべての辺を根から離れる方向ではなく、根の方向に向けておく。このような有向グラフは、in-tree ^{[ 16 ]}やanti-arborescence ^{[ 17 ]} など、さまざまな用語で指定される。WT Tutte は、arborescence が[ある根]から分岐する場合とarborescence が [ある根] に収束する場合という表現を用いて、2 つのケースを区別している。^{[ 18 ]}

$n$ 個のノードを持つ根付き木（または樹状構造）の数は、次の数列で表されます。

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

参考文献

↑ Darij Grinberg (2023 年 8 月 2 日). "グラフ理論入門 (ドレクセル大学 2022 年春学期 Math 530 のテキスト)" (PDF) . Darij Grinberg、ルートヴィヒ・マクシミリアン大学ミュンヘン. p. 187 . 2024 年7 月 2 日取得.定理 5.6.5、ステートメント A4: 各頂点 v ∈ V に対して、多重有向グラフ D は r から v への一意のウォークを持つ。
↑ Gordon, Gary (1989). "A greedoid polynomial which distinguishes rooted arborescences" . Proceedings of the American Mathematical Society . 107 (2): 287– 298. doi : 10.1090/S0002-9939-1989-0967486-0 .
1 2スタンレー・ギル・ウィリアムソン (1985).コンピュータサイエンスのための組み合わせ論. クーリエ・ドーバー出版. p. 288. ISBN 978-0-486-42076-9。
↑ジャン＝クロード・フルニエ (2013).グラフ理論と応用：演習問題付き. ジョン・ワイリー・アンド・サンズ. pp. 94–95 . ISBN 978-1-84821-070-7。
↑ Jean Gallier (2011).離散数学. Springer Science & Business Media. pp. 193–194 . ISBN 978-1-4419-8046-5。
↑ Per Hage およびFrank Harary (1996). Island Networks: Communication, Kinship, and Classification Structures in Oceania . Cambridge University Press. p. 43. ISBN 978-0-521-55232-5。
1 2 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ジョナサン・L・グロス、ジェイ・イェレン、ピン・チャン（2013）。グラフ理論ハンドブック、第2版。CRC Press。p. 116。ISBN 978-1-4398-8018-0。
↑ 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。
1 2 3アレクサンダー・シュライバー (2003)。組み合わせ最適化: 多面体と効率。スプリンガー。 p. 34.ISBN 3-540-44389-4。
↑ Jørgen Bang-Jensen; Gregory Z. Gutin (2008). Digraphs: Theory, Algorithms and Applications . Springer. p. 339. ISBN 978-1-84800-998-1。
↑ジェームズ・エヴァンス (1992).ネットワークとグラフのための最適化アルゴリズム、第2版。CRC Press。p. 59。ISBN 978-0-8247-8602-1。
↑ Bernhard Korte ; Jens Vygen (2012). Combinatorial Optimization: Theory and Algorithms (5th ed.). Springer Science & Business Media. p. 18. 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-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。
↑ Tutte, WT (2001), Graph Theory , Cambridge University Press, pp. 126–127 , ISBN 978-0-521-79489-3

外部リンク

ワイススタイン、エリック W. 「樹状構造」 . MathWorld .
ワイススタイン、エリック W. 「根付き木」 . MathWorld .

[Grinberg2023-1] Darij Grinberg (2023 年 8 月 2 日). "グラフ理論入門 (ドレクセル大学 2022 年春学期 Math 530 のテキスト)" (PDF) . Darij Grinberg、ルートヴィヒ・マクシミリアン大学ミュンヘン. p. 187 . 2024 年7 月 2 日取得.定理 5.6.5、ステートメント A4: 各頂点 v ∈ V に対して、多重有向グラフ D は r から v への一意のウォークを持つ。

[poly-2] Gordon, Gary (1989). "A greedoid polynomial which distinguishes rooted arborescences" . Proceedings of the American Mathematical Society . 107 (2): 287– 298. doi : 10.1090/S0002-9939-1989-0967486-0 .

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

[Fournier2013-4] ジャン＝クロード・フルニエ (2013).グラフ理論と応用：演習問題付き. ジョン・ワイリー・アンド・サンズ. pp. 94–95 . ISBN 978-1-84821-070-7。

[Gallier2011-5] Jean Gallier (2011).離散数学. Springer Science & Business Media. pp. 193–194 . ISBN 978-1-4419-8046-5。

[Hage1996-6] Per Hage およびFrank Harary (1996). Island Networks: Communication, Kinship, and Classification Structures in Oceania . Cambridge University Press. p. 43. ISBN 978-0-521-55232-5。

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

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

[GrossYellen2013-9] 1 2ジョナサン・L・グロス、ジェイ・イェレン、ピン・チャン（2013）。グラフ理論ハンドブック、第2版。CRC Press。p. 116。ISBN 978-1-4398-8018-0。

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

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

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

[Bang-JensenGutin2008-13] Jørgen Bang-Jensen; Gregory Z. Gutin (2008). Digraphs: Theory, Algorithms and Applications . Springer. p. 339. ISBN 978-1-84800-998-1。

[Evans1992-14] ジェームズ・エヴァンス (1992).ネットワークとグラフのための最適化アルゴリズム、第2版。CRC Press。p. 59。ISBN 978-0-8247-8602-1。

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

[MehlhornSanders2008-16] Kurt Mehlhorn ; Peter Sanders (2008). Algorithms and Data Structures: The Basic Toolbox (PDF) . Springer Science & Business Media. p. 52. ISBN 978-3-540-77978-0。

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

[18] Tutte, WT (2001), Graph Theory , Cambridge University Press, pp. 126–127 , ISBN 978-0-521-79489-3

[

[

[

[

[

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

樹状構造（グラフ理論）

意味

さらなる定義

関連項目

参考文献

外部リンク

関連するトピック

グラフ理論

頂点

有向ウォークがちょうど 1 つ存在するような

有向グラフの