子图

$G=<V,E>,G^{\prime }=<V^{\prime },E^{\prime }>$,

• 若 $V^{\prime }\subseteq V$ 且 $E^{\prime }\subseteq E$, 称 $G^{\prime }$ 是 $G$ 的子图, 记为 $G^{\prime }\subseteq G$.

• 若 $G^{\prime }\subseteq G$ 且 $V^{\prime }=V$, 称 $G^{\prime }$ 为 $G$ 的生成子图.

• 若 $V^{\prime }\subset V$ 或 $E^{\prime }\subset E$, 称 $G^{\prime }$ 为 $G$ 的真子图.

• $G$ 中两个端点都在 $V^{\prime }$ 中的边组成边集 $E^{\prime }$ 的子图称为 $V^{\prime }$ 的导出子图, 记作 $G[V^{\prime }]$.

• $G$ 中与 $E^{\prime }$ 中的边关联的顶点组成的顶点集 $V^{\prime }$ 的子图称为 $E^{\prime }$ 的导出子图, 记作 $G[E^{\prime }]$.