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

但是我没有北大的离散教程,学离散时用的英文版,提到了这个算法,讲了构造法,但是我中文都不太理解。。

Posted by sunmoonstar_love at 2005-06-29 22:23:34 on Problem 2438
In Reply To:请大家讲讲这个构造法,我看不明白,是离散数学中关于哈密顿的经典构造(见内) Posted by:sunmoonstar_love at 2005-06-29 22:05:22
用容斥原理易证有ai(1<i<k)使a1与ak相连且ai+1与a1相连,

这一点,怎么证的?




> 
> 由于每个人都与半数以上的人是朋友,这样就可以用调整法找到一个哈密顿圈。 
> 
> 把人与人的关系看作一个无向图,易证图是连通的。用贪心法找到一条极长路,设其为a1,a2,……,ak。用容斥原理易证有ai(1<i<k)使a1与ak相连且ai+1与a1相连,再连a1-ai+1与ai-ak,使ai与ai+1断开,则这条路变成了一个环。由于图是连通的,从这个环的某处断开必能找到一个更长的极长路,就这样反复找下去,最后那个最大的环就是该图的哈密顿圈。

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