2. 考研
  3. G=(V，E)是一个带有权的连通图，如图所示。 (1)什么是G的最小生成树? (2)G如图所示，请找出G的所有最小生成树。

G=(V，E)是一个带有权的连通图，如图所示。 (1)什么是G的最小生成树? (2)G如图所示，请找出G的所有最小生成树。

admin2019-01-16  18
问题 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)}
解析
转载请注明原文地址:https://jikaoti.com/ti/NpfjFFFM
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)