グラフマイナー定理

ウィキペディア

グラフ・マイナー定理

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/03/27 13:50 UTC 版)

グラフマイナー定理（グラフマイナーていり、英: Robertson–Seymour theorem）とは、有限グラフの全体は、マイナー順序によって良い擬順序になっている、という定理である。

背景

グラフ理論においては、部分グラフやマイナーをグラフ環境（英語版）に含むか否かで分類される。一方、グラフ幾何学では、グラフを描き込む幾何学的対象によって分類される。例えば、グラフを２次元時空に描く時、エッジの交差の有無で分類できる。グラフを平面に描き込んでもエッジが交差しないとき、グラフを平面グラフ、グラフを球面S³に埋め込んでエッジの交差が解けるとき球面グラフという。

グラフに対して、エッジを任意のノード要素を含むエッジに置き換えて得られるグラフを細分という。また、グラフのエッジ要素をいくらか削除したグラフを部分グラフという。グラフの細分が、頂点数5の完全グラフK₅や、上下に3点ずつ頂点がある2部グラフK_3,3を、部分グラフとして含まないとき、グラフは平面グラフである。これをクラトフスキーの定理という。

あるエッジに対し、両端にある頂点を一つの頂点に融合させる操作を縮約操作という。なお、このとき頂点から伸びるエッジの数は問われない。グラフGから縮約操作によって部分グラフHが得られたとき、H を G のマイナーといい、H ≤ Gとここでは表すこととする。グラフGのすべてのマイナーが、K₅ や K_3,3 を有しないとき、そのグラフは平面グラフである。これをワグナーの定理という。

グラフにおいて、グラフ間には数的にも幾何学的にも順序を考えることができる。（以降は数的な記述で表現している。）以下の四つの公理を満たすようなグラフの順序を全順序という。

1. 反射律: a ≤ a.
2. 推移律: a ≤ b , b ≤ c ならば b ≤ c.
3. 反対称律: a ≤ b かつ b ≤ a ならば a = b.
4. 全順序律: ある${\displaystyle a}$