题13 题目 Q:设无向图 和 ,若 是 的生成树,则下列说法错误的是 ( ). A. 为 的子图 B. 为 的连通分量 C. 为 的极小连通子图且 D. 是 的一个无环子图 分析 A:连通分量是无向图的极大连通子图, 其中极大的含义是将依附于连通分量中顶点的所有边都加上, 所以连通分量中可能存在回路, 这样就不是生成树了。 注意 极大连通子图是无向图 (不一定连通) 的连通分量, 极小连通子图是连通无向图的生成树。 极小和极大是在满足连通的前提下, 针对边的数目而言的。 极大连通子图包含连通分量的全部边; 极小连通子图 (生成树) 包含连通图的全部顶点, 且使其连通的边数最少。 解 B