グラフ同型のソースを表示

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

==概要==
頂点集合が等しいグラフG, G'について、各々の枝集合をE, E'とする。Gの任意の枝e=(v, w)について、(f(v), f(w))がE'に属するような[[全単射]]な[[写像]] f が存在するとき、GとG'は'''グラフ同型'''（あるいは単に同型）であるといい、G'はGの'''同型グラフ'''であるという。

例として以下のようなグラフが与えられたとする。
{|class="wikitable"
! グラフ G
! グラフ G'
! G と G' の対応
|-
|[[Image:Graph isomorphism a.svg|100px]]
|[[Image:Graph isomorphism b.svg|210px]]
|align="center"|<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 (計算量理論)|P]], [[co-NP]], [[BPP_(計算量理論)|BPP]]に属するかどうかは分かっていない。[[NP完全]]に属するかどうかも分かっていないので、[[量子計算機]]を用いて[[多項式時間]]で解けるかどうかに関しても、さかんに研究されている。

{{DEFAULTSORT:くらふとうけい}}
[[category:グラフ理論]]
[[Category:数学に関する記事]]