题4

题4

题目

Q:设有 个顶点的无向连通图的最小生成树不唯一，则下列说法中正确的是 ( ).
A. 图的边数一定大于
B. 图的权值最小的边一定有多条
C. 图的最小生成树的代价不一定相等
D. 图的各条边的权值不相等

分析

A:最小生成树，每次选择边权最小、同时不构成回路的边

解

A
若图的边数小于 ,则图不存在最小生成树;
若无向连通图的边数等于 ,则最小生成树唯一,即为图本身,所以图的边数一定大于 正确。
若最小生成树不唯一,则一定存在权值相等的边, 但未必是权值最小的边, 如下图所示, B 错误。
最小生成树可能不唯一, 但代价一定相同, 错误。
当图的各边的权值互不相等时,图的最小生成树是唯一的, 错误。