Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学暑期课《ACM/ICPC竞赛训练》面向全球招生!

Re:为什么是Prim最小树的最大边权就可以了?怎么证明这个最大值是最小的?

Posted by liaopifan at 2017-09-13 19:55:27 on Problem 2485
In Reply To:为什么是Prim最小树的最大边权就可以了?怎么证明这个最大值是最小的? Posted by:z__jj at 2009-03-12 23:42:54
在无向图G=(V,E)中。
若T为MST,边(u,v)为T中最长边;
反证法:假设生成树T'中的最长边(u’,v‘)<(u,v)
即为T’中的任意一条边(x,y)<=(u’,v‘)<(u,v);若去掉边(u,v),u属于集合A,v属于集合B,要联通AB必须要连接点集AB之间的一条边,T’为生成树,A,B已经联通,则连接的是一边(x,y)并且小于(u,v),此时图中无环,T‘=T-(u,v)+(x,y),T’比T更优。
则对于T为MST这个条件矛盾,所以不可能存在一个生成树的最长边小于MST的最长边。
最大权值最小的生成树也叫瓶颈生成树,MST就是其中的最小瓶颈生成树。
下面是生成树的一些性质。(上面运用了切割性质)
(1)切割性质:(各边边权均不相同)一条边是连接某两个集合的最小边,那么这条边就在最小生成树中
(2)回路性质:(各边边权均不相同)图若有回路,那么回路中的最长边一定不在最小生成树中
增量最小生成树:(动态加边,对于每条边加入后输出当前最小生成树),根据 “回路性质”复杂度O(n*m)
最小瓶颈生成树:(最大边权值尽量小),最小生成树就是这么一棵树
最小瓶颈路:(u到v的路径满足最大边权值尽量小),先求最小生成树,然后u到v的路径在树上是唯一的,取路径中最长的一条。
求任意两点的最小瓶颈路:O(n)枚举一个点,然后O(n)树形dp,总体复杂度O(n^2)。
次小生成树:1.prim()扩展,跟次短路一样的算法
2.先求最小生成树,每当边<u,v>加入后就会有环,删除环上除了边<u,v>以外的最长边(也就是删去u到v 之间的最小瓶颈路),所以先求出“任意两点的最小瓶颈路”(上面有)。
-----------------------------转载:http://blog.csdn.net/miracle_ma/article/details/43116981

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator