グラフ・マイナー定理
From Wikipedia, the free encyclopedia
グラフマイナー定理（グラフマイナーていり、英: Robertson–Seymour theorem）とは、有限グラフの全体は、マイナー順序によって良い擬順序になっている、という定理である。
グラフ理論においては、部分グラフやマイナーをグラフ環境（英語版）に含むか否かで分類される。一方、グラフ幾何学では、グラフを描き込む幾何学的対象によって分類される。例えば、グラフを２次元時空に描く時、エッジの交差の有無で分類できる。グラフを平面に描き込んでもエッジが交差しないとき、グラフを平面グラフ、グラフを球面S3に埋め込んでエッジの交差が解けるとき球面グラフという。
グラフに対して、エッジを任意のノード要素を含むエッジに置き換えて得られるグラフを細分という。また、グラフのエッジ要素をいくらか削除したグラフを部分グラフという。グラフの細分が、頂点数5の完全グラフK5や、上下に3点ずつ頂点がある2部グラフK3,3を、部分グラフとして含まないとき、グラフは平面グラフである。これをクラトフスキーの定理という。
あるエッジに対し、両端にある頂点を一つの頂点に融合させる操作を縮約操作という。なお、このとき頂点から伸びるエッジの数は問われない。グラフGから縮約操作によって部分グラフHが得られたとき、H を G のマイナーといい、H ≤ Gとここでは表すこととする。グラフGのすべてのマイナーが、K5 や K3,3 を有しないとき、そのグラフは平面グラフである。これをワグナーの定理という。
グラフにおいて、グラフ間には数的にも幾何学的にも順序を考えることができる。（以降は数的な記述で表現している。）以下の四つの公理を満たすようなグラフの順序を全順序という。
- 反射律: a ≤ a.
- 推移律: a ≤ b , b ≤ c ならば a ≤ c.
- 反対称律: a ≤ b かつ b ≤ a ならば a = b.
- 全順序律: ある
,
に対し a ≤ bもしくはb ≤ aのどちらかが成り立つ
一方のグラフが他方のグラフをマイナーとして含むことがない場合、このグラフの順序は全順序律を満たさないため、半順序となる。このような順序を擬順序という。G が H をマイナーとして含むとき、すなわち、H ≤ Gの順序 ≤ をマイナー順序という。例えば、H が G をマイナーとして含むグラフの対はマイナー順序にならない。なお、K5 と K3,3 は擬順序の対である。
ところで、集合論における良い擬順序の定義を示す。 ≤ が擬順序になっており、Xが無限集合であるものを考える。X上の無限列 (x1, x2, ...) において、添字 i < j が xi ≤ xj となるとき、この列をよい列 (good)であるといい、 ≤ を良い擬順序という。
Xをグラフの（有限の）全体、 ≤ をマイナー順序として定義したときに、 ≤ は X上で良い擬順序になっている。これをグラフマイナー定理という。
グラフ幾何学においては、部分グラフは縮約操作によって得られたものであるため、元のグラフより大きくなることは考え得ない。平面トポロジーを含んだグラフ環境における定理の拡張が求められている。