对于含有n个顶点的带权连通图，它的最小生成树是指()。

Question

A.图中任意一个由n-l条权值最小的边构成的子图
B.图中任意一个由n-1条权值之和最小的边构成的子图
C.图中任意一个由n-1条权值之和最小的边构成的连通子图
D.图中任意一个由n个顶点构成的边的权值之和最小的连通子图

Answer 1

【答案】：D
一个连通图的生成树(连通无回路图)是一个极小连通子图。它含有图中全部n个项点，但只有构成一棵树的(n-1)条边。如果小于(n-1)条边，则是非连通图；如果多于(n-1)条边，则一定有回路，因为这条边使得它依附的那两个顶点之间有了第二条路径。但是，有(n-1)条边的图不一定都是生成树。带权连通无向图的所有生成树中具有边上的权值之和最小的树称为图的最小生成树。总之，含有n个顶点的带权连通图，它的最小生成树是指图中任意一个由n个顶点构成的边的权值之和最小的连通子图。