同构图

考虑图 G(V, E) 和 G* (V*,E*)，如果存在一一对应关系，即 f:V→V* 使得 {u, v} 是 G 的一条边当且仅当 {f(u), f(v)} 是 G* 的一条边，则称它们是同构的。

图 (a) 的顶点数必须等于图 (b) 的顶点数，即一一对应，边也同样。

同胚图

如果两个图 G 和 G* 可以通过相同图或同构图的方法获得，则称它们是同胚的。图 (a) 和 (b) 不是同构的，但它们是同胚的，因为它们可以通过向图 (c) 添加适当的顶点来获得。

子图

图 G=(V, E) 的子图是一个图 G'=(V',E')，其中 V'⊆V 且 E'⊆E，并且 G' 的每条边在 G' 中具有与图 G 中相同的端点。

注意：单个顶点是一个子图。

示例： 考虑图 G，如图所示。显示该图的不同子图。

解决方案： 以下是上图中所示的图的所有子图

生成子图

如果 G₁ 包含 G 的所有顶点，则称图 G₁ 是 G 的生成子图。

示例：下图是图 Fig 中所示的生成子图