离散数学中有关图论中的极大连通子图的概念理解

离散数学中有关图论中的极大连通子图的概念理解
我看书上说 “任意增加结点或边所得的子图都是不连通的.”这句话不理解 谁能画图举例说明呀?
我是东天 1年前 已收到1个回答 举报

lylt 幼苗

共回答了18个问题采纳率:94.4% 举报

一个图可能是不连通的,它的极大连通子图实际上就是一个连通分支.

1年前 追问

10

我是东天 举报

那么这个连通分支任意增加结点或边所得子图都是不连通的吗?

举报 lylt

对一个给定的图,它的连通分支是确定的,对连通分支增加结点或边时整个图就变了。

我是东天 举报

我知道整个图就变了 增加边或结点可能由原来的不连通图变成了连通图啊,或者由原来的连通图变成不连通的啊 为什么所得子图都是不连通的啊? 感觉所得子图可能也是联通的哦

举报 lylt

比如这个图G,有两个连通分支,左边的是一个G1,右边的是一个G2.

对图G的任意连通子图,都不能真包含G1或G2,这就是“G1与G2是G的极大连通子图”的意思。

“对连通分支任意增加结点或边”是在整个图G的限制下增加的,增加后的图还是G的子图,当然就不连通了。

可能相似的问题
Copyright © 2024 YULUCN.COM - 雨露学习互助 - 17 q. 1.117 s. - webmaster@yulucn.com