グラフ構造定理

数学において、グラフ構造定理はグラフ理論の分野における重要な成果である。この成果は、グラフマイナー理論と位相的埋め込みの間に深く根本的なつながりを確立する。この定理は、ニール・ロバートソンとポール・シーモアによる23本の論文シリーズの17番目に述べられている。その証明は非常に長く複雑である。Kawarabayashi & Mohar (2007)およびLovász (2006)は、専門家以外の人にも理解しやすい概説であり、定理とその帰結について説明している。

定理の設定と動機

グラフ $G$ のマイナーとは、いくつかの辺を縮約することで $G$ のサブグラフから得られるグラフと同型のグラフ $H$ のことです。G がグラフ H をマイナーとして持た $ない$ $場合$ 、 G $は$ $H$ フリーであると言えます。H $を$ 固定グラフとします。直感的には、 $G が$ 巨大な H フリーグラフである $場合$ 、これには「十分な理由」があるはずです。グラフ構造定理は、そのような「十分な理由」を $G$ の構造の大まかな説明の形で提供します。本質的に、すべての $H$ フリーグラフ $G は$ 、 2 つの構造上の欠陥のいずれかを抱えています。つまり、 $Gが$ $H を$ マイナーとして持つには「薄すぎる」か、 $G が(ほぼ) 位相的に$ $H を$ 埋め込むには単純すぎる表面に埋め込まれる可能性があるかのどちらかです。最初の理由は $H が$ 平面グラフである場合に当てはまり、 $H$ が平面でない場合は両方の理由が当てはまります。まず、これらの概念を明確にします。

木の幅

グラフ $G$ のツリー幅は、 $G$ の「細さ」を指定する正の整数です。たとえば、連結グラフ $G の$ ツリー幅が 1 になるのは、それがツリーである場合に限ります。また、 $G の$ ツリー幅が 2 になるのは、それが直列並列グラフである場合に限ります。直感的には、巨大グラフ $G の$ ツリー幅が小さいのは、 $G が$ 、ノードとエッジが小さなグラフに置き換えられた巨大ツリーの構造をとる場合のみです。ツリー幅の正確な定義は、クリーク和に関するサブセクションで示します。定理として、 $H が$ $G$ のマイナーである場合、 $H$ のツリー幅は $G$ のツリー幅より大きくないということです。したがって、 $Gが$ $H$ フリーである「十分な理由」の 1 つは、 $G$ のツリー幅がそれほど大きくないことです。グラフ構造定理は、この理由が $H が$ 平面グラフである場合に常に当てはまることを意味しています。

系 1.すべての平面グラフ $Hに対して、すべての$ $Hフリーグラフのツリー幅が$ $k$ 未満になるような正の整数 $k$ が存在する。

残念なことに、系 1 の $kの値は一般に$ $H$ のツリー幅よりもはるかに大きくなります(注目すべき例外は、 $H = K 4$ 、つまり 4 つの頂点を持つ完全グラフで、この場合は $k = 3 です)。これが、グラフ構造定理が$ $H$ フリーグラフの「大まかな構造」を記述すると言われる理由の 1 つです。

表面埋め込み

大まかに言えば、曲面は円板の局所的な位相構造を持つ点の集合です。曲面は 2 つの無限族に分類されます。有向曲面には球、トーラス、二重トーラスなどが含まれ、無向曲面には実射影平面、クラインの壺などがあります。グラフが曲面に埋め込まれるのは、辺と頂点が入射または隣接している場合を除き、互いに交差または接触しない点 (頂点) と弧 (辺) の集合としてグラフを曲面上に描画できる場合です。グラフが球面に埋め込まれている場合、そのグラフは平面です。グラフ $Gが特定の曲面に埋め込まれている場合、$ $G$ のすべてのマイナーもその同じ曲面に埋め込まれます。したがって、 $Gが$ $H$ フリーである「十分な理由」は、 $H が$ 埋め込まれていない曲面に $G が$ 埋め込まれていることです。

$H$ が平面でない場合、グラフ構造定理はクラトフスキー定理の広範な一般化として見ることができます。 Wagner (1937) によって証明されたこの定理のバージョンは、グラフ $Gが$ $K 5$ フリーかつ $K 3,3$ フリーである場合、 $G は$ 平面であると述べています。この定理は、グラフ $G が$ マイナーとして $K 5$ または $K 3,3 を$ 持たない「十分な理由」を提供します。具体的には、 $G は$ 球面に埋め込まれますが、 $K 5$ も $K 3,3 も$ 球面に埋め込まれません。残念ながら、この「十分な理由」の概念は、グラフ構造定理には十分に洗練されていません。クリーク和と渦という 2 つの概念がさらに必要です。

クリークサム

グラフ $G$ 内のクリークは、 $G$ 内で互いに隣接する任意の頂点の集合です。非負の整数 $k$ に対して、2 つのグラフ $G$ と $Kの$ $k$ クリーク和は、非負の整数 $m$ $\leq$ $k$ $を選択し、 G$ と $K$ のそれぞれでサイズ $m$ のクリークを選択し、 2 つのクリークをサイズ $m$ の単一のクリークとして識別し、新しいクリーク内の頂点を結合する 0 個以上の辺を削除することによって得られる任意のグラフです。

$G 1 、 G 2 、\dots、 G n が$ グラフのリストである場合、 $k$ -クリーク和を介してグラフのリストを結合することにより、新しいグラフを作成できます。つまり、 $G$ $1$ と $G$ $2$ $のk$ -クリーク和を取り、次に結果のグラフで $G$ $3$ $のk$ -クリーク和を取り、これを繰り返します。グラフのリストから $k$ -クリーク和を介して取得できる場合、グラフのツリー幅は最大で $k$ になります。リスト内の各グラフには最大で $k$ $+ 1$ 個の頂点があります。

系 1 は、H が平面である場合、小さなグラフの k クリーク和が H フリーグラフの大まかな構造を記述することを示しています $。H$ $が$ 非 $平面$ の場合 $、$ それぞれが表面に埋め込まれているグラフのリストの $k$ クリーク和も考慮する必要があります。H $=$ $K$ $5$ の次の例は、この点を示しています。グラフ $K$ $5は$ $、$ 球を除くすべての表面に埋め込まれます。ただし、平面からはほど遠い $K$ $5$ フリーグラフが存在します。特に、平面グラフの任意のリストの 3 クリーク和は、 $K$ $5$ フリーグラフになります。Wagner (1937) は、 Wagner の定理として知られる一連の結果の一部として、 $K$ $5$ フリーグラフの正確な構造を決定しました。

定理 2. $G$ が $K 5$ フリーである場合、 $G は$ 、平面グラフのリストからの 3 クリーク和と、8 頂点を持つ 1 つの特別な非平面グラフのコピーを介して取得できます。

$定理 2 は、 K$ $5$ フリーグラフの正確な構造が決定されているため、正確な構造定理であることを指摘します。このような結果はグラフ理論ではまれです。ほとんどのグラフ $Hでは、$ $H$ フリーグラフの構造記述に $Hフリーでは$ ないグラフがいくつか含まれるため、グラフ構造定理はこの意味では正確ではありません。

渦（大まかな説明）

定理 2 の類似が $K$ $5$ 以外のグラフ $H$ にも当てはまると推測したくなるかもしれません。おそらく、次のことは真実です。任意の非平面グラフ $H$ に対して、正の整数 $k$ が存在し、すべての $Hフリーグラフは、最大で$ $k 個の頂点を持つか、$ $H が$ 埋め込まれていない表面に埋め込まれているグラフのリストから $k$ クリーク和を介して取得できます。残念ながら、このステートメントはまだ十分に洗練されていないため、真実ではありません。各埋め込みグラフ $G$ $i が$ 2 つの限られた方法で「ごまかす」ことを許可する必要があります。まず、限られた複雑さで互いに交差することが許可されているいくつかの新しい頂点と辺を追加できる表面上の場所を制限された数だけ許可する必要があります。このような場所は渦と呼ばれます。渦の「複雑さ」は、パス幅と密接に関連する深さと呼ばれるパラメーターによって制限されます。読者は、深さ $k$ の渦に関する次の正確な説明を読むのを延期することを好むかもしれません。次に、渦を含む埋め込みグラフのそれぞれに、限られた数の新しい頂点を追加できるようにする必要があります。

渦（正確な定義）

埋め込みグラフの面は、グラフから分離しているが、境界が埋め込みグラフのいくつかの辺の和集合である、表面上の開いた 2 セルです。埋め込みグラフ $G$ の面を $F$ とし、 F の境界上にある頂点を(円形の順序で) $v$ $0$ $、$ $v$ $1$ $、 ...、$ $v$ $n$ $- 1$ 、 $v$ $n$ $=$ $v$ $0$ とします。 $F$ の円形区間は、形式 ${$ $v$ $a$ $、$ $v$ $a$ $+1$ $、 \dots、$ $v$ $a$ $+$ $s$ の頂点の集合です。ここで、 $a$ と $sは整数で、添え字は$ $n を$ 法として約分されます。 $Λ を$ $F$ $の$ 円形区間の有限リストとします。次のようにして新しいグラフを構築します。 $Λ$ 内の各円形区間 $Lに対して、$ $L$ 内の 0 個以上の頂点に結合する新しい頂点 $v$ $L$ を追加します。最後に、 $Λ$ 内の区間の各ペア ${$ $L$ $,$ $M$ $}について、$ $L$ と $M$ の交差が空でない場合、 $v$ $L$ と $v$ $M$ を結ぶ辺を追加できます。結果のグラフは、 $F$ の境界上の頂点が $Λ内の$ $k を$ 超える区間に現れない場合、深さが最大 $k$ の渦を(面 $F$ に) 追加することによって $G$ から取得されたと言えます。