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

admin2019-01-16  16

问题 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://kaotiyun.com/show/UYRi777K
0

最新回复(0)