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 |
请大家讲讲这个构造法,我看不明白,是离散数学中关于哈密顿的经典构造(见内)In Reply To:请教大家对这题的解法 Posted by:c0500446123 at 2005-05-29 21:28:10 在hit上看到的 我在网上找到一种据说“很经典”的构造方法,没看明白,大家讨论一下吧: 由于每个人都与半数以上的人是朋友,这样就可以用调整法找到一个哈密顿圈。 把人与人的关系看作一个无向图,易证图是连通的。用贪心法找到一条极长路,设其为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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator