ポリツリー

数学、より具体的にはグラフ理論において、ポリツリー^[1]（有向木^[2]、有向木^[3]、単連結ネットワーク^[4]とも呼ばれる）は、基となる無向グラフが木である有向非巡回グラフである。言い換えれば、有向辺を無向辺に置き換えると、連結かつ非巡回である無向グラフが得られる。（2つの無向辺が同じ有向辺に置き換えられてはならない。つまり、有向グラフ内で両方向の辺によってリンクされた頂点のペアが存在してはならない。）

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

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

ポリツリーという用語は1987年にRebaneとPearlによって造られました。^[5]

• 樹状構造は、有向ルート付きツリー、つまり、他のすべてのノードへの一意のパスを持つ単一のソース ノードが存在する有向非巡回グラフです。すべての樹状構造はポリツリーですが、すべてのポリツリーが樹状構造であるとは限りません。
• マルチツリーは、任意のノードから到達可能なサブグラフがツリーを形成する有向非巡回グラフです。すべてのポリツリーはマルチツリーです。
• ポリツリーのノード間の到達可能性関係は、最大で3つの順序次元を持つ半順序を形成します。順序次元が3の場合、7つの要素、、（ に対して）のサブセットが存在し、各に対して、またはのいずれかが存在し、これらの6つの不等式は、これら7つの要素上のポリツリー構造を定義します。^[6]${\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}}$
• フェンスまたはジグザグポセットは、基になるツリーがパスであり、エッジの方向がパスに沿って交互に変わるポリツリーの特殊なケースです。ポリツリーの到達可能性順序は、一般化フェンスとも呼ばれています。^[7]

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

サムナー予想は、デイヴィッド・サムナーにちなんで名付けられ、トーナメントは多角形の普遍グラフであるというもので、頂点を持つすべてのトーナメントには、頂点を持つすべての多角形が部分グラフとして含まれるというものである。この予想は未解決のままであるが、十分に大きい のすべての値に対して証明されている。^[8]${\displaystyle 2n-2}$${\displaystyle n}$${\displaystyle n}$

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

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

• グラフ理論用語集

• Carr, Hamish; Snoeyink, Jack; Axen, Ulrike (2000)、「すべての次元での等高線ツリーの計算」、Proc. 11th ACM-SIAM Symposium on Discrete Algorithms (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)、「グラフ理論と工学およびコンピュータサイエンスへの応用」(PDF)、ニュージャージー州エングルウッド: Prentice-Hall、ISBN 0-13-363473-6。
• ハラリー、フランク;サムナー、デイビッド(1980)、「有向木の二色数」、組合せ論、情報、システム科学ジャーナル、5 (3): 184–187、MR  0603363。
• Kim, Jin H.; Pearl, Judea (1983)、「推論エンジンにおける因果推論と診断推論の計算モデル」(PDF)、Proc. 8th International Joint Conference on Artificial Intelligence (IJCAI 1983)、カールスルーエ、ドイツ、1983 年 8 月、pp. 190–193。
• キューン、ダニエラ、マイクロフト、リチャード、オスタス、デリック (2011)、「大規模トーナメントに対するサムナーの普遍トーナメント予想の証明」、ロンドン数学会紀要、第 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。
• ラスキー、フランク（1989）、「交互順列の転置生成」、Order、6（3）：227–233、doi：10.1007 / BF00563523、MR  1048093。
• シミオン、ロディカ(1991)、「1因子の木と有向木」、離散数学、88 (1): 93–104、doi :10.1016/0012-365X(91)90061-6、MR  1099270。
• トロッター、ウィリアム T. ジュニア; ムーア、ジョン I. ジュニア (1977)、「平面ポセットの次元」、組み合わせ理論ジャーナル、シリーズ B、22 (1): 54–67、doi : 10.1016/0095-8956(77)90048-X。