同型-2

前回の記事で抽象的な話をしていたが, 

同型についてもう少し具体的な例を示す.

まず, 次の 2 つのグラフを考える.

\( G = \left(\{1, 2, 3\}, \{\{ 1, 2\},\{ 2, 3\},\{ 1, 3\}\}\right)  \)

\( H = \left(\{a, b, c\}, \{\{ a, b\},\{ b, c\},\{ a, c\}\}\right) \)

これらはどちらもグラフとして図示すれば三角形になる.

しかし, グラフを構成している要素が異なる以上, G = H ではあり得ない.

この「違うグラフ」である「同じ形をしたグラフ」を結びつけるのが同型である.

実際にこの G と H が同型であることを確認しよう.

まず同型の定義を確認しておく. 

定義：同型

2 つのグラフ G(V, E) と G'(V', E') が同型であるとは, 

ある V から V' への 1 対 1 写像 σ が存在して任意の u, v ∈ V に対して

が成り立つことである.

定義に G と H を代入してみると, G=({1,2,3}, {{1,2},{2,3},{1,3}}) と

H= ({a,b,c}, {{a,b},{b,c},{a,c}}) が同型であることを示すためには, 

{1, 2, 3} から {a, b, c} への 1 対 1 写像 σ であって, 任意の u, v ∈ {1, 2, 3} に対して

 

が成り立つものの存在を示せば良い.

そのような σ として, たとえば

σ(1) = a, σ(2) = b, σ(3) = c

が考えられる.