グラフ同型
出典: フリー百科事典『ウィキペディア（Wikipedia）』
グラフ同型（ぐらふどうけい）とはグラフ理論における概念の一つである。
概要
頂点集合が等しいグラフG, G'について、各々の枝集合をE, E'とする。Gの任意の枝e=(v, w)について、(f(v), f(w))がE'に属するような全単射な写像 f が存在するとき、GとG'はグラフ同型（あるいは単に同型）であるといい、G'はGの同型グラフであるという。
例として以下のようなグラフが与えられたとする。
| グラフ G | グラフ G' | G と G' の対応 |
|---|---|---|
| 100px | 210px | <math> a \leftrightarrow 1</math>
<math> b \leftrightarrow 6</math> <math> c \leftrightarrow 8</math> <math> d \leftrightarrow 3</math> <math> g \leftrightarrow 5</math> <math> h \leftrightarrow 2</math> <math> i \leftrightarrow 4</math> <math> j \leftrightarrow 7</math> |
このとき、グラフ G の各ノードに繋がっているノードは全てグラフ G' の対応する各ノードに繋がっていることがわかる。 このように GとG'が同一の頂点を持ち、同一の辺のつながりかたをしているときにそのグラフを「同型」というのである。
グラフ同型性判定問題
与えられた二つのグラフが同型か否かを判定する問題である。この問題がNPに属することは分かっているが、P, co-NP, BPPに属するかどうかは分かっていない。NP完全に属するかどうかも分かっていないので、量子計算機を用いて多項式時間で解けるかどうかに関しても、さかんに研究されている。
