算法|图最小生成树|问题8

考虑顶点集{V1，V2，V}上的加权完全图G，使得边（V，V）的权重为2πJJ。G的最小生成树的权重为：（GATE CS 2006）

（A） n-1 （B） 2n-2 （C） nC2 （D） 2. 答复: （B） 说明： 这种图的最小生成树是

v1
  
    v2
      
       v3
         
          v4
            .
              .
                .
                 vn
 

最小生成树的权重 = 2|2 – 1| + 2|3 – 2| + 2|4 – 3| + 2|5 – 4| …. + 2 | n–（n-1）| =2n-2 这个问题的小测验