このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ
  • 追加された行はこの色です。
  • 削除された行はこの色です。
  • グラフ同型問題 へ行く。

*目次 [#q57dc336]

#contents


*グラフ同型問題 [#c1bd6285]

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

-入力
--n頂点の2つのグラフGSUB{1};=(VSUB{1};,ESUB{1};)とGSUB{2};=(VSUB{2};,ESUB{2};)
-問題
--{u,v}∈ESUB{1};と{π(u),π(v)}∈ESUB{2};が必要十分条件となるような同型写像π:VSUB{1};→VSUB{2};は存在するか?
---つまり、GSUB{1};とGSUB{2};は同型か?

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