組合せとグラフの理論(塩田)第2回 (5) グラフの同型
グラフの同型
グラフはもののつながりを表す概念なので、「つながり方が同じである」ということを定義しましょう。
Def.6 ふたつのグラフ $G=(V,E)$, $H=(W,F)$ が同型である ( $G \cong H$ )、とは、
次の同値な条件のいずれかが成り立つこと:
- 辺を接続させたまま頂点を動かすと同じ絵になる
- オーダーが等しく、頂点の名前を付け替えると辺集合が等しくなる
- 頂点の一対一対応 $\varphi : V \rightarrow W$ があって、
$uv$ が $G$ の辺であること ( $uv \in E$ ) と
$\varphi(u)\varphi(v)$ が $H$ の辺であること ( $\varphi(u)\varphi(v) \in F$ ) が同値になる
Ex.7 次の 2 つのグラフは同型である。
$G=$
$H=$
(1) による説明:$G$ の右下の頂点を左へ移動させ、下の 2 頂点を右へずらすと $H$ になります。
→
→
動画はここ ( 243KB )
(2) による説明:次のように頂点の名前を付けると、どちらも辺集合が $\{\,12,13,14,23,34\,\}$ になります。
$G=$
$H=$
(3) による説明:次のように頂点の名前を付け、
$$\varphi(1)=u,\ \varphi(2)=v,\ \varphi(3)=w,\ \varphi(4)=x$$
と定めると、
隣接していない頂点は $G$ では $2$ と $4$, $H$ では $v=\varphi(2)$ と $x=\varphi(4)$ となって、
$\varphi$ によって隣接関係が写り合っています。
$G=$
$H=$
Ex.8 次の 2 つのグラフは同型である。
$G=$
$H=$
これは次のように頂点番号を振ってもわかりますし(確かめてみましょう)、
$G=$
$H=$
Ex.7 と同様に
動画 ( 235KB ) でも確かめられます。
※ 例えば「一筆描きできるか否か」といった、つながり方に関する問題の答えは、同型なグラフであれば同じになります。
ここ大事!
Th.9 同型なグラフでは
- オーダー ( 頂点数 )
- サイズ ( 辺数 )
- 頂点の次数たち
は全て等しい。
証明 動かせば同じ絵になるから。(証明終)
※ しかし、逆は言えません。
オーダー、サイズ、頂点の次数たちが等しいからと言って同型とは限らないのです。
ここめちゃくちゃ大事!
Ex.10 次の二つのグラフはいずれも、オーダー 6、サイズ 9、次数は全て 3 で同じであるが、同型ではない。
$G=$
$H=$
証明 $G$ は三角形を含むが $H$ は含まないから。(証明終)