导出子图
定义
其正式定义为:设图G = (V, E),令S⊂V,使得S是G的任意顶点子集。则G的导出子图G(S)中,其顶点集为S,边集为G的边集E中两个顶点均属于S的边的集合。该定义适用于无向图,有向图与多重图。[1]
导出子图G[S]也可以称为S从G中导出的子图,或者(如果上下文中G没有歧义)S的导出子图。
实例
导出子图的重要类型包括如下内容:
参考文献
- Diestel, Reinhard, , Graduate texts in mathematics 173, Springer-Verlag: 3–4, 2006, ISBN 9783540261834
- Howorka, Edward, , 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, , Annals of Mathematics, 2006, 164 (1): 51–229, MR 2233847, arXiv:math/0212070, doi:10.4007/annals.2006.164.51.
- Johnson, David S., , Journal of Algorithms, 1985, 6 (3): 434–451, MR 800733, doi:10.1016/0196-6774(85)90012-4.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.