部分グラフ

定義

• グラフ $G = (V,E)$ について, $G$ の部分グラフ $G' = (V',E')$ とは, $V' \subset V$ かつ $E' \subset E$ なるグラフのことをいう.

• $G$ と $V' \subset V$ について, $G[V']$ とは, 頂点集合を $V'$, 辺集合を $E \cap [V']^2$ と定めた $G$ の部分グラフのことをいう.

• $G$ の部分グラフ $G' = (V',E')$ について $V' = V$ ならば, $G'$ は全域的な部分グラフであるという.

information

情報源

• R. Diestel. "Graph Theory". Springer (2000).

関連項目

• グラフ