グラフ同型

グラフ同型（グラフどうけい）とはグラフ理論における概念の一つである。
概要.
formula_1 を（単純）グラフとする。ただし formula_2 は formula_3 の頂点集合，formula_4 は formula_3 の枝の集合，同様に formula_6 は formula_7 の頂点集合，formula_8 は formula_7 の枝の集合である。formula_3 の任意の2頂点 formula_11 に対して，formula_12 となるのが formula_13 となるとき、かつそのときに限るような formula_2 から formula_6 への全単射写像 formula_16 が存在するとき，formula_3 と formula_7 はグラフ同型（あるいは単に同型）であるといい、formula_7 は formula_3 の同型グラフであるという。
例として以下のようなグラフが与えられたとする。
このとき、隣接する頂点に対応する頂点は隣接していることがわかる。
このように formula_3 と formula_7 が「同一」の頂点を持ち、同一の辺のつながりかたをしているときにそのグラフを同型というのである。
グラフ同型性判定問題.
与えられた二つのグラフが同型か否かを判定する問題である。この問題がNPに属することは分かっているが、P, co-NP, BPPに属するかどうかは分かっていない。NP完全に属するかどうかも分かっていないので、量子計算機を用いて多項式時間で解けるかどうかに関しても、さかんに研究されている。より詳しい状況は英語版のWikipediaを参照されたい。