同型

グラフは実用的には, その頂点と辺の関係性のみが重要となり, 

頂点を意味する集合が何であるかが問題になることは少ない.

それゆえ, 頂点と辺の関係性が同じであるようなグラフは同じものであるとして扱いたい.

ところが, 定義にある通り, グラフは本質的に集合の組であるから, 

用いている集合が異なっていれば同じものと扱うことはできない.

これはリンゴ 3 個とみかん 3 個を同じ 3 として扱うことができないようなもので

とても不便である.

グラフを有意義に扱うためには, 頂点と辺の関係性が同じグラフを同じものであると扱うための同値関係が必要となる, それが同型である.

定義：同型

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

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

\( \{u, v\} \in E \Leftrightarrow \{\sigma(u), \sigma(v)\} \in E' \)

が成り立つことである.

補題：

同型は同値関係である.