マイナー順序の推移性について

概要

　グラフマイナーの理論では、「$G$から部分グラフ$G'$をとり、その後$G'$のいくつかの辺を縮約することによって$H$が得られる」ならば、 $H$は$G$のマイナーであると定義されます。特にこのことを$H \preceq G$などと書き、順序関係$\preceq$はマイナー順序などと呼ばれ、世に知られるグラフマイナー定理は「$\preceq$はwell-quasi-orderである、即ち任意に有限グラフの無限列を持ってきたときに必ず$H \preceq G$なる$G,H$がその無限列に含まれる 」と主張しています。

　多くのグラフ理論では、マイナー順序を紹介する際に「マイナー順序は推移律を満たす」即ち「$X\preceq Y$ かつ $Y \preceq Z$ならば $X\preceq Z$である」ことは自明なものとして細かい説明は省かれています。しかしマイナー順序では「まず部分グラフをとり、その後縮約する」という順番があるので、この推移律の事実は「$Z$→部分グラフ→縮約→$Y$→部分グラフ→縮約→$X$」という流れを「$Z$→部分グラフ→縮約→$X$」という操作に変換できるということに他なりません。本当にそうなのでしょうか？？

　本記事では、「自明」として片付けられているマイナー順序の推移律の簡単な証明っぽいものを与えることにします。

　まずグラフ$G$に対し「縮約→部分グラフ」という操作によってグラフ$H$が得られるとします。通常のマイナーでは「部分グラフ→縮約」を考えますので、これはマイナーの逆順序の操作になっています。今、マイナーの推移律を仮定せずに$H \preceq G$(注*) が示せたとしましょう。すると、「縮約→部分グラフ」という操作が「部分グラフ→縮約」という操作に書き換えることが出来ることになるので、
$Z$→部分グラフ→縮約→部分グラフ→縮約→$X$
が
$Z$→部分グラフ→部分グラフ→縮約→縮約→$X$
と書き換えられ、まとめると
$Z$→部分グラフ→縮約→$X$
となり、$X \preceq Z$が示せたことになります。

(注*) なお、マイナーの推移律を仮定するとこの事実は簡単に示せます。なぜならば$G$から縮約して得られるグラフを$G'$とし、$H$が$G'$の部分グラフになっているように$G'$をとってくると、$H \preceq G' \preceq G$となるので、推移律より明らかに$H \preceq G$が言えます。つまりこの事実は推移律と等価になっています。

証明っぽい説明

　というわけで、「縮約→部分グラフ」によって得られたグラフ$H$は「部分グラフ→縮約」によっても得られることを示しましょう。

・ケース1

まず、次の図の左上のグラフ$G$のように、部分グラフの領域(図の黄色領域)(注**)を、縮約する辺(赤い辺)が横切らない場合を考えます：



この図では、$G$の赤い辺を縮約することを考えており、「縮約→部分グラフ」という操作によって$H$が得られています (図の↓→に対応します)。

・黄色領域外の辺は、結局部分グラフをとるので縮約しようがしまいが関係ありません。
・図より明らかなように、この$H$は図の→↓の操作によっても得られます。

従ってこの場合は縮約と部分グラフの操作の順番を入れ替えても差し支えありません。

(注**)
$G$の黄色領域は、イメージとしては「$H$の頂点に含まれる or 寄与した頂点の全体」です。ちゃんと言うと、まず、$G$から縮約して得られたグラフ(図左下に対応)の頂点のうち、$H$に含まれるものを赤く塗ります。次にこのグラフの赤い頂点それぞれに対し、それが$G$から縮約によって得られたものならば縮約された$G$の辺に対し、その辺に接続する頂点を全て黄色く塗ります。また、$G$に含まれる$H$の頂点も黄色く塗ります。
このとき、黄色く塗られた頂点の全体が黄色い領域となります。「黄色い領域を横切る辺が存在しない」とは「どちらか一方のみが黄色い頂点であるような辺は存在しない」という意味です。

・ケース2

次の図のように、縮約する辺で黄色い領域を横切るようなものが存在する場合を考えます。



　この場合、$G$の黄色い領域を少し拡張し、またがるような縮約辺が存在しないようにすることによって所望の$H$を「部分グラフ→縮約」の操作によって得ることができます。
　具体的には、(注**)の操作によって$G$の頂点を黄色く塗った後、黄色い頂点を横切る赤い辺があったならば黄色領域外にあった頂点もまた黄色く塗る」という操作を可能な限り行います。そして、$G$から黄色い領域を部分グラフとしてもってきて、その後縮約すれば$H$を得ることができます。(この時、黄色領域内にあって$H$に寄与しないような辺は最初の部分グラフをとる操作の際に消しておきます)

まとめ

　マイナー順序の推移律を簡単に示したっぽいことをしました (直感的な説明ばかりであまり厳密な議論ではありませんが、、、）。特に面白い事実としては「縮約→部分グラフ」という操作と「部分グラフ→縮約」という操作は（書き換え可能という意味において）等価であるということだと思います。グラフ理論にはマイナーの他にも「位相的マイナー」「shallow minor」など、様々な亜種が知られていますが、多分似たような雰囲気で示せるのではないかと思います。