グラフ同型

グラフ同型（グラフどうけい）とはグラフ理論における概念の一つである。

概要

$G=(V,E),G'=(V',E')$ を（単純）グラフとする。ただし $V$ は $G$ の頂点集合， $E$ は $G$ の枝の集合，同様に $V'$ は $G'$ の頂点集合， $E'$ は $G'$ の枝の集合である。 $G$ の任意の2頂点 $v,w\in V$ に対して， $(v,w)\in E$ となるのが $(f(v),f(w))\in E'$ となるとき、かつそのときに限るような $V$ から $V'$ への全単射写像 $f$ が存在するとき， $G$ と $G'$ はグラフ同型（あるいは単に同型）であるといい^[1]、 $G'$ は $G$ の同型グラフであるという。

例として以下のようなグラフが与えられたとする。

グラフ $G$	グラフ $G'$	同型 $f$
		$a\mapsto 1$ $b\mapsto 6$ $c\mapsto 8$ $d\mapsto 3$ $g\mapsto 5$ $h\mapsto 2$ $i\mapsto 4$ $j\mapsto 7$

このとき、隣接する頂点に対応する頂点は隣接していることがわかる。このように $G$ と $G'$ が「同一」の頂点を持ち、同一の辺のつながりかたをしているときにそのグラフを同型というのである。

グラフ同型性判定問題

与えられた二つのグラフが同型か否かを判定する問題である。この問題がNPに属することは分かっているが、P, co-NP, BPPに属するかどうかは分かっていない。NP完全に属するかどうかも分かっていないので、量子計算機を用いて多項式時間で解けるかどうかに関しても、さかんに研究されている。より詳しい状況は英語版のWikipediaを参照されたい。

脚注

^ ディーステル 2000, p. 3 (p. 32)

参考文献

ディーステル, R. 著、根上生也・太田克弘訳『グラフ理論』（原書第2版）シュプリンガー・フェアラーク東京、2000年。ISBN 978-4-431-70876-6。
戸田誠之助：「グラフ同型性判定問題」，富山房（2001）．

[FOOTNOTEディーステル20003-1] ディーステル 2000, p. 3 (p. 32)

[1]