查看“︁导出子图”︁的源代码

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

== 定义 ==
其正式定义为：设图 <math>G=(V,E)</math>，令 <math>S\subset V</math>，使得 {{mvar|S}} 是 {{mvar|G}} 的任意[[顶点 (图论)|顶点]]子集。则 {{mvar|G}} 的导出子图 <math>G[S] </math> 中，其顶点集为 {{mvar|S}}，边集为 {{mvar|G}} 的边集 {{mvar|E}} 中两个顶点均属于 {{mvar|S}} 的边的集合。该定义适用于[[图 (数学)|无向图]]，[[有向图]]与[[多重图]]。<ref>{{Citation|title=Graph Theory|volume=173|series=Graduate texts in mathematics|first=Reinhard|last=Diestel|publisher=Springer-Verlag|year=2006|isbn=9783540261834|pages=3–4|url=https://books.google.com/books?id=aR2TMYQr2CMC&pg=PA3|accessdate=2019-06-14|archive-date=2021-01-25|archive-url=https://web.archive.org/web/20210125064543/https://books.google.com/books?id=aR2TMYQr2CMC&pg=PA3|dead-url=no}}</ref>与子图（subgraph）的不同之处在于，导出子图中的两顶点间若在原图中有边，则导出子图中一定包含此边，而子图可包含或不包含该边。

导出子图 <math>G[S] </math> 也可以称为 {{mvar|S}} 从 {{mvar|G}} 中导出的子图，或者 (如果上下文中{{mvar|G}}没有歧义) {{mvar|S}} 的导出子图。

== 实例 ==
导出子图的重要类型包括如下内容：
[[File:Snake in the box.svg|缩略图|[[盒子中的蛇|盒子中蛇]]的问题涉及到在[[超立方体图]]中的最长[[导出路径]]]]

* [[导出路径]]是[[道路 (图论)|路径]]的子图。无权图中任意两个[[顶点 (图论)|顶点]]之间的[[最短路径]]是一个导出路径，因为任意一对顶点之间的附加边，如果可能导致它不能被导出也会导致它不是最短。反之，在[[距离遗传图]]中，所有导出路径都是最短路径。<ref>{{Citation|last=Howorka|first=Edward|title=A characterization of distance-hereditary graphs|journal=The Quarterly Journal of Mathematics. Oxford. Second Series|volume=28|number=112|year=1977|pages=417–420|mr=0485544|url=http://qjmath.oxfordjournals.org/cgi/reprint/28/4/417|doi=10.1093/qmath/28.4.417}}.</ref>
* [[导出循环|导出周期]]是诱导子图或[[環 (圖論)|循环]]。图的[[圍長 (圖論)|围长]]由其最短周期(导出周期)的长度决定。根据[[强完美图定理]]，导出周期及其[[補圖|补图]]在[[完美图]]的特征中处于至关重要的地位。<ref>{{Citation|last=Chudnovsky|first=Maria|author-link=Maria Chudnovsky|last2=Robertson|first2=Neil|author2-link=Neil Robertson (mathematician)|last3=Seymour|first3=Paul|author3-link=Paul Seymour (mathematician)|last4=Thomas|first4=Robin|author4-link=Robin Thomas (mathematician)|doi=10.4007/annals.2006.164.51|number=1|journal=[[Annals of Mathematics]]|pages=51–229|title=The strong perfect graph theorem|url=http://annals.princeton.edu/annals/2006/164-1/p02.xhtml|volume=164|year=2006|mr=2233847|arxiv=math/0212070|accessdate=2019-06-14|archive-date=2010-06-18|archive-url=https://web.archive.org/web/20100618172636/http://annals.princeton.edu/annals/2006/164-1/p02.xhtml|dead-url=no}}.</ref>
* [[團 (圖論)|团]]和[[独立集]]分别为[[完全圖|完全图]]和[[无边图]]的导出子图。
* 导出匹配是[[匹配 (图论)|匹配]]的诱导子图。
* 一个[[顶点 (图论)|顶点]]的[[邻域(图论)|邻域]]是与其相邻的所有顶点的导出子图。

== 计算 ==
[[导出子图同构问题]]是[[子图同构问题]]的一种形式，其目的是检验一个图是否可以作为另一个图的导出子图。因为它把[[分團問題|分团问题]]作为一个特例，所以它是[[NP完全|NP完备]]的。<ref>{{Citation|last=Johnson|first=David S.|doi=10.1016/0196-6774(85)90012-4|number=3|journal=Journal of Algorithms|mr=800733|pages=434–451|title=The NP-completeness column: an ongoing guide|volume=6|year=1985}}.</ref>

== 参考文献 ==
{{Reflist}}
[[Category:图论组成结构]]
[[Category:有未审阅翻译的页面]]