子图与补图

子图与补图是从"删边删点"和"补全缺失边"两个方向生成新图的构造，用于研究图的结构关系。

定义

• 子图：$G'=(V',E')$ 满足 $V'\subseteq V$、$E'\subseteq E$；若 $V'=V$ 称生成子图；若 $E'$ 包含 $V'$ 中所有两端都在 $V'$ 的边，称导出子图。
• 补图：对简单图 $G=(V,E)$，$\overline{G}=(V,\binom{V}{2}\setminus E)$，即同顶点、边集取补。

性质

$G$ 与其补图 $\overline{G}$ 顶点数相同、边数互补：$|E|+|\overline{E}|=\binom{|V|}{2}$。

示例

三角形 $K_3$ 的补图是三个孤立点；完全二分图 $K_{2,2}$ 的补图是两个互不相连的 $K_2$。

子图关系与补图构造都是同构意义下不变的，见图的同构。