门|门CS 2012 |问题27

设G是边权大于1的加权图，G’是通过将G中边的权平方而构造的图。设T和T’分别是G和G’的最小生成树，总权为T和T’。以下哪项陈述是正确的？ （A） T’=T，总重量T’=T ^2. （B） T’=T，总重量T’ 2. （C） T’！=但总重量T’=T ^2. （D） 以上都不是 答复: （D） 说明： 在加权图中，对边的权重求平方不会改变最小生成树 .假设相反，得到一个矛盾。如果最小生成树发生了变化，那么旧最小生成树T中的旧图G中的至少一条边必须替换为树T’中的新边，该边具有平方边权重。来自G’的新边的权重必须低于来自G的边。这意味着存在一些权重C1和C2，使得C1 =C22。这是一个矛盾。 资料来源： http://www.cs.nyu.edu/courses/spring06/V22.0310-001/hw3.htm

两个或更多数字的平方和总是小于平方和。 示例：2^2+2^2

但是

there is one counter example when the graph has only one edge.  
         In that case, the two values are same. 

这个问题的小测验