题11

题11

题目

Q:设有无向图 和 ,若 是 的生成树,则下列不正确的是 ( ).
I. 为 的连通分量
II. 为 的无环子图
III. 为 的极小连通子图且
A. I、 II
B. 只有 III
C. II、III
D. 只有 I

分析

A:强连通分量：有向图中的极大连通子图
生成树：包含图中全部顶点的一个极小连通图
注意区别，极大连通子图和极小连通图
极小连通子图: 一个连通图的极小连通子图是指，该子图是连通的，但删除任意一条边都会导致该子图不再连通。
极大连通子图: 一个图的极大连通子图是指，该子图是连通的，并且在该图中无法找到包含该子图且更大的连通子图。
“并且在该图中无法找到包含该子图且更大的连通子图”有点拗口，意思是：一个图的连通分量是该图中一个最大的结点集合，集合中的任意两个结点之间都存在路径，并且无法再将图中的其他结点加入到这个集合中，否则就会破坏连通性。
生成树是极小连通子图: 生成树包含了原图中的所有顶点，并且边的数量最少，删除任意一条边都会导致图不再连通，因此生成树是原图的一个极小连通子图。
连通分量和极大连通子图是同一个概念
和这个题目一起看，了解强连通分量的概念：题13

解

D
一个连通图的生成树是一个极小连通子图, 显然它是无环的, 所以选项 II、III 正确。
极大连通子图称为连通分量, 连通但非连通分量。
这里再补充一下 “极大连通子图”: 若图本来就不是连通的, 且每个子部分包含其本身的所有顶点和边, 则它就是极大连通子图。