C++博客-Gauss的十九岁http://www.cppblog.com/yh-tsp/－－终于不明白了zh-cnTue, 09 Jun 2026 21:35:01 GMTTue, 09 Jun 2026 21:35:01 GMT60MST的更新，23.2-7http://www.cppblog.com/yh-tsp/archive/2008/01/11/41002.html被苹果砸到了被苹果砸到了Fri, 11 Jan 2008 15:59:00 GMThttp://www.cppblog.com/yh-tsp/archive/2008/01/11/41002.htmlhttp://www.cppblog.com/yh-tsp/comments/41002.htmlhttp://www.cppblog.com/yh-tsp/archive/2008/01/11/41002.html#Feedback1http://www.cppblog.com/yh-tsp/comments/commentRss/41002.htmlhttp://www.cppblog.com/yh-tsp/services/trackbacks/41002.html
引理  设T是G（V，E）的最小生成树，G‘是G（V‘，E’）的子图。若T’＝E－T，则G‘的最小生成树不包括T’中的边。

事实   对于任意点对（u,v)属于V，如果Kruskal算法在G上运行后这些向量是属于同一个集合的，那么在G‘上运行Kruskal算法后，它们仍然属于同一个集合。

后面就是对上面两个的证明，好难看啊，直接看结论。

已 知G‘（V’，E‘）是G（V，E）加入一个新的节点和其所属的边后构成的新图。设T是G的MST。计算G’的MST，构造新图G“（V‘，E”），E “包括T和E‘－E，然后找出G“的MST，T‘。由于引理，G’的MST不包含E－T。还句话说，G‘包括T和E’－E。这些边精确的包括在E”中。于 是，G“的MST，T‘，也是G’的MST。

尽管证明引理用的是Kruskal算法，但不需要使用它。我们使用Prim算法和Fibonacci-heap priority queue。
最后得出结论计算G‘的MST需要O（VlgV）。

过程复述一下：（以下简称MST为T，以标号区分）
已经得到G的T，加入一个节点和边后构成G‘。为了计算G’的T‘，则用T和新加入的边构成G“，
用Prim计算G“的T”，根据引理，T“＝T‘，完毕。

23时51分36秒
于校






被苹果砸到了 2008-01-11 23:59 发表评论
]]>