图论1-3 子图

3.1 基本介绍

1. 子图（subgraph）

如果$V(H)\subseteq V(G)$，$E(H)\subseteq E(H)$，并且$\phi(H)$是在$\phi(E)$上的限制，则称图 H 是图 G 的 子图，图 G 是图 H 的 母图，记为$H\subseteq G$，当$H\neq G$时，则称图 H 是图 G 的 真子图，记为$H\subset G$。

2. 生成子图（spanning subgraph）

若图 H 是图 G 的 子图，且满足$V(H)=V(G)$，则称图 H 是图 G 的 生成子图，图 G 是图 H 的 生成母图。

3. 简单基础图

将图 G 的所有环删除，并使每一对相邻顶点只留下一条边，得到的生成子图称为 简单基础图。

4. 导出子图（Induced Subgraph）

设 $V^{‘}$是$V$的一个非空子集，以 $V^{‘}$为点集，以两端端点均在$V^{‘}$的边的全体为边集组成的子图，称为$G$ 由 $V^{‘}$导出的子图，记为 $G[V^{‘}]$，$G[V^{‘}]$是 $G$的 导出子图。
导出子图$G[V\backslash V^{‘}]$记为$G-V^{‘}$，它是从$G$ 中删除 $V^{‘}$中的顶点以及相关联的边所得到的子图。$G-{v}=G-v$。

5. 边导出子图（edge-induced subgraph）

设 $E^{‘}$是$E$的一个非空子集，以 $E^{‘}$为边集，以$E^{‘}$中端点全体为顶点集组成的子图，称为$G$ 由 $E^{‘}$导出的子图，记为 $G[E^{‘}]$，$G[E^{‘}]$是 $G$的 边导出子图。
边导出子图$G[E\backslash E^{‘}]$记为$G-E^{‘}$，它是从$G$ 中删除 $E^{‘}$中的所有的边所得到的子图。类似的在$G$ 上加上不想交的边集$E^{‘}$，记为$G+E^{‘}$。$G\pm{e}=G\pm e$。

3.2 图的交并

设 $G_1$和 $G_2$是 $G$的子图。

• 若 $G_1$和 $G_2$没有公共顶点，称它俩是 不相交 的。
• 若 $G_1$和 $G_2$没有公共边，称它俩是 边不重 的。
• $G_1$和 $G_2$的 **并图 **记为 $G_1\cup G_2$，其顶点集为 $V(G_1)\cup V(G_2)$，边集为$E(G_1)\cup E(G_2)$。如果 $G_1$和 $G_2$是不相交的，则并图也可以记为$G_1+G_2$。
• $G_1$和 $G_2$的 **交图 **记为 $G_1\cap G_2$，$G_1$和 $G_2$至少有一个公共顶点，其顶点集为 $V(G_1)\cap V(G_2)$，边集为$E(G_1)\cap E(G_2)$。

  3.3 例子