📂グラフ理論

サブグラフ

定義 ¹

グラフ$G$について、グラフ$H$が$V(H) \subset V(G)$と$E(H) \subset E(G)$を満たす場合、$H$を$G$のサブグラフと言う。

説明

注意すべき点は、$H$が$G$のサブグラフであると$H \subset G$のように示してはいけないことである。サブグラフの概念はグラフ理論自体の興味の対象としてよりは、むしろ自然で常識的な用語としての意味がある。

例

サブグラフを定義することで、次のような例を考えることができる：

コンポーネント

切断されたグラフ$D$のコンポーネントは全て$D$のサブグラフである。

グラフの減算

グラフ$G$が与えられたとする：

• エッジについて：$e \in E(G)$に対して、$E(G) - e$は$G$のエッジ$e$を取り除いたグラフとして定義され、自然に$G$のサブグラフとなる。このようなグラフの減算操作$-$は、エッジの集合に対しても拡張可能である。$E(G) - E$は、$G$のエッジの部分集合$E$のエッジを取り除いたグラフとして定義され、同様に$G$のサブグラフとなる。
• バーテックスについて：$v \in V(G)$に対して、$E(G) - v$は$G$のバーテックス$v$と$v$に付随する全てのエッジを取り除いたグラフとして定義される。バーテックスについても、バーテックスの集合$V \subset V(G)$に対して拡張可能である。$E(G) - V$は、$G$のバーテックスの部分集合$V$のバーテックスとそれに付随するエッジを取り除いたグラフとして定義され、当然、$G$のサブグラフとなる。
• グラフの収縮：上記の二つの減算操作で記号$-$に注目する。集合の減算記号$\setminus$は、グラフでのエッジのContractionを意味するために使われる。エッジが収縮されるということは、エッジ$e$が消えて、$e$に接続されていた二つの端点$v$と$w$を同一視することである。

このようなグラフの減算は、グラフを構築するアルゴリズムなどを話すときに非常に便利なツールとなる。

スパニング

$G$のサブグラフ$H$が$V\left( H \right) = V(G)$を満たす場合、$H$を$G$のスパニングと言う。簡単に言えば、バーテックスはそのままで、エッジのみが取り除かれた可能性があるサブグラフである。グラフの減算でエッジが取り除かれたケースに当たる。

誘導グラフ

$G$のサブグラフ$H$が $$E \left( H \right) = \left\{ uv \in E(G) : u,v \in V \left( H \right) \right\}$$ を満たす場合、誘導グラフと呼ばれる。誘導グラフは、特定のルールなしにエッジが取り除かれ、バーテックスのみが保持されるスパニングとは異なり、バーテックスが保持されている部分では接続するエッジも保持されているため、元のグラフ$G$の性質をある程度受け継いでいると推測できる。