0. 概要
グラフマイナー定理とは
有限グラフの全体は, マイナー順序によってよい擬順序になっている (well-quasi-ordered)
という定理です.
...さてこれは何を言ってるんでしょうか. 本記事では現代のグラフ理論において最も重要な定理の一つであるグラフマイナー定理について、その中身と研究背景をグラフ理論の観点から可能な限りちゃんと書いていきたいと思います. なお本記事では「グラフ」とは単に有限グラフのことを指すこととします. また, 頂点にラベルは付いていないものとします.
章の構成は以下です. グラフマイナー定理の凄さをアピールする記事なので, 研究背景の説明に重きをおいています. 内容を知りたい方は4章から読んでください.
- 1~3章 : グラフマイナー定理の研究背景
- 4章 : グラフマイナー定理の内容の説明
- 5章 : 木に関するグラフマイナー定理
1. 平面グラフのマイナーによる特徴づけ
グラフマイナー定理について説明する前にその研究動機について説明したいと思います.
世の中には様々なグラフがありますが, その中でも平面グラフと呼ばれる種類のグラフがあり, これまで多くの研究がなされてきました. 平面グラフとはグラフを紙面上に辺を交差せずに描けるようなグラフのことを指します. 数学的には球への埋め込みを使って定義されます.
 |
| 図1: 左のグラフは一見すると中央で辺が交差しているように見えますが, 右のように描くことにより交差せずに描けるので, このグラフは平面グラフです. |
 |
| 図2: 左のグラフは $K_5$, 右のグラフは $K_{3,3}$. どちらのグラフも平面グラフではない. |
図1のグラフはどちらも「4つの頂点を持ち, どの頂点ペアも辺で結ばれているようなグラフ」です. このグラフを頂点数4の完全グラフと呼び, $K_4$と表記します. $K_4$は図1右のように描けば辺を交差させずに平面上に描くことが出来ます.
一方で $K_5$ (図2左) はどうかというと, 実はどんなに頑張っても決して辺を交差させずに平面上に描くことは出来ません. また, 図2右のグラフは「上と下に三つずつ頂点をもち, 上の頂点と下の頂点のペアはどれも辺で結ばれている」グラフです. このグラフは上下に三つずつ頂点があるので $K_{3,3}$と表記します (完全二部グラフとも呼ばれます) このグラフも実は平面グラフでないことを証明することが出来ます. 証明は例えば高校数学の美しい物語に載っています.
さて, 与えられたグラフが平面的であるかどうか をどうやって判定すれば良いでしょうか. 実はこの問題はグラフの頂点数 $n$ に対して $O(n)$時間で解くことが出来ます [1].
そのアルゴリズムで使われている定理が Kuratowski の定理 です. この定理は平面グラフの特徴づけを与えている定理で, 次のようなものです:
定理 (Kuratowski, 1930)
グラフ$G$が平面グラフであることの必要十分条件は, $G$が$K_5$と$K_{3,3}$の細分を部分グラフとして含まないことである.
ここでグラフ$H$の細分とは, $H$の辺をいくつか指定して, それぞれの辺を任意の長さ(ただし1以上)のパスに置き換えて得られるグラフです. 具体的には次の図を見てください.
 |
| 図3: $K_4$の細分の例です. (上):太線で書かれた辺を長さ3のパスに置き換えています. (下):選択する辺は複数本でもよく, 更にそれぞれ異なる長さのパスに置換しても良いです. |
グラフ$G$がグラフ$H$を部分グラフとして含む, というのは $E(G),\,E(H)$ をそれぞれ $G,\,H$ の辺集合としたときに, $E(H) \subseteq E(G)$ となることを言います. $G$から頂点と辺を何本か取り除くと $H$ が得られる, と言い換えることも出来ます.
$K_5$の細分と$K_{3,3}$の細分を部分グラフとして含まない, というのは中々強い要請であることが分かります. 例えば, これらの細分を含むようなグラフは必ず次数3以上の頂点を4つ以上持つため, 「次数3以上の頂点が高々3つならば, そのグラフは平面グラフである」ということが証明できたりするわけです(*).
(*): グラフ $G$ が グラフ $H$ の細分を部分グラフとして含むとき, $G$ は $H$ を 位相的マイナーとして含む, と言うこともあります.
また, Kuratowski の定理と似たような平面グラフの特徴づけの定理が次に示す Wagner の定理です.
定理 (Wagner, 1937)
グラフ$G$が平面グラフであることの必要十分条件は, $G$が$K_5$と$K_{3,3}$をマイナーとして含まないことである.Kuratowski の定理と似ていますがこちらには「マイナー」という単語が出てきています.
グラフ $G$ がグラフ $H$ をマイナーとして含む, というのは, $G$ の適当な部分グラフ $F$ が存在して, $H$は$F$の有限回の縮約操作によって得られる, という意味です (図4).
 |
| 図4: $G$ のある部分グラフ $F$ から縮約操作によって $H$ が得られている. このとき $G$ は $H$ をマイナーとして含むという. |
縮約操作とは, 辺を一つ指定してその両端点にある頂点の一つの頂点に合体させる操作を指します. 自己ループや多重辺の生じうるものとします. 次の図を見てください.
 |
| 図5: 右のグラフが縮約後のグラフになります. |
すなわち, $G$ から頂点と辺を幾つか除いた後に辺の縮約を行うことによって $H$ が得られたとき, $G$ は $H$ をマイナーとして含む, ということになります.
さて, Wagner の定理により, $G$が平面グラフであることの必要十分条件とは, $G$の適当な部分グラフ$H$が存在して, $H$に適当な縮約操作を繰り返してやると $K_5$ または $K_{3,3}$ が得られる, ということになります. このように 「グラフ $X$ をマイナーとして含まない」ようなグラフの族 $\mathcal{G}$ に対して $X$ を $\mathcal{G}$ の禁止マイナーと呼ぶこともあります. 今回で言えば, $K_5$ と $K_{3,3}$ は平面グラフの禁止マイナーということになります.
2. 四色定理 ～Wagnerのアプローチ, Hadwiger 予想～
この章は少し蛇足気味です. 飛ばして読んでもかまいません. 当時のグラフ理論界では「四色問題」が大ブームでした. 四色問題とは次のような問題です:
四色問題
平面グラフは4-彩色可能である.彩色とは, グラフの頂点に色を塗ることですが, 条件として隣接する頂点同士は異なる色で塗らなければなりません. グラフ $G$ が $k$ 色で彩色できる場合は, $G$ は $k$-彩色可能である と言ったりします. $k$ 色で彩色可能ならば $k+1$ 色で彩色することも明らかに可能なので, グラフ $G$ を彩色するのに必要な色の種類数を定義することができます. この値を 彩色数 と呼び, $\xi(G)$ と表します.
Wagner は 平面グラフのマイナーによる特徴付けというアプローチから四色問題に取り組んでいました. 結論から言うと失敗するのですが, このときに「$K_5$ をマイナーとして含まないグラフはどのようなグラフか」という問題に対して Wagner の分解定理 と呼ばれる有名な定理を示しています.
例えば, $K_2$ をマイナーとして含まないグラフというのは 「辺を含まないグラフ」であり, $K_3$ をマイナーとして含まないグラフというのは, 森 (閉路を含まないグラフ) となります.
ここで重要なのは, これまでの結果として
- $K_2$をマイナーとして含まないグラフは 1-彩色可能
- $K_3$をマイナーとして含まないグラフは 2-彩色可能
- $K_4$をマイナーとして含まないグラフは 3-彩色可能
- $K_5$をマイナーとして含まないグラフは 4-彩色可能
ということが示されたことです. では,
$K_{t+1}$ をマイナーとして含まないグラフは $t$-彩色可能 なのでしょうか？
この予想は Hadwiger 予想と呼ばれるもので, グラフ理論の最重要かつ最難な未解決問題といわれています. (今なお未解決です)
3. Wagner 予想
2.で述べたように, Wagner は 四色問題を解決するために, 平面グラフをマイナー (縮約) という概念からアプローチしていました. その結果として, 平面グラフを二つの禁止マイナーによって特徴付けることに成功しました.
 |
| 図6: 平面グラフを縮約しても平面グラフのままである. |
ところで, 上の図から分かるように, 平面グラフは縮約操作に関して閉じているということが分かります. つまり平面グラフに対して縮約操作を行って得られたグラフもまた平面グラフです. 即ち平面グラフの全体はマイナーに関して閉じています.
一般に, グラフ族 $\mathcal{G}$ に対して, 任意のグラフ $G \in \mathcal{G}$ に対して, $G$に縮約操作を行って得られるグラフもまた $\mathcal{G}$ に属するとき, $\mathcal{G}$ をマイナーに関して閉じている (minor closed) と言います.
例えば $\mathcal{G}$ として「トーラスに埋め込むことの出来るグラフ全体」「射影平面に埋め込むことの出来るグラフ全体」などはマイナーに関して閉じています. これらのグラフは 禁止マイナーを使って特徴付けられるでしょうか？ つまりマイナーに関して閉じているようなグラフ族 $\mathcal{G}$ 及び任意のグラフ $G$に対し,
$G \in \mathcal{G}$ であることと $G$ は $X_1,\,X_2,\,\ldots$ をマイナーとして含まない ことは必要十分条件である.
となるようなグラフの集合 ${\bf X} := X_1,\,X_2,\,\ldots$ をとることは可能なのでしょうか？
$X$が無限集合でも良い場合は明らかに, ${\bf X}$ を $\mathcal{G}$に含まれないグラフの全体 とすることによって条件を満たすことが出来ます. でも平面グラフの場合は, ${\bf X}=\{K_5,\,X_{3,3}\}$ と有限集合で取ることが出来ました.
実は先ほどの例で挙げた 「トーラスに埋め込むことの出来るグラフ全体」「射影平面に埋め込むことの出来るグラフ全体」は有限個の禁止マイナーで特徴付けられることが証明されています. そこで出てきたのが次のWagner 予想 です.
予想 (Wagner)
マイナーに関して閉じているようなグラフ族は, 有限個の禁止マイナーで特徴付けることが出来る.
この予想はグラフ理論の難しい未解決問題として知られていました. しかしSeymour と Robertson の二人が 1984年に「木分解」と呼ばれる斬新なテクニックを用いてこの予想を肯定的に解決しました. この二人が示したのが次に示す主張で, 現在ではこの主張を「グラフマイナー定理」と呼ばれます.
定理 (Seymour, Robertson, 2004)
グラフの全体はマイナー順序によって, よい擬順序付けられている.そしてこの定理と Wagner 予想 が同値であるので, めでたく Wagner 予想が肯定的に解決された, ということになります.
この二人は1984年に Wagner 予想の解決を発表してから 2004年まで, 通算で500ページにもわかる長大な論文を20年もかけて書き上げました. こうして証明されたグラフマイナー定理から得られる系は沢山あり, グラフ理論のみならず組合せ最適化の分野にも影響を及ぼしました.
4. グラフマイナー定理
3章までがグラフマイナー定理の誕生の動機でしたが, 本章からはその内容について書いていきます.
4.1. マイナー順序
数学においてはしばし「順序関係」という言葉が使われます. 一般には数の大小や単語の辞書式順序などの意味でよく使われると思いますが, 今回は グラフの順序 として, マイナー順序というのを考えます. 順序については こちらの記事 で用語の解説を書いています.
定義 (マイナー順序)
二つのグラフ $G,\,H$ に対し, $H$が$G$をマイナーとして含むとき, $G \preceq H$ と表す. この順序 $\preceq$ を マイナー順序と呼ぶ.全順序は以下の四つの公理を満たすような順序でした:
- $a \preceq a$. (反射律)
- $a \preceq b,\,b \preceq c$ ならば $a \preceq c$. (推移律)
- $a \preceq b$ かつ $b \preceq a$ ならば, $a=b$ (反対称律)
- 任意の $a,b$ に対して $a \preceq b$ もしくは $b \preceq a$ のどちらかが成り立つ (全順序律)
しかしマイナー順序は全順序ではありません. 例えば $K_5$ と $K_{3,3}$ は一方が他方をマイナーとして含むようなことはないので, この順序では比較できません. このようなペアのことを 比較不能対 と呼ぶことにします. 有限グラフ上のマイナー順序は上に挙げた中で 1,2,3が成り立つので, この順序は半順序です. が, 今回では参考文献[2]に従って 擬順序 として考えることにします.
4.2. よい擬順序 (well-quasi-order)
順序集合 $(X, \leq)$ で $\leq$ が擬順序 になっていて, 更に $X$ が無限集合であるようなものを考えます. 例えば $X$ として 平面グラフの全体, $\leq$ として マイナー順序 とするのが良いでしょう. $X$ 上の無限列 $(x_1,x_2,\ldots)$ を考えます. この列が よい列 (good) であるとは, あるインデックス $i<j$ が存在して $x_i \leq x_j$ となることをいいます. そして $X$ 上の任意の無限列が よい列 であるならば, $\leq$ は 良い擬順序 (well-quasi-order) といいます. また, 無限列 $(x_1,x_2,\ldots)$ が 反鎖 であるとは, この列に含まれる任意の二要素が比較不能であることをいいます.
$(x_1,x_2,\ldots)$ が よい列 でないということは, 任意の $i<j$ に対して, $x_i > x_j$ もしくは $x_i$ と $x_j$ は比較不能 であるということです. 実は $\leq$ が $X$上で 良い擬順序であるための必要十分条件は, $X$は 狭義単調減少無限列 も 反鎖 も含まないことであるという定理が証明できます.
少し例を挙げます.
- $X=\mathbb{Z}$, $\leq$ を通常の整数の大小関係としましょう. このとき $X$ 上の無限列として $(-1,-2,\ldots)$ という狭義単調減少無限列がとれるため, $\leq$ は よい擬順序ではありません.
- $X=\mathbb{N}$, $\leq$ を通常の自然数の大小関係としましょう. このとき $X$ 上の無限列 として 単調減少なものはとれません. もちろん $\leq$ は全順序なので, 反鎖も存在しません. 従って $\leq$ は $\mathbb{N}$ 上では良い擬順序になっています.
これでグラフマイナー定理の言っていることが分かると思います. つまり $X$ をグラフの全体, $\leq$ をマイナー順序 として定義したときに, $\leq$ は $X$ 上で良い擬順序になっている, と言っています. 自然数の例と同様に, マイナーの順序で単調減少な無限列はとれないので, グラフマイナー定理を言い換えると「任意のグラフの無限列 $(G_1,G_2,\ldots)$ をもってきたときに, $G_j$ が $G_i$ をマイナーとして含む (すなわち $G_i \leq G_j$) なる $i<j$ が存在する」ということになるわけです.
5. 木に関するグラフマイナー定理
$\mathcal{T}$ を 木の全体とします. 更に $T_1, T_2 \in \mathcal{T}$ に対し, $T_2$ が $T_1$ を位相的マイナーとして含む (即ち $T_2$ は $T_1$ の細分を部分グラフとして含む) ときに $T_1 \leq T_2$ として定義します. この章では 次の定理を紹介します.
定理 (Kruskal, 1960)
上で定義した $\leq$ は $\mathcal{T}$ 上でよい擬順序になっている.この定理はいわば「グラフマイナー定理の木ver」と見ることが出来ます. この証明は非常にトリッキーで面白いので, 興味がある方は是非調べて見てください[2].
私自身はグラフマイナー定理の証明をちゃんと追ったわけではないのでいい加減なことは言えないのですが, その長大な証明の大筋は次のようなロジックに従っているとのことです[2].
- グラフに対してその木っぽさ (木幅) を定義する.
- 木幅が有限なグラフに対しては, 木ver のグラフマイナー定理の証明ロジックを何回か適用させる.
- 木幅が大きくなってしまうグラフに対しては, 木幅が大きいという構造上の特徴を用いてなんとかする.
この中でグラフの木っぽさという概念が非常に有用なものなので, それについては後日書きたいと思います.
[1]: J. Hopcroft, R. E. Tarjan, "Efficient planarity testing", Journal of the Association for Computing Machinery, 21 (4): 549–568, 1974
[2]: R. Diestel, "Graph Theory", 2000
0 件のコメント:
コメントを投稿