組合せとグラフの理論（塩田）2024年度

組合せとグラフの理論（塩田）第15回 (2)　グラフマイナー

前へ / 戻る / 次へ

$\newcommand{\ol}[1]{\overline{#1}}$

$\newcommand{\card}[1]{\left|\,#1\,\right|}$

マイナーの定義

　平面性の回に次の定理を習いました：

クラトフスキーの定理

$G$ が平面的であること

$\Leftrightarrow$

$G$ のいかなる部分グラフも

$K_5$ や

$K_{3,3}$ には縮約できない

このような現象が実はたくさんある、というお話です。何が「このような」かを説明するために次の定義をします。

Def. グラフ

$G$ に対して次の3種類の操作を繰り返し施して得られるグラフを

$G$ のマイナーと呼ぶ：

頂点を除去する
辺を除去する
辺を縮約する

$H$ が

$G$ のマイナーであることを

$H \preceq G$ と表す。

するとクラトフスキーの定理は

$G$ が平面的であること

$\Leftrightarrow$

$K_5$ も

$K_{3,3}$ も

$G$ のマイナーにならないこと

と言い換えられます。

グラフマイナー理論

　Robertson と Seymour による一連の研究により、

$\preceq$ は「良い」順序(正確には擬順序と呼ぶ）になっていることが示され、沢山の定理が造られています。

Th. 任意の閉曲面

$S$ に対し、有限個のグラフ

$H_1$ ,

$H_2$ ,

$\cdots$ ,

$H_n$ があって
「

$G$ が

$S$ 上に辺の交差無く描画できること

$\Leftrightarrow$

$H_i$ (

$i=1,2,\cdots,n$ ) がすべて

$G$ のマイナーにならないこと」

　平面グラフであることは、球面上に辺の交差無く描画できることと同値でしたから、

$S$ が球面のときこの定理が

$H_1=K_5$ ,

$H_2=K_{3,3}$ で成り立つ、とういうのがクラトフスキーの定理です。
　球面や、図のような曲面を閉曲面と言い、

任意の閉曲面に対しても、そのような有限個のグラフ

$H_1$ ,

$H_2$ ,

$\cdots$ ,

$H_n$ が存在することが証明された、という訳です。（具体的に

$H_1$ ,

$H_2$ ,

$\cdots$ ,

$H_n$ を書き下す問題は難しいらしい。)

Th. 固定されたグラフ

$H$ に対し、入力されたグラフが

$H$ をマイナーとするか否かを判定する多項式時間アルゴリズムが存在する。

多項式時間アルゴリズムを与えている訳ではありませんが、多項式時間アルゴリズムが存在することは証明できているそうです。

前へ / 戻る / 次へ