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

Re:关于最小生成树的最长边为所求的证明

Posted by eiwoqu at 2014-12-11 18:43:52 on Problem 2485
In Reply To:关于最小生成树的最长边为所求的证明 Posted by:1120121860 at 2013-08-07 10:54:00
楼主证的有一点问题,我来补充一下。
在u,v在T'的通路P上,必须找到一条边,这些边的两个点,在原图以(u,v)为分割的两个集合中,是分别属于两个集合的。
(这点通过反证,假设通路P为u,A,B,C,D,E,F,v,假设不存在分别属于(u,v)分割的两个集合,则u,A同一集合,A,B同一集合,B,C同一集合,...推出u,v同一集合,矛盾)
对于这条边,叫做(p,q)好了,那么对于原图T,将(u,v)删除,替换成(p,q)。(设想p本来就是在u集合那边,q就是在v集合那边)。那么这样就能找到更小的最小生成树了。与假设T是最小生成树矛盾。

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