グラフマイナー理論

グラフマイナー理論

今井 浩(情報理工学系研究科コンピュータ科学専攻 教授)

道路網は交差点を点,交差点を結ぶ道路を枝で表して,点集合と2点を結ぶ枝集合からなるグラフとして表現でき,カーナビはこのグラフ上の最短路問題を解いている。正方・ハニカム・カゴメ格子などの結晶構造,化学構造・電気回路もグラフである。

道路網は立体交差等がない限り平面上に枝の交差なく描画できる平面グラフであり,正方格子等も同様である。一方,5点中の2点を全ての組合せで枝で結んだグラフ K5 は,平面上にどう描こうが枝交差ができ,非平面グラフである。6点の内の3点の各点を,他の3点の各点と枝で結んで得られるグラフ K3,3 も非平面グラフである(図参照)。ここで,グラフのマイナーを,枝を単に削除か両端点を同一化して削除(縮約)を繰り返して得られるグラフとすると,グラフが平面的である必要十分条件は K5, K3,3 をマイナーとしてもたないことであり,平面グラフに対して K5, K3,3 は「禁止マイナー」になっている。電池を直並列に接続してできる2端子電気回路のグラフに代表される直並列グラフの禁止マイナーは K4,植物の木のように閉路を持たないグラフ(木)の禁止マイナーは K3 となる。

平面・直並列・木グラフのマイナーは引き続き平面・直並列・木である。グラフのクラスで,すべてのマイナーがそのクラスに属するものを,マイナーに関して閉じているという。グラフマイナー理論の第一定理は,「マイナーについて閉じたグラフのクラスは,有限個の禁止マイナーで特徴づけられる」というものである。平面・直並列・木は,禁止マイナーが2個・1個・1個だが,他の場合も有限な定数個の禁止マイナーによって特徴づけられる。

グラフマイナー理論は,グラフの深遠な分解理論(木分解など)も提供する。グラフが木にどれだけ近いかを示す木幅というグラフのパラメタは,木分解から定義される。木の木幅は1で,直並列グラフの木幅は2である。グラフマイナー理論の次の定理は「十分大きな木幅のグラフは,十分大きな正方格子グラフをマイナーとしてもつ」である。この定理は,量子コンピュータの測定ベース計算モデルの万能性と関係するなど,理学の他分野の問題を深く関わっており,グラフマイナー理論はそうした分野へ展開されている。