题3

题3

题目

Q:以下叙述中, 正确的是 ( ).
A. 只要无向连通图中没有权值相同的边, 则其最小生成树唯一
B. 只要无向图中有权值相同的边, 则其最小生成树一定不唯一
C. 从 个顶点的连通图中选取 条权值最小的边,即可构成最小生成树
D. 设连通图 含有 个顶点,则含有 个顶点、 条边的子图一定是 的生成树

分析

A:最小生成树算法是基于贪心策略的, 每次总是选取权值最小且满足条件的边, 若各边权值不同, 则每次选择的新顶点也是唯一的, 因此最小生成树唯一, A 正确。
对于 B, 若无向图本身就是一棵树,则最小生成树就是它本身,这时就是唯一的。
对于 ,选取的 条边可能构成回路。
对于 ,含有 个顶点、 条边的子图可能构成回路,也可能不连通。

解

A