亚瑟王(传说中的英国国王)在王宫中召见他的2n名骑士,其中某些骑士之间互相有仇,已知每个骑士的仇人不超过n－1个,证明：摩尔林(亚瑟王的谋士)能够让这些骑士围着圆桌坐下,使每个骑士都
来源：学生作业帮助网 编辑：六六作业网 时间：2024/11/21 20:03:20
亚瑟王(传说中的英国国王)在王宫中召见他的2n名骑士,其中某些骑士之间互相有仇,已知每个骑士的仇人不超过n－1个,证明：摩尔林(亚瑟王的谋士)能够让这些骑士围着圆桌坐下,使每个骑士都
亚瑟王(传说中的英国国王)在王宫中召见他的2n名骑士,其中某些骑士之间互相有仇,已知每个骑士的仇人不超过n－1个,证明：摩尔林(亚瑟王的谋士)能够让这些骑士围着圆桌坐下,使每个骑士都不与他的仇人相邻．
亚瑟王(传说中的英国国王)在王宫中召见他的2n名骑士,其中某些骑士之间互相有仇,已知每个骑士的仇人不超过n－1个,证明：摩尔林(亚瑟王的谋士)能够让这些骑士围着圆桌坐下,使每个骑士都
证明:
用2n个顶点表示这2n个骑士,如果骑士x和y不是仇人,那么在x和y之间连接一条边.问题转化为证明图中有一个包含所有顶点的环,即哈密顿环.
用反证法,假设图中没有哈密顿环.那么我们可以在图中添加若干条(可以为0)边,使得如果再连接图中任意一对不相邻的顶点后,图中都有一个哈密顿环(很明显这总是能做到的).
添加完边后,任取图中两个不相邻的顶点u,v,因为连接u,v将产生一个哈密顿环.那么u.v之间有一条长2n的的路径包含所有2n个顶点:
u(=v1),v2,v3,v4.v2n-1,v(=v2n)
vi和vi+1(1≤i≤2n-1)相邻
另一方面,记集合
S(u)={i|u与vi+1相邻,1≤i≤2n-1}
S(v)={i|v与vi相邻,1≤i≤2n-1}
那么|S(u)|≥2n-1-(n-1)=n,|S(v)|≥2n-1-(n-1)=n
由抽屉原理,有一个i使得u与vi+1相邻且v与vi相邻,这样u,vi+1...v2n-1,v,vi,vi-1,.v2,u这个环包含所有2n个顶点,是一个哈密顿环,与我们当初断言的图中没有哈密顿环矛盾.
所以原图中必有哈密顿环,也就是这样的骑士安排是可以做到的,得证.
实际上,刚才的证明方法可以启发我们找到一个构造哈密顿环的算法:
STEP 1:在图中任意找一个环C
STEP 2:任取C中相邻两点u,v,由图是连通的(有哈密顿环),必有一顶点w使得:
(1)w不在C上
(2)w与u,v均连通
STEP3:断开u,v边,连接w与u,v之间的路径得到一个更大的环C'
STEP4:若C'包含所有2n个顶点,退出.否则令C=C',转STEP2
希望回答对你有所帮助!