^Diestel, Reinhard, Graph Theory, Graduate texts in mathematics 173, Springer-Verlag: 3–4, 2006 [2019-06-14], ISBN 9783540261834, (原始内容于2021-01-25)
^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.
^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.
二月 17, 2023
导出子图, 在图论中, 一个图的, induced, subgraph, 是指, 由该图顶点的一个子集和该图中两端均在该子集的所有边的集合组成的图, 目录, 定义, 实例, 计算, 参考文献定义, 编辑其正式定义为, 设图, displaystyle, displaystyle, subset, 使得, 的任意顶点子集, displaystyle, 其顶点集为, 边集为, 的边集, 中两个顶点均属于, 的边的集合, 该定义适用于无向图, 有向图与多重图, displaystyle, 也可以称为, 中导出的子图, 或. 在图论中 一个图的导出子图 induced subgraph 是指 由该图顶点的一个子集和该图中两端均在该子集的所有边的集合组成的图 目录 1 定义 2 实例 3 计算 4 参考文献定义 编辑其正式定义为 设图 G V E displaystyle G V E 令 S V displaystyle S subset V 使得 S 是 G 的任意顶点子集 则 G 的导出子图 G S displaystyle G S 中 其顶点集为 S 边集为 G 的边集 E 中两个顶点均属于 S 的边的集合 该定义适用于无向图 有向图与多重图 1 导出子图 G S displaystyle G S 也可以称为 S 从 G 中导出的子图 或者 如果上下文中G 没有歧义 S 的导出子图 实例 编辑导出子图的重要类型包括如下内容 盒子中蛇的问题涉及到在超立方体图中的最长导出路径 导出路径是路径的子图 无权图中任意两个顶点之间的最短路径是一个导出路径 因为任意一对顶点之间的附加边 如果可能导致它不能被导出也会导致它不是最短 反之 在距离遗传图中 所有导出路径都是最短路径 2 导出周期是诱导子图或循环 图的围长由其最短周期 导出周期 的长度决定 根据强完美图定理 导出周期及其补图在完美图的特征中处于至关重要的地位 3 团和独立集分别为完全图和无边图的导出子图 导出匹配是匹配的诱导子图 一个顶点的邻域是与其相邻的所有顶点的导出子图 计算 编辑导出子图同构问题是子图同构问题的一种形式 其目的是检验一个图是否可以作为另一个图的导出子图 因为它把分团问题作为一个特例 所以它是NP完备的 4 参考文献 编辑 Diestel Reinhard Graph Theory Graduate texts in mathematics 173 Springer Verlag 3 4 2006 2019 06 14 ISBN 9783540261834 原始内容存档于2021 01 25 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 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 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 取自 https zh wikipedia org w index php title 导出子图 amp oldid 71734130, 维基百科,wiki,书籍,书籍,图书馆,