导出子图

在图论中，一个图的导出子图(induced subgraph)是指，由该图顶点的一个子集和该图中两端均在该子集的所有边的集合组成的图。

定义

其正式定义为：设图 ${\displaystyle G=(V,E)}$，令 ${\displaystyle S\subset V}$，使得 S 是 G 的任意顶点子集。则 G 的导出子图 ${\displaystyle G[S]}$ 中，其顶点集为 S，边集为 G 的边集 E 中两个顶点均属于 S 的边的集合。该定义适用于无向图，有向图与多重图。^[1]与子图（subgraph）的不同之处在于，导出子图中的两顶点间若在原图中有边，则导出子图中一定包含此边，而子图可包含或不包含该边。

导出子图 ${\displaystyle G[S]}$ 也可以称为 S 从 G 中导出的子图，或者 (如果上下文中G没有歧义) S 的导出子图。

1 sources

实例

导出子图的重要类型包括如下内容：

盒子中蛇的问题涉及到在超立方体图中的最长导出路径

• 导出路径是路径的子图。无权图中任意两个顶点之间的最短路径是一个导出路径，因为任意一对顶点之间的附加边，如果可能导致它不能被导出也会导致它不是最短。反之，在距离遗传图中，所有导出路径都是最短路径。^[2]
• 导出周期是诱导子图或循环。图的围长由其最短周期(导出周期)的长度决定。根据强完美图定理，导出周期及其补图在完美图的特征中处于至关重要的地位。^[3]
• 团和独立集分别为完全图和无边图的导出子图。
• 导出匹配是匹配的诱导子图。
• 一个顶点的邻域是与其相邻的所有顶点的导出子图。

2 sources

计算

导出子图同构问题是子图同构问题的一种形式，其目的是检验一个图是否可以作为另一个图的导出子图。因为它把分团问题作为一个特例，所以它是NP完备的。^[4]

1 sources

参考文献

1. Diestel, Reinhard, Graph Theory, Graduate texts in mathematics 173, Springer-Verlag: 3–4, 2006 [2019-06-14], ISBN 9783540261834, （原始内容存档于2021-01-25）
2. Howorka, Edward, A characterization of distance-hereditary graphs, The Quarterly Journal of Mathematics. Oxford. Second Series, 1977, 28 (112): 417–420, MR 0485544, doi:10.1093/qmath/28.4.417.
3. Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin, The strong perfect graph theorem, Annals of Mathematics, 2006, 164 (1): 51–229 [2019-06-14], MR 2233847, arXiv:math/0212070 , doi:10.4007/annals.2006.164.51, （原始内容存档于2010-06-18）.
4. Johnson, David S., The NP-completeness column: an ongoing guide, Journal of Algorithms, 1985, 6 (3): 434–451, MR 0800733, doi:10.1016/0196-6774(85)90012-4.