グラフ同型性判定問題
$ Gと$ G'が同型であるとは、
$ Gの任意の$ 2頂点$ v,w \in Vに対して$ (v,w)\in Eなら、かつその時に限り$ (f(v),f(w)) \in E'となる$ Vから$ V'への全単射写像$ fが存在すること。
$ Vの置換を考える。順列$ (P_1,P_2,\dots,P_N)によって頂点$ i \in Vを$ P_i \in V'に対応させることにする。より直感的には、$ Gの頂点$ iを$ G'の頂点$ P_iとみなすことにする。
この頂点の並び替えによって、$ (i,j) \in Eなら、かつその時に限り$ (P_i,P_j)\in E'であるようにできるなら、$ Gと$ G'は同型である。
具体的には、$ 2つのグラフを隣接行列で持っておいて、あり得る並び替えを順列全探索ですべて試す。 あり得るすべての$ i,jに対して、$ G_{i,j}と$ G'_{P_i,P_j}の辺の有無が一致していれば同型。