トレモーの木

すべての有限連結無向グラフには、少なくとも1つのトレモー木が存在する。^{[ 4 ]}深さ優先探索を行い、各頂点（探索の開始頂点を除く）を、その頂点が発見された以前の頂点に接続することで、このような木を構築できる。このようにして構築された木は、深さ優先探索木として知られている。${\displaystyle uv}$はグラフ内の任意のエッジであり、${\displaystyle u}$探索によって到達する2つの頂点のうち、より早い方である場合、${\displaystyle v}$から派生するサブツリーに属していなければならない${\displaystyle u}$深さ優先探索木では、探索によって必然的に発見される${\displaystyle v}$このサブツリーを探索している間、サブツリー内の他の頂点のいずれかから、またはそれが失敗した場合は、${\displaystyle u}$直接。すべての有限トレモー木は深さ優先探索木として生成できます。${\displaystyle T}$は有限グラフのトレモー木であり、深さ優先探索では の子ノードを探索します。${\displaystyle T}$他の頂点を探索する前に各頂点を探索すると、必然的に${\displaystyle T}$深さ優先探索木として。

逐次的な深さ優先探索アルゴリズムによって見つかるトレモー木を見つけることはP 完全である。このアルゴリズムでは、各頂点の隣接頂点をその識別子の順に探索する。 ^{[ 5 ]}それにもかかわらず、ランダム化並列アルゴリズムによって異なるトレモー木を見つけることが可能であり、トレモー木の構築が複雑性クラスRNCに属することを示している。このアルゴリズムは、 0-1 重み付きグラフで最小重みの完全マッチングを見つけるための別のランダム化並列アルゴリズムに基づいている。^{[ 6 ]} 1997 年時点では、トレモー木の構築が複雑性クラスNCの決定論的並列アルゴリズムによって実行できるかどうかは不明であった。^{[ 7 ]}マッチングが NC で見つかるのであれば、トレモー木も NC で見つかる。^{[ 6 ]}

集合の性質を表現することは可能である${\displaystyle T}$ルート頂点を選択できるエッジ${\displaystyle r}$グラフの単項二階論理において、トレモー木を形成します。より具体的には、頂点集合と辺集合の両方に対して量化を可能にするMSO ₂と呼ばれる論理形式において、この性質は、以下の性質の論理積として表現できます。

• グラフはエッジで接続されています${\displaystyle T}$これは論理的に、グラフの頂点の空でない真部分集合ごとに、辺が存在するという記述として表現できます。${\displaystyle T}$指定された部分集合内に、ちょうど1つの端点が存在する。
• ${\displaystyle T}$非巡回である。これは論理的に、空でない部分集合が存在しないという命題として表現できる。${\displaystyle C}$の${\displaystyle T}$各頂点がゼロまたは２つの辺に接続している${\displaystyle C}$。
• あらゆるエッジ${\displaystyle e}$ない${\displaystyle T}$祖先-子孫の頂点ペアを接続する${\displaystyle T}$これは、両端が${\displaystyle e}$パスに属する${\displaystyle T}$。これは論理的に、すべての辺について次の文として表現できます。${\displaystyle e}$部分集合が存在する${\displaystyle P}$の${\displaystyle T}$ちょうど 2 つの頂点があり、そのうちの 1 つが${\displaystyle r}$は、単一のエッジに隣接しています。${\displaystyle P}$、そして両端が${\displaystyle e}$少なくとも１つのエッジに隣接している${\displaystyle P}$。

このようにしてトレモー木が特定されると、祖先端点から子孫端点への方向を持つエッジの集合を指定することで、与えられたグラフの向きを単項二階述語論理で記述することができます。この集合に含まれない残りのエッジは、反対方向に向き付けられなければなりません。この手法により、向きに関するグラフの特性を単項二階述語論理で指定することができ、これらの特性をクールセルの定理を用いて木幅が制限されたグラフ上で効率的にテストすることができます。^{[ 8 ]}

グラフにハミルトンパスが存在する場合、そのパス（その端点のいずれかを根とする）はトレモー木でもある。すべてのトレモー木がこの形式を持つ無向グラフは、サイクルグラフ、完全グラフ、およびバランスのとれた完全二部グラフである。^{[ 9 ]}

トレモー木は、木の深さの概念と密接に関連しています。グラフの木の深さ${\displaystyle G}$最小の数として定義できる${\displaystyle d}$グラフが存在する${\displaystyle H}$トレモーの木と共に${\displaystyle T}$高さ${\displaystyle d}$、したがって${\displaystyle G}$は、${\displaystyle H}$グラフ族における有界ツリー深さは、その族のグラフのグラフマイナーとして出現しないパスの存在と同等である。グラフ上の多くの困難な計算問題には、入力のツリー深さによってパラメータ化されると固定パラメータ扱い可能なアルゴリズムが存在する。 ^{[ 10 ]}

トレモー木は、与えられたグラフが平面グラフであるかどうかを判定するフレイセイ・ローゼンシュティール平面性判定基準においても重要な役割を果たします。この判定基準によれば、グラフは${\displaystyle G}$与えられたトレモー木に対して、${\displaystyle T}$の${\displaystyle G}$残りのエッジは、同じ配置のエッジが交差しないようにする制約に従って、木の左側または右側に一貫した方法で配置できます。^{[ 11 ]}

すべての無限グラフが正規全域木を持つとは限りません。たとえば、非可算個の頂点を持つ完全グラフは正規全域木を持ちません。完全グラフの正規全域木はパスにしかなり得ませんが、パスは可算個の頂点しか持ちません。しかし、可算個の頂点を持つ連結グラフはすべて正規全域木を持ちます。^{[ 3 ] [ 4 ]}

可算グラフであっても、深さ優先探索では最終的にグラフ全体を探索できない可能性があり、^{[ 3 ]}また、すべての正規全域木が深さ優先探索によって生成されるわけではありません。深さ優先探索木であるためには、可算正規全域木は無限パスが 1 つだけ、または無限に多くの子を持つノードが 1 つだけ存在する必要があります (両方ではありません)。

無限グラフの場合${\displaystyle G}$は正規全域木を持ち、連結グラフマイナーはすべて正規全域木を持ちます。${\displaystyle G}$このことから、正規全域木を持つグラフは、禁止マイナーによって特徴付けられることがわかる。禁止マイナーの 2 つのクラスのうちの 1 つは、二部グラフの一方の側が可算で、もう一方の側が非可算であり、すべての頂点の次数が無限であるような二部グラフである。禁止マイナーのもう 1 つのクラスは、アロンシャイン木から派生した特定のグラフである。^{[ 12 ]}

この特徴付けの詳細は、数学を形式化するために使用される集合論的公理化の選択に依存します。特に、マーティンの公理が真であり、連続体仮説が偽である集合論のモデルでは、この特徴付けにおける二部グラフのクラスは、単一の禁止マイナーに置き換えることができます。しかし、連続体仮説が真であるモデルでは、このクラスにはマイナー順序で互いに比較できないグラフが含まれます。^{[ 13 ]}

正規全域木は、無限グラフの端点とも密接に関連しており、直感的には同じ方向に無限に伸びる無限パスの同値類です。グラフが正規全域木を持つ場合、この木はグラフの各端点に対してちょうど1つの無限パスを持つ必要があります。^{[ 14 ]}

無限グラフは、グラフ自体を単体複体とみなし、グラフの両端に無限遠点を追加することで、位相空間を形成するために使用できます。この位相では、グラフの頂点の集合が可算個の閉集合の和集合に分解できる場合に限り、グラフは正規全域木を持ちます。さらに、この位相空間は、グラフが正規全域木を持つ場合に限り、距離空間で表現できます。 ^{[ 14 ]}