问答题
G=(V，E)是一个带有权的连通图，如图所示。
(1)什么是G的最小生成树?
(2)G如图所示，请找出G的所有最小生成树。
【正确答案】(1)无向连通图的生成树包含图中全部n个顶点，以及足以使图连通的n-1条边。而最小生成树则是各边权值之和最小的生成树。
(2)最小生成树有两棵。下面给出顶点集合和边集合，编以三元组(Vi，Vj，W)形式，其中W代表权值。
V(G)={1，2，3，4，5}
E1(G)={(4，5，2)，(2，5，4)，(2，3，5)，(1，2，7)}；
E2(G)={(4，5，2)，(2，4，4)，(2，3，5)，(1，2，7)}
(2)最小生成树有两棵。下面给出顶点集合和边集合，编以三元组(Vi，Vj，W)形式，其中W代表权值。
V(G)={1，2，3，4，5}
E1(G)={(4，5，2)，(2，5，4)，(2，3，5)，(1，2，7)}；
E2(G)={(4，5，2)，(2，4，4)，(2，3，5)，(1，2，7)}
【答案解析】此题考查的知识点是最小生成树的定义。该题说明图的最小生成树不唯一，但权值和唯一，出现两个或两个以上的情况是因为有权值相同的边。牢记Prim(选图的顶点)、Kruskal(选图的边，边上权值排序)两种算法的区别及算法步骤。