グラフ同型

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索

グラフ同型(ぐらふどうけい)とはグラフ理論における概念の一つである。

概要[編集]

を(単純)グラフとする。ただし の頂点集合, の枝の集合,同様に の頂点集合, の枝の集合である。 の任意の2頂点 に対して, となるのが となるとき、かつそのときに限るような から への全単射写像 が存在するとき,グラフ同型(あるいは単に同型)であるといい[1]同型グラフであるという。

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

グラフ グラフ 同型
Graph isomorphism a.svg Graph isomorphism b.svg

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

グラフ同型性判定問題[編集]

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

脚注[編集]

参考文献[編集]