在学习数据结构图时，自己对极大连通子图、极小连通子图一类概念的理解，如有不妥，希望大家指正：
1、极大连通子图（即连通分量）、极小连通子图都为图的连通子图，极大即包含边最多，极小即包含边最少；
2、对于连通图
极大连通子图（包含边最多的连通子图）即本身（包含所有边）。
极小连通子图为某一顶点子集所确定的连通子图中包含边最少的连通子图（n个顶点，无向连通图最少n-1条边，有向连通图最少n条边——成环）。图全部顶点所确定的极小连通子图即为连通图的生成树。
3、对于非连通图
极大连通子图即为非连通图中连通的每一个部分（每一个连通部分包含边最多的连通子图即为该连通部分本身）。
极小连通子图为非连通图中每一连通部分的极小连通子图。由每一连通部分所有顶点所确定的极小连通子图即为该连通部分的生成树，各连通部分的生成树构成非连通图的生成森林。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
