部分グラフと部分グラフ同型

グラフの性質として, そのグラフの一部に特定の形が表れているか否かが重要になる場合がある. また, グラフに関する解析をするときに, グラフをいくつかの部分に分割してそれぞれの結果を得, 最後に統合するような手段もよく使われる.

これらの場合に必要になるのが部分グラフの概念である.

定義：部分グラフ

グラフ \( H = (W, F) \) とグラフ \( G = (V, E) \) が \( W \subseteq V \) かつ \( F \subseteq E \) であるとき, \( H \) は \( G \) の部分グラフである.

\( H \) が \( G \) の部分グラフであるとき, \( H \subseteq G \) と書く.

次に, グラフの部分グラフであって別のグラフと同型なものが存在することを意味する 部分グラフ同型を定義する.

定義：部分グラフ同型

グラフ \( H = (W, F) \) とグラフ \( G = (V, E) \) に対して, ある写像 \( \sigma \) が存在して 任意の \( v, w \in W\) で \( \{ v, w\} \in F \Rightarrow \{\sigma(v), \sigma(w) \}\in E \) を満たすとき, \( H \) は \( G \) の部分グラフ同型である.

グラフ \( H \) と \( G \) が同型であるとき, 集合の対としては別物であるにもかかわらず \( H = G\) と書いた. それと同様に, \( H \) が \( G \) の部分グラフ同型であるとき, \( H \subseteq G \) と書く.

部分グラフ同型の定義が目的にかなっていることを, 次の補題で証明する.

補題：部分グラフ同型：１

グラフ \( H \) と \( G \) が部分グラフ同型であるとき, \( G \) は \( G' = H \) を満たすようなグラフ \( G'\) を部分グラフとして持つ.

証明

実際にグラフ \( G' \) を与えることで証明とする.

\( H = (W, F) \), \( G = (V, E) \) とおく. \( H \) と \( G \) が部分グラフ同型である[by 補題の仮定]から, ある写像 \( \sigma \) が存在して 任意の \( v, w \in W\) で \( \{ v, w\} \in F \Rightarrow \{\sigma(v), \sigma(w) \}\in E \) を満たす[by 定義：部分グラフ同型]. ここで, \( G' \) を

\[ G' = ( \{ \sigma(v) \mid v \in W \}, \{ \{ \sigma(v), \sigma(w) \} \mid v, w \in W \} ) \]

と定めると, \( \sigma \) の定義より, \( \{ \sigma(v) \mid v \in W \} \subseteq V \) かつ \( \{ \{ \sigma(v), \sigma(w) \} \mid v, w \in W \} \subseteq E \) である. 故に, \( G' \) は \( G \) の部分グラフであり[by 定義：部分グラフ], \( G' \) が見つかったので補題は証明された.

証明終