单选题
下面的说法中正确的是______。
A.图的一棵最小生成树的代价不一定比该图其他任何一棵生成树的代价小
B.带权连通图的最小生成树可能不唯一,但权值最小的边一定出现在解中
C.若带权连通图上各边上的权值互不相同,则该图的最小生成树是唯一的
D.一个带权连通图的最小生成树的权值之和不是唯一的
A
B
C
D
【正确答案】
C
【答案解析】
[解析] 带权连通图中的所有生成树中权值之和最小的生成树为该图的最小生成树,因此选项A错误。当一个顶点存在指向自己的回边的时候,不论该回边权值大小如何,都不会被纳入生成树的边集合中,因此选项B不正确。在图中每边的权值都不同的情况下,最小生成树一定由权值最小的n-1条边构成,必然是唯一的,因此选项C正确。一个带权连通图中最小生成树的权值之和等于不构成环的n-1条边的权值总和,必然是唯一的,因此选项D不正确。
提交答案
关闭