ポリツリー

数学、特にグラフ理論において、ポリツリー^{[ 1 ]}（有向木^{[ 2 ]} 、方向付き木^{[ 3 ]}、単連結ネットワーク^{[ 4 ]}とも呼ばれる）は、基となる無向グラフが木である有向非巡回グラフである。言い換えれば、ポリツリーは、連結された非巡回無向グラフの各辺に方向を割り当てることによって形成される。

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

ポリツリーは、有向グラフの一例です。

ポリツリーという用語は、1987年にRebaneとPearlによって造語された。^{[ 5 ]}

• アーボレッセンスとは、有向根付き木、すなわち、単一の始点ノードから他のすべてのノードへの一意なパスが存在する有向非巡回グラフのことです。すべてのアーボレッセンスはポリツリーですが、すべてのポリツリーがアーボレッセンスであるとは限りません。
• マルチツリーとは、任意のノードから到達可能な部分グラフが木構造を形成する有向非巡回グラフのことである。すべてのポリツリーはマルチツリーである。
• 多木構造のノード間の到達可能性関係は、最大で3次元の順序次元を持つ部分順序を形成します。順序次元が3の場合、7つの要素からなる部分集合が存在する必要があります。${\displaystyle x}$、$\displaystyle y_{i}}$、 そして${\displaystyle z_{i}}$（のために${\displaystyle i=0,1,2}$）各​${\displaystyle i}$、どちらか${\displaystyle x\leq y_{i}\geq z_{i}}$または${\displaystyle x\geq y_{i}\leq z_{i}}$これらの6つの不等式は、これら7つの要素上のポリツリー構造を定義する。^{[ 6 ]}
• フェンスまたはジグザグ順序集合は、基となる木がパスであり、辺の向きがパスに沿って交互に変化するポリツリーの特殊なケースです。ポリツリーの到達可能性順序は、一般化されたフェンスとも呼ばれています。^{[ 7 ]}

異なるポリツリーの数${\displaystyle n}$ラベルなしノードの場合${\displaystyle n=1,2,3,\dots }$、 は

デイビッド・サムナーにちなんで名付けられたサムナー予想は、トーナメントは多木構造の普遍グラフであると述べている。つまり、すべてのトーナメントは多木構造の普遍グラフであり、${\displaystyle 2n-2}$頂点には、すべてのポリツリーが含まれます。${\displaystyle n}$頂点を部分グラフとして扱う。未解決ではあるが、十分大きな値に対しては証明されている。${\displaystyle n}$[ ^{8 ]​}

ポリツリーは、確率的推論のグラフィカルモデルとして使用されてきました。^{[ 1 ]}ベイジアンネットワークがポリツリーの構造を持つ場合、信念伝播を使用して効率的に推論を実行できます。^{[ 4 ] [ 5 ]}

ベクトル空間上の実数値関数の等高線木は、関数のレベルセットを表す多木です。等高線木のノードは、関数の臨界点を通るレベルセットであり、エッジは臨界点を持たない連続したレベルセットを表します。エッジの向きは、対応する2つのレベルセット上の関数値の比較によって決定されます。^{[ 9 ]}

• グラフ理論用語集

• Carr, Hamish; Snoeyink, Jack; Axen, Ulrike (2000)、「あらゆる次元における輪郭木の計算」、第11回ACM-SIAM離散アルゴリズムシンポジウム（SODA 2000）論文集、Association for Computing Machinery、pp. 918–926、ISBN  978-0-89871-453-1
• Dasgupta, Sanjoy (1999)、「ポリツリーの学習」（PDF）、第15回人工知能における不確実性に関する会議（UAI 1999）議事録、ストックホルム、スウェーデン、1999年7月～8月、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-6。
• Harary, Frank ; Sumner, David (1980)、「有向木の二色数」、Journal of Combinatorics, Information & System Sciences、5 (3): 184–187、MR 0603363 。
• Kim, Jin H.; Pearl, Judea (1983)、「推論エンジンにおける因果的および診断的推論のための計算モデル」（PDF）、第8回国際人工知能合同会議（IJCAI 1983）議事録、ドイツ、カールスルーエ、1983年8月、pp. 190–193 。
• Kühn, Daniela ; Mycroft, Richard; Osthus, Deryk (2011)、「大規模トーナメントにおけるSumnerの普遍トーナメント予想の証明」、Proceedings of the London Mathematical Society、第3シリーズ、102 (4): 731–766、arXiv : 1010.4430、doi : 10.1112/plms/pdq035、MR 2793448 。
• Rebane, George; Pearl, Judea (1987)、「統計データからの因果ポリツリーの復元」（PDF）、第3回人工知能における不確実性に関する年次会議（UAI 1987）議事録、米国ワシントン州シアトル、1987年7月、pp. 222–228 。
• Ruskey, Frank (1989)、「交代順列の転置生成」、Order、6 (3): 227–233、doi : 10.1007/BF00563523、MR 1048093 。
• Simion, Rodica (1991)、「1因子を持つ木と有向木」、離散数学、88 (1): 93–104、doi : 10.1016/0012-365X(91)90061-6、MR 1099270 。
• Trotter, William T. Jr. ; Moore, John I. Jr. (1977)、「平面半順序集合の次元」、Journal of Combinatorial Theory, Series B、22 (1): 54–67、doi : 10.1016/0095-8956(77)90048-X。