グラフマイナー

グラフ理論では、無向グラフ H がグラフG のマイナーグラフであるとは、辺と頂点を削除し、辺を縮小することによってGから形成できる場合を指します。

グラフマイナーの理論は、グラフが平面的であるためには、そのマイナーが完全グラフK ₅も完全二部グラフK _{3,3 も}含まないというワグナーの定理から始まった。^[1]ロバートソン・シーモア定理は、削除や辺の縮約によって保存されるグラフのあらゆる特性に対して、類似の禁制マイナー特性が存在することを意味している。 ^[2] 固定されたあらゆるグラフHに対して、 Hが入力グラフGのマイナーであるかどうかを多項式時間でテストすることができる。^[3]禁制マイナー特性と合わせて、これは、削除や縮約によって保存されるあらゆるグラフ特性が多項式時間で認識できることを意味する。^[4]

グラフマイナーに関する他の結果と予想には、グラフ構造定理（これによれば、 H をマイナーとして持たないグラフはより単純な部分を接着することによって形成される）や、グラフを着色できないことと、そのマイナーとして大きな完全グラフが存在することとを関連付けるハドヴィガーの予想などがある。グラフマイナーの重要な変種には、位相マイナーと浸漬マイナーがある。

辺の縮約とは、グラフから辺を削除すると同時に、その辺が接続に使用した 2 つの頂点を結合する操作です。無向グラフ Hは、いくつかの辺を縮約し、いくつかの辺を削除し、いくつかの孤立した頂点を削除することで、 GからHと同型のグラフを取得できる場合、別の無向グラフGのマイナーです。このような縮約と削除のシーケンスがGで実行される順序は、結果のグラフHには影響しません。

グラフマイナーは、マトロイドマイナーのより一般的な文脈で研究されることが多い。この文脈では、すべてのグラフが接続されており、自己ループと複数のエッジが許可されている（つまり、単純なグラフではなくマルチグラフである）と想定するのが一般的である。ループの縮小とカットエッジの削除は禁止された操作である。この観点には、エッジの削除によってグラフのランクが変わらず、エッジの縮小によって常にランクが 1 減少する という利点がある。

他の文脈（擬似森林の研究など）では、カットエッジの削除を許可し、切断されたグラフを許可するが、多重グラフを禁止する方が理にかなっています。グラフマイナー理論のこのバリエーションでは、グラフは、エッジの縮小後に常に単純化され、自己ループと多重エッジが削除されます。^[5]

関数fは、 H がGのマイナー関数である場合に、 f ( H ) ≤ f ( G )が成り立つとき、 「マイナー単調」と呼ばれます。

次の例では、グラフHはグラフGのマイナーです。

H.

G.

次の図はこれを示しています。まず、破線のエッジ (および結果として生じる孤立した頂点) を削除してGのサブグラフを作成し、次に灰色のエッジを縮小します (接続する 2 つの頂点を結合します)。

グラフマイナー関係が有限無向グラフの同型類上で半順序を形成することは簡単に検証できる。つまり、グラフマイナー関係は推移的であり（ GのマイナーのマイナーはG自身のマイナーである）、非自明なマイナー演算は辺や頂点を削除するため、 GとH は同型である場合にのみ互いのマイナーになり得る。ニール・ロバートソンとポール・シーモアによる深い結果では、この半順序は実際にはよく準順序付けであると述べている。有限グラフの無限リスト（G ₁、G ₂、…）が与えられた場合、常に 2 つのインデックスi < jが存在し、 G _{i は}G _jのマイナーである。これを述べる別の同等の方法は、グラフの任意のセットは、マイナー順序付けの下で有限個の最小要素のみを持つことができる、ということである。^{[6]この結果は、}クラウス・ワーグナーにちなんでワーグナー予想として以前知られていた予想を証明した。ワーグナーはずっと以前からこの仮説を立てていたが、1970年に初めて発表した。^[7]

証明の過程で、シーモアとロバートソンはグラフ構造定理も証明している。この定理では、任意の固定グラフHについて、 H をマイナーとして持たない任意のグラフの大まかな構造を決定する。定理の記述自体は長くて複雑であるが、簡単に言えば、そのようなグラフは、種数が制限された曲面に埋め込まれたグラフからわずかに修正されたより小さなグラフのクリーク和の構造を持つ必要があることを証明している。このように、彼らの理論は、グラフマイナーとグラフの位相的埋め込みとの間の基本的な関係を確立している。^[8]

任意のグラフHについて、単純なHマイナーフリーグラフはスパース、つまり辺の数が頂点数の定数倍よりも少ない必要があります。^[9]より具体的には、Hにh 個の頂点がある場合、単純なn頂点の単純なHマイナーフリーグラフは最大で個の辺を持つことができ、いくつかのK _hマイナーフリーグラフは少なくともこの数の辺を持ちます。^{[10]したがって、} H にh個の頂点がある場合、Hマイナーフリーグラフは平均次数を持ち、さらに退化 を持ちます。 さらに、Hマイナーフリーグラフには、平面グラフの平面セパレータ定理に似たセパレータ定理があります。つまり、任意の固定されたHと任意のn頂点のHマイナーフリーグラフGについて、頂点の削除によってGが 2 つの (おそらく切断された) サブグラフに分割され、サブグラフあたり最大で2 n ⁄ 3 個の頂点を持つような頂点のサブセットを見つけることができます。 ^[11]さらに強いことに、任意のHに対して、Hマイナーフリーグラフは木幅を持つ。^[12]${\displaystyle \scriptstyle O(nh{\sqrt {\log h}})}$ ${\displaystyle \scriptstyle O(h{\sqrt {\log h}})}$ ${\displaystyle \scriptstyle O(h{\sqrt {\log h}})}$${\displaystyle \scriptstyle O({\sqrt {n}})}$ ${\displaystyle \scriptstyle O({\sqrt {n}})}$

グラフ理論におけるハドヴィガー予想は、グラフG がk頂点上の完全グラフと同型のマイナーグラフを含まない場合、G はk – 1色で適切な彩色を持つというものである。^[13] k = 5の場合は、 4 色定理の言い換えである。ハドヴィガー予想はk ≤ 6に対して証明されているが^[14]、一般的なケースでは不明である。ボロバス、カトリン、エルデシュ (1980) はこれを「グラフ理論における最も深い未解決問題の一つ」と呼んでいる。4 色定理とグラフマイナーグラフを関連付けるもう 1 つの結果は、ロバートソン、サンダース、シーモア、トーマスによって発表されたスナーク定理である。これは、 WT タットによって予想された 4 色定理を強化したもので、辺​​彩色に 4 色を必要とするブリッジのない3 正則グラフは、ピーターセングラフをマイナーとして持たなければならないことを述べている。 ^[15]

多くのグラフ族は、 F内のグラフのすべてのマイナーがF内にも存在するという性質を持ちます。このようなクラスはマイナー閉であると言われています。たとえば、任意の平面グラフ、または固定された位相面上のグラフの任意の埋め込みでは、エッジの削除もエッジの縮小も埋め込みの種数を増やすことはできません。したがって、平面グラフと任意の固定面上に埋め込み可能なグラフはマイナー閉族を形成します。

Fがマイナー閉族である場合、（マイナーの準順序付けの性質により）Fに属さないグラフの中に、マイナー極小グラフの有限集合Xが存在する。これらのグラフはFの禁制マイナーである。つまり、グラフがFに属するのは、 Xのいかなるグラフもマイナーとして含まないときのみである。つまり、すべてのマイナー閉族Fは、禁制マイナーの有限集合Xに対するXマイナーフリーグラフの族として特徴付けることができる。 ^[2] このタイプの特徴付けの最もよく知られた例は、平面グラフを K ₅も K _3,3もマイナーとして持たないグラフとして特徴付けるワーグナーの定理である。^[1]

場合によっては、マイナー閉族のグラフの特性はその排他的マイナーの特性と密接に関係していることがあります。たとえば、マイナー閉グラフ族Fがパス幅を制限される場合、その禁制マイナーにフォレストが含まれます。[16] F が木の深さを制限される場合、その禁制マイナーにパスグラフの互いに素な和が含まれます。[17] F が木幅を制限される場合、その禁制マイナーに^平面グラフが含まれます。 [ ^17] Fがローカル木幅を制限される場合（直径と木幅の間の関数関係）は、禁制マイナーに頂点グラフ（単一の頂点を削除することで平面にできるグラフ）が含まれる場合に限ります。^[18] H が平面上に単一の交差のみで描画できる場合（つまり、交差数が1 の場合）、Hマイナーフリーグラフには、平面グラフと制限された木幅のグラフのクリーク和として形成されるという簡略化された構造定理があります。^[19]たとえば、K ₅とK _3,3はどちらも交差数が 1 であり、ワグナーが示したように、 K ₅フリーグラフは平面グラフの 3 クリーク和と 8 頂点のワグナーグラフに正確に相当し、K _{3,3フリーグラフは平面グラフと}K ₅の 2 クリーク和に正確に相当します 。^[20]

グラフHの細分がグラフGのサブグラフと同型である場合、グラフHはグラフGの位相マイナーと呼ばれます。^[21]すべての位相マイナーはマイナーでもあります。ただし、その逆は一般には当てはまりません (たとえば、ピーターセングラフの完全グラフK ₅はマイナーですが、位相マイナーではありません)。ただし、最大次数が 3 以下のグラフには当てはまります。^[22]

位相的マイナー関係は有限グラフの集合上の準整列関係ではないため^{[23] 、RobertsonとSeymourの結果は位相的マイナーには適用されない。しかし、k本の出枝を持つすべての枝集合を、少なくとも2のダウン次数を持つ}k本の葉を持つすべての木に置き換えることによって、有限禁制の位相的マイナー特徴付けから有限禁制の位相的マイナー特徴付けを構築するのは簡単である。

グラフHは、​​グラフGの誘導サブグラフから辺を縮約することで得られる場合、グラフGの誘導マイナーと呼ばれます。そうでない場合、GはH誘導マイナーフリーであると言われています。 ^[24]

リフティングと呼ばれるグラフ操作は、イマージョンと呼ばれる概念の中心です。リフティングは、隣接するエッジに対する操作です。3 つの頂点v、u、w があり、(v,u)と(u,w)がグラフ内のエッジである場合、vuw、または(v,u)、(u,w)に相当するリフティングは、2 つのエッジ(v,u)と(u,w)を削除し、エッジ(v,w)を追加する操作です。 (v,w) がすでに存在する場合、 vとw は複数のエッジで接続されるため、この操作は本質的にマルチグラフ操作です。

グラフGから一連のリフティング操作 ( G上) と同型サブグラフの検出によってグラフHを取得できる場合、 HはGの浸漬マイナーであるといいます。浸漬マイナーを定義する別の方法があり、これはリフティング操作と同等です。 H の頂点からGの頂点への単射写像が存在し、 Hの隣接要素の像が辺が互いに素なパスによって G で接続される場合、HはGの浸漬マイナーであるといいます。

浸漬マイナー関係は有限グラフの集合上の準整列関係であり、したがって Robertson と Seymour の結果は浸漬マイナーに適用されます。これはさらに、すべての浸漬マイナー閉族が禁制浸漬マイナーの有限族によって特徴付けられることを意味します。

グラフ描画では、非平面グラフの平面化として浸漬マイナーが出現する。平面上の交差のあるグラフの描画から、各交差点を新しい頂点に置き換え、その過程で交差する各辺をパスに細分化することで浸漬マイナーを形成することができる。これにより、平面グラフの描画方法を非平面グラフに拡張することができる。^[25]

グラフGの浅いマイナーとは、マイナーを形成するために縮約されたGの辺が、直径が小さい互いに素なサブグラフの集合を形成するマイナーである。浅いマイナーは、グラフマイナーとサブグラフの理論の間を補間するものであり、深さが深い浅いマイナーは通常のタイプのグラフマイナーと一致し、深さが 0 の浅いマイナーはまさにサブグラフである。^[26]また、グラフマイナーの理論を、マイナーを取ることに関して閉じていない1 平面グラフなどのグラフのクラスに拡張することも可能になる。 ^[27]

グラフマイナーの別の同等の定義は、Hの頂点が G の頂点互いに素な部分木の集合で表すことができる場合、つまり、 H 内で 2 つの頂点が隣接している場合、 G 内の対応する 2 つの木に端点を持つ辺が存在する場合、 H は G のマイナーであるということである。奇数マイナーは、これらの部分木にパリティ条件を追加することで、この定義を制限します。H が上記のようにGの部分木の集合で表されている場合、部分木内のGの各辺が適切に色付けされ (端点が異なる色になる)、2 つの部分木間の隣接関係を表すGの各辺が単色になる (両方の端点が同じ色になる)ように、Gの頂点に 2 つの色を割り当てることができる場合はいつでも、 H はGの奇数マイナーです。通常の種類のグラフマイナーとは異なり、禁制の奇数マイナーを持つグラフは必ずしもスパースではありません。^[28] k-彩色グラフは必ずk-頂点完全グラフをマイナーとして含むというハドヴィガー予想も奇数マイナーの観点から研究されてきた。^[29]

グラフマイナーの概念のパリティベースの拡張として、二部マイナーの概念がある。これは、開始グラフが二部グラフである場合に常に二部グラフを生成する。グラフH は、グラフ G から頂点を削除し、辺を削除し、グラフの周辺サイクルに沿って互いに距離 2 にある頂点のペアを折りたたむことによって G から得られる場合に、他のグラフGの二部マイナーである。ワグナーの定理の形式は二部マイナーにも適用される。二部グラフGが平面グラフである場合、それは二部マイナーとしてユーティリティグラフK _3,3を持たない。^[30]

グラフG がH をマイナーとして含んでいるかどうかを決定する問題は、一般に NP 完全である。たとえば、 H がGと同じ数の頂点を持つサイクルグラフである場合、G がハミルトンサイクル を含んでいる場合に限り、HはGのマイナーである。しかし、G が入力の一部であるがHが固定されている場合、多項式時間で解くことができる。より具体的には、この場合HがGのマイナーであるかどうかをテストするための実行時間はO ( n ³ ) である。ここで、 n はGの頂点数であり、大きな O 表記はHに超指数的に依存する定数を隠している。^{[3]オリジナルの Graph Minors の結果以来、このアルゴリズムは}O ( n ² ) 時間に改善されている。^{[31]したがって、与えられたグラフに禁制マイナーのいずれかが含まれているかどうかをテストするための多項式時間アルゴリズムを適用することにより、}多項式時間で任意のマイナー閉族のメンバーを認識することが理論的に可能である。この結果は実際には使われていない。なぜなら、隠れた定数が非常に大きい（表現するにはクヌースの上矢印記法の3層が必要）ため、いかなる応用も不可能であり、銀河アルゴリズムになってしまうからである。^[32] さらに、この結果を建設的に応用するためには、グラフ族の禁制小数が何であるかを知る必要がある。^[4]禁制小数が既知であるか、計算できる場合もある。^[33]

Hが固定された平面グラフである場合、入力グラフGにおいてHがGのマイナーであるかどうかを線形時間でテストすることができる。^[34] Hが固定されていない場合、 Gが平面である場合のより高速なアルゴリズムが知られている。^[35]

• ワイスタイン、エリック・W.「グラフ・マイナー」。マスワールド。