組合せとグラフの理論（塩田）第2回 (5)　グラフの同型
前へ / 戻る / 次へ

グラフの同型

　グラフはもののつながりを表す概念なので、「つながり方が同じである」ということを定義しましょう。
Def.6　ふたつのグラフ $G=(V,E)$, $H=(W,F)$ が同型である ( $G \cong H$ )、とは、 次の同値な条件のいずれかが成り立つこと：
  1. 辺を接続させたまま頂点を動かすと同じ絵になる
  2. オーダーが等しく、頂点の名前を付け替えると辺集合が等しくなる
  3. 頂点の一対一対応 $\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$ は含まないから。（証明終）

前へ / 戻る / 次へ