企源知识库

如果无向图G的最小生成树中含有边（a，b）和（a，c）,则下列选项中，—定不在T中的边是

A、(b，c)
B、(b，d)
C、(c，d)
D、(c，e)
【正确答案】：A
【题目解析】：最小生成树是：一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。只有答案A（b，c）这条边是多余的。