跳转到内容

导出子图

维基百科,自由的百科全书

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

定义

[编辑]

其正式定义为:设图 ,令 ,使得 SG 的任意顶点子集。则 G 的导出子图 中,其顶点集为 S,边集为 G 的边集 E 中两个顶点均属于 S 的边的集合。该定义适用于无向图有向图多重图[1]

导出子图 也可以称为 SG 中导出的子图,或者 (如果上下文中G没有歧义) S 的导出子图。

实例

[编辑]

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

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

计算

[编辑]

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

参考文献

[编辑]
  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 .