在具有刀个顶点的图G中,若最小生成树不唯一,则( )。
A、
G的边数一定大于n一1
B、
G的权值最小的边一定有多条
C、
G的最小生成树代价不一定相等
D、
上述选项都不对
【正确答案】
A
【答案解析】
解析:G的最小生成树的边数为n—1,若最小生成树不唯一,则G的边数一定大于,n—1,A正确。在G中找到与最小生成树T中某条边e1权值相等的边e2,加入最小生成树中,则会产生一个环,就可以用e2来代替el,形成一个新的最小生成树E
T
=T—el+e2,这就使最小生成树不唯一,而边的权值在这里是任意的,并不是最小的,B错误。最小生成树的树形可能不唯一,但代价肯定是相等且是最小的,C错误。
提交答案
关闭