組合せとグラフの理論(塩田)第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$ は含まないから。(証明終)