良いスパニングツリー

数学のグラフ理論の分野において、埋め込み平面グラフの良好な全域木 ^[1] とは、 非木辺が以下の条件を満たす 根付き全域木である。${\displaystyle T}$ ${\displaystyle G}$${\displaystyle G}$

• の根から 葉までの経路上に、木以外のエッジは存在しない。${\displaystyle (u,v)}$${\displaystyle u}$${\displaystyle v}$${\displaystyle T}$
• 頂点に接続する辺は3つの集合とに分けることができ、ここで、 ${\displaystyle v}$${\displaystyle X_{v},Y_{v}}$${\displaystyle Z_{v}}$
  • ${\displaystyle X_{v}}$非ツリーエッジの集合であり、それらはレッドゾーンで終了する
  • ${\displaystyle Y_{v}}$木の辺の集合であり、それらは${\displaystyle v}$
  • ${\displaystyle Z_{v}}$非ツリーエッジのセットであり、それらはグリーンゾーンで終了します

出典: ^{[1] [2]}

を平面グラフとする。をの根付き全域木とする。を における根から頂点 への経路とする。 この経路は、、 を除く の子 を2 つのグループ、つまり左グループと右グループに分割する。 の子 はグループに属し 、 で表されるのは、辺 から順序付けを開始したときに、 に付随する辺を時計回りに並べたときに、辺 が の前に現れる場合である。同様に、 の子 はグループに属し、 で表されるのは、辺 から順序付けを開始したときに、 に付随する辺を時計回りに並べたときに、辺 が の後に現れる場合である。のすべての頂点 がに関して次の 2 つの条件を満たす場合、木はの良好な全域木^[1] と呼ばれる 。 ${\displaystyle G_{\phi}}$${\displaystyle T}$${\displaystyle G_{\phi}}$${\displaystyle P(r,v)=(r=u_{1}),u_{2},\ldots ,(v=u_{k})}$${\displaystyle T}$${\displaystyle r}$${\displaystyle v\neq r}$${\displaystyle P(r,v)}$${\displaystyle u_{i}}$${\displaystyle (1\leq i<k)}$${\displaystyle u_{i+1}}$${\displaystyle L}$${\displaystyle R}$${\displaystyle x}$${\displaystyle u_{i}}$${\displaystyle L}$${\displaystyle u_{i}^{L}}$${\displaystyle (u_{i},x)}$${\displaystyle (u_{i},u_{i+1})}$${\displaystyle u_{i}}$${\displaystyle (u_{i},u_{i+1})}$${\displaystyle x}$${\displaystyle u_{i}}$${\displaystyle R}$${\displaystyle u_{i}^{R}}$${\displaystyle (u_{i},x)}$${\displaystyle (u_{i},u_{i+1})}$${\displaystyle u_{i}}$${\displaystyle (u_{i},u_{i+1})}$${\displaystyle T}$${\displaystyle G_{\phi}}$${\displaystyle v}$ ${\displaystyle (v\neq r)}$${\displaystyle G_{\phi}}$${\displaystyle P(r,v)}$

• [条件1]には非木辺が存在しない。${\displaystyle G_{\phi}}$${\displaystyle (v,u_{i})}$${\displaystyle i<k}$
• [条件2]頂点に接する辺を除く辺は、3つの互いに素な（空の場合もある）集合に分割でき、次の条件（a）～（c）を満たす。 ${\displaystyle G_{\phi}}$${\displaystyle v}$${\displaystyle (u_{k-1},v)}$${\displaystyle X_{v},Y_{v}}$${\displaystyle Z_{v}}$
  • (a) およびはそれぞれ、連続する非木辺の集合であり、連続する木辺の集合である。${\displaystyle X_{v}}$${\displaystyle Z_{v}}$${\displaystyle Y_{v}}$
  • (b) 集合、 、 の辺は、辺 から時計回りにこの順序で現れます。${\displaystyle X_{v}}$${\displaystyle Y_{v}}$${\displaystyle Z_{v}}$${\displaystyle (u_{k-1},v)}$
  • ( c) 各辺 について、は に含まれ、各辺 について、は に含まれます。${\displaystyle (v,v')\in X_{v}}$${\displaystyle v'}$${\displaystyle T_{u_{i}^{L}}}$${\displaystyle i<k}$${\displaystyle (v,v')\in Z_{v}}$${\displaystyle v'}$${\displaystyle T_{u_{i}^{R}}}$${\displaystyle i<k}$

    

グラフの単調描画において^[2] 、グラフの2可視性表現において^[1]

すべての平面グラフには、良好な全域木を含む埋め込みがあります。良好な全域木と適切な埋め込みは、線形時間でから見つけることができます。 ^[1]のすべての埋め込みに良好な全域木が含まれるわけで はありません。${\displaystyle G}$${\displaystyle G_{\phi}}$${\displaystyle G_{\phi}}$${\displaystyle G}$${\displaystyle G}$

• スパニングツリー
• シュナイダー・リアライザー