Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:对prim算法算出的结果表示怀疑,以上回答都不能充分证明这个问题。。In Reply To:对prim算法算出的结果表示怀疑,以上回答都不能充分证明这个问题。。 Posted by:swust20105592 at 2011-12-20 19:06:49 最小生成树的边权序列是唯一的。网上很多证明。 如果有另一个路网满足要求,且最大边权L比最小生成树中T的最大边权l小。 那么路网连通,有最小生成树t. (1)如果L的边不在最小生成树t边,显然矛盾. (2)L的边在t中.那么对于T的最大边(u,v).t中有一条u->v的路径.且路径上边权均不大于l.用其中一边替代(u,v).即(u,v)是原图中某个回路的唯一最大边.故不存在包括(u,v)的原图的最小生成树。与T是原图的最小生成树矛盾. Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator