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

北大离散数学教程定理8.7的特殊推论,图论作业...

Posted by ArXoR at 2005-06-29 22:14:30 on Problem 2438
In Reply To:请大家讲讲这个构造法,我看不明白,是离散数学中关于哈密顿的经典构造(见内) Posted by:sunmoonstar_love at 2005-06-29 22:05:22
> 在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:
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