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

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

==概要==
<math>G=(V,E), G'=(V', E')</math> を（[[単純グラフ|単純]]）グラフとする。ただし <math>V</math> は <math>G</math> の頂点集合，<math>E</math> は <math>G</math> の枝の集合，同様に <math>V'</math> は <math>G'</math> の頂点集合，<math>E'</math> は <math>G'</math> の枝の集合である。<math>G</math> の任意の2頂点 <math>v, w \in V</math> に対して，<math>(v,w) \in E</math> となるのが <math>(f(v), f(w)) \in E'</math> となるとき、かつそのときに限るような <math>V</math> から <math>V'</math> への[[全単射]][[写像]] <math>f</math> が存在するとき，<math>G</math> と <math>G'</math> は'''グラフ同型'''（あるいは単に'''同型'''）であるといい{{sfn|ディーステル|2000|p={{google books quote|id=CZq8AAAAQBAJ|page=3|3}}|ps=&#x20;(p. {{google books quote|id=CZq8AAAAQBAJ|page=32|32}})}}、<math>G'</math> は <math>G</math> の'''同型グラフ'''であるという。

例として以下のようなグラフが与えられたとする。
{|class="wikitable" style="margin:0 auto; text-align:center"
! グラフ <math>G</math>
! グラフ <math>G'</math>
! 同型 <math>f</math>
|-
|style="width:33%"|[[Image:Graph isomorphism a.svg|100px]]
|style="width:33%"|[[Image:Graph isomorphism b.svg|210px]]
|style="width:33%"|<math> a \mapsto 1</math>

<math> b \mapsto 6</math>

<math> c \mapsto 8</math>

<math> d \mapsto 3</math>

<math> g \mapsto 5</math>

<math> h \mapsto 2</math>

<math> i \mapsto 4</math>

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

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

==脚注==
{{reflist}}

==参考文献==
*{{cite book
|和書
|last1      = ディーステル
|first1     = R.
|translator = 根上生也・太田克弘
|year       = 2000
|title      = グラフ理論
|edition    = 原書第2版
|url        = {{google books|CZq8AAAAQBAJ|plainurl=yes}}
|publisher  = [[シュプリンガー・ジャパン|シュプリンガー・フェアラーク東京]]
|isbn       = 978-4-431-70876-6
|ref        = harv
}}
* 戸田誠之助：「グラフ同型性判定問題」，富山房（2001）．

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