请问离散数学中的生成子图是什么意思?

2022-04-13 文化 245阅读

生成子图,亦称支撑子图,图论中一类图的统称。由一个图的全部顶点及连结这些顶点的部分边构成的图称为原图的支撑子图。若支撑子图是树,则为支撑树。在图论中,解决一些悬而未决的问题往往首先从树这类图入手。许多问题对一般的图未能解决或者没有简便的方法,而对于树,则已完满解决,且方法较为简便。



扩展资料

子图为图论的基本概念之一,节点集和边集分别是某一图的节点集的子集和边集的子集的图。若这个节点子集或边子集是真子集,则称这个子图为真子图;若图G的每一个节点也是它的子图H的节点,则称H是G的支撑子图。

设S是V(G)的子集,以S为节点集,以G的所有那些两端点都在S内的边组成边集,所得到的G的子图称为S在G中的导出子图,或更确切地,节点导出子图。设B是E(G)的子集,由G的所有与B内至少有一条边关联的节点组成节点集,以B为边集,所得到的G的子图称为B在G中的边导出子图。

参考资料来源:百度百科-支撑子图

参考资料来源:百度百科-子图

声明:你问我答网所有作品(图文、音视频)均由用户自行上传分享,仅供网友学习交流。若您的权利被侵害,请联系fangmu6661024@163.com