请教大家一下数据结构问题!在图中有个概念叫极大连通子图,想问为什么叫极大连通子图,感觉极大连通子图

请教大家一下数据结构问题!在图中有个概念叫极大连通子图,想问为什么叫极大连通子图,感觉极大连通子图好像就是连通子图,这样说是因为还有极小连通子图吗?但是书上也没有提到极小连通子图,网上有人说极小连通子图是连通图的生成树,这种说法是不是错误的!生成树是不连通的,怎么能说是连通子图呢?

你好,又是我
这些问题要从两方面来说
刚才已经说过,无向图分为连通图和非连通图
首先,说下连通图
连通图的极大…就是其本身,极小就是它的生成树
,所谓生成树,就是延连边遍历连通图上所有顶点,遍历过程中,会经历图上部分连边,但不一定经历所有边,我们把图上所有点加上遍历所经历的边构成一张图,就是生成树,例如矩形ABCD,从A开始遍历,经历边AB BC CD 这三条边加上四个顶点就是图ABCD的一颗生成树,但是边DA并不包含在内。因为遍历方法并不唯一,比如可以从其他点开始,也可以延不同的方向,所以生成树并不唯一,也就是极小…并不唯一
至于为什么叫极小,这是因为首先它要包含连通图中所有顶点,但是在多加一条边就会产生环,减少一条边就无法构成完整的生成树,另外,所有无向树都是连通图,不知道你为什么觉得生成树是非连通的…
总结,连通图中,极大为其本身,显然是唯一的,极小为其生成树,不唯一,
下面再说非连通图
非连通图按照极大连通子图的定义可以拆为数个极大,也称连通分量,每个分量显然都是连通图,这样又回到连通图的讨论上,已论述。
总结 非连通图标的极大和极小都不唯一

注:极大并非最大,类比数学中求函数的极大值和最大值
非连通的极大,其实图摆在你面前,你一眼就能看出来,哪些图是连在一起的,哪些没有,应该是很显然的事情吧,对照这个再看书上的定义 应该很好理解追问

谢谢啦!这几天没有看知道,现在懂了,非常感谢!

温馨提示:答案为网友推荐,仅供参考
相似回答