1. 什么是导出子图？
在图论中，导出子图（Induced Subgraph） 是图的一种特殊子图形式。它不仅保留了原图中某些节点，还保留了这些节点之间所有存在的边。换句话说，如果我们选定了一个节点集合 S，那么由 S 导出的子图必须包含所有两端点都在 S 中的边。
这与普通子图不同。普通子图可以只保留部分边，而导出子图必须保留所有符合条件的边。
2. 子图 vs 导出子图
| 特性 | 普通子图 | 导出子图 |
|---|---|---|
| 节点集合 | 是原图节点的子集 | 是原图节点的子集 |
| 边集合 | 是原图边的子集 | 必须包含所有两端点在选定集合中的边 |
| 是否唯一 | 不唯一（可以任意选边） | 唯一（由节点集合决定） |
| 是否保留邻接关系 | 不一定 | 一定保留 |
✅ 导出子图的关键在于“完全保留邻接关系”。
例如，原图如下：
它的一个导出子图如下：
3. 导出子图相关问题与算法
3.1 构造导出子图
问题描述：给定图 G = (V, E) 和节点集合 S ⊆ V，构造由 S 导出的子图 G_S = (S, E_S)，其中 E_S 是 G 中两端点都在 S 中的所有边。
✅ 算法思路：
- 遍历 S 中每个节点 u；
- 遍历 u 的所有邻接节点 v；
- 如果 v 也在 S 中，就将边 (u, v) 加入 E_S。
algorithm ConstructInducedSubgraph(G, S):
// INPUT
// G = (V, E) = the input graph with nodes V and edges E
// S = the inducing set of nodes, a subset of V
// OUTPUT
// G_S = (S, E_S) = the subgraph of G induced by S
E_S <- an empty set
for u in S:
for v in ADJACENT-NODES(u):
if v in S:
E_S <- E_S ∪ {(u, v)}
G_S <- (S, E_S)
return G_S
⚠️ 时间复杂度分析：
- 邻接表表示：遍历每条与 S 中节点相连的边，复杂度为 O(|E_S|)。
- 邻接矩阵表示：对每个 S 中的节点，遍历整行 V 个元素，总复杂度为 O(|S| * |V|)。
3.2 判断子图是否为导出子图
问题描述：给定图 G1 和它的子图 G2，判断 G2 是否是 G1 的导出子图。
✅ 判断条件：
- G2 中必须包含所有 G1 中两端点都在 G2 节点集合中的边。
✅ 算法思路：
- 遍历 G2 中每个节点 u；
- 遍历 G1 中 u 的所有邻接节点 v；
- 如果 (u, v) 不在 G2 的边集合中，说明 G2 缺失了某些边 → 不是导出子图。
algorithm CheckingIfSubgraphIsInduced(G1, G2):
// INPUT
// G1 = the input graph with nodes V1 and edges E1
// G2 = a subgraph of G1, with nodes V2 and edges E2 (V2 ⊆ V1 and E2 ⊆ E1)
// OUTPUT
// Returns true if G2 is an induced subgraph, false otherwise
for u in V2:
for v in ADJACENT-NODES(u):
if (u, v) not in E2:
return false
return true
3.3 判断某图是否为另一图的导出子图
问题描述：给定两个图 G1 和 G2，判断 G2 是否是 G1 的导出子图。
✅ 判断步骤：
- 检查 G2 的所有边是否都存在于 G1 中；
- 检查 G2 是否保留了所有应保留的边（即是否是导出子图）。
algorithm CheckInducedSubgraph(G1, G2):
// INPUT
// G1 = (V1, E1) - the input graph with nodes V1 and edges E1
// G2 = (V2, E2) - a graph of nodes in V1
// (so V2 ⊆ V1, but not necessarily E2 ⊆ E1)
// OUTPUT
// true, if G2 is an induced subgraph of G1
// false, otherwise
// First, check if G2 is a subgraph of G1
for (u, v) in E2:
if (u, v) is not in E1:
return false
// If yes, check if it is induced by V2
for u in V2:
for v in ADJACENT-NODES(u):
if (u, v) is not in E2:
return false
return true
3.4 导出子图同构（Induced Subgraph Isomorphism）
问题描述：给定两个图 G1 和 G2，是否存在一个映射 f，使得 G2 同构于 G1 的某个导出子图。
✅ 定义条件：
f 是从 G2 的节点集到 G1 的节点集的单射函数，满足：
- 相邻节点映射后仍相邻；
- 不相邻节点映射后仍不相邻。
⚠️ 问题性质：
- NP-Hard 问题，目前没有已知的多项式时间解法；
- 可以建模为约束满足问题（CSP）；
- 每个 G2 的节点对应一个 CSP 变量，变量的取值范围是 G1 的所有节点。
// 伪代码示意
algorithm InducedSubgraphIsomorphism(G1, G2):
// INPUT
// G1 = (V1, E1)
// G2 = (V2, E2)
// OUTPUT
// true if G2 is isomorphic to an induced subgraph of G1
// 尝试所有可能的节点映射
for each injective mapping f from V2 to V1:
if f preserves adjacency and non-adjacency:
return true
return false
4. 小结
导出子图是图论中非常重要的概念，其核心在于“保留邻接关系”。以下是几个关键点：
✅ 导出子图的构建：只需保留目标节点之间的所有边。
✅ 导出子图的验证：需确保没有遗漏应保留的边。
✅ 导出子图同构：属于 NP-Hard 问题，通常用 CSP 求解器处理。
📌 踩坑提醒：
- 不要混淆“普通子图”和“导出子图”的定义；
- 实现时注意边的遍历范围，避免重复添加；
- 判断导出子图时，不要遗漏“非邻接边”的检查；
- 同构问题复杂度高，实际中可能需要剪枝或启发式算法优化。