グラフ同型

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

概要

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

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

グラフ G {\displaystyle G} グラフ G ′ {\displaystyle G'} 同型 f {\displaystyle f}
a ↦ 1 {\displaystyle a\mapsto 1}

b ↦ 6 {\displaystyle b\mapsto 6}

c ↦ 8 {\displaystyle c\mapsto 8}

d ↦ 3 {\displaystyle d\mapsto 3}

g ↦ 5 {\displaystyle g\mapsto 5}

h ↦ 2 {\displaystyle h\mapsto 2}

i ↦ 4 {\displaystyle i\mapsto 4}

j ↦ 7 {\displaystyle j\mapsto 7}

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

グラフ同型性判定問題

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

脚注

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

参考文献