マルチツリー

組合せ論と順序理論では、多重木は2 つの同等な構造のいずれかを表します。1 つは、任意の 2 つの頂点間に最大で 1 つの有向パスしかない有向非巡回グラフ(DAG) 、もう 1 つは、任意の頂点から到達可能なサブグラフが無向木を誘導する DAG です。もう 1 つは、4 つの項目a、b、c、およびd がa ≤ b ≤ dおよびa ≤ c ≤ dのダイヤモンド部分順序を形成することはないが、 bとc が互いに比較できない部分順序集合 (poset)です(ダイヤモンドフリー poset ^[1]とも呼ばれます)。

計算複雑性理論では、マルチツリーは強く一義的なグラフやマングローブとも呼ばれ、任意の2つの状態を結ぶ計算パスが最大で1つしかない非決定性アルゴリズムをモデル化するために使用できます。^[2]

マルチツリーは、同じグラウンドセット上の複数の重複する分類法を表すために使用できます。^[3]家系図に、ある家族から別の家族への複数の結婚が含まれる可能性があるが、2人の血縁者間の結婚は含まれていない場合、それはマルチツリーを形成します。^[4]

有向非巡回グラフでは、任意の 2 つの頂点間に最大で 1 つの有向パスがある場合、または同等に、任意の頂点から到達可能なサブグラフが無向ツリーを誘導する場合、その到達可能性関係はダイヤモンドフリー半順序です。逆に、ダイヤモンドフリー半順序では、推移的縮約により、任意の頂点から到達可能なサブグラフが無向ツリーを誘導する有向非巡回グラフが識別されます。

ダイヤモンドフリー集合族とは、包含順序がダイヤモンドフリー半集合を形成する集合族Fである。D ( n )がn元集合の最大のダイヤモンドフリー部分集合族を表す場合、次の式が成り立つことが知られている 。

${\displaystyle 2\leq \lim _{n\to \infty }D(n){\Big /}{\binom {n}{\lfloor n/2\rfloor }}\leq 2{\frac {3}{11}}}$、

そしてその限界は2であると推測される^。[1]

ポリツリーは、無向木のエッジ を方向付けて形成される有向非巡回グラフであり、マルチツリーの特殊なケースです。

マルチツリー内の任意の頂点から到達可能なサブグラフは、頂点をルートとする樹状線、つまりすべてのエッジがルートから離れた方向を向いているポリツリーです。

「マルチツリー」という言葉は、直列-並列半順序^[5]や、複数のツリーを組み合わせて形成される他の構造を指すためにも使用されています。