このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ

目次

グラフ同型問題

 グラフ同型問題(graph non-isomorphism problem)とは、次の入力に対して、次の問題を解くことである。

  • 入力
    • n頂点の2つのグラフG1=(V1,E1)とG2=(V2,E2)
  • 問題
    • {u,v}∈E1と{π(u),π(v)}∈E2が必要十分条件となるような同型写像π:V1→V2は存在するか?
      • つまり、G1とG2は同型か?

 このグラフ同型問題は多項式時間で解けるかどうかは未解決問題になっている。同型か否かを調べる問題なので、同型であることを示すのも同型でないことを示すのも困難ということになる。