百度作业网亚瑟王(传说中的英国国王)在王宫中召见他的2n名骑士,其中某些骑士之间互相有仇,已知每个骑士的仇人不超过n－1个,证明：
来源：学生作业帮 编辑：百度作业网作业帮 分类：综合作业 时间：2024/06/25 10:04:24
亚瑟王(传说中的英国国王)在王宫中召见他的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
希望回答对你有所帮助!
用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
希望回答对你有所帮助!
求亚瑟王和圆桌骑士的传说,完整的.
亚瑟王和圆桌骑士的传说详细介绍
亚瑟王的圆桌骑士（名字）
1 从《亚瑟王》中看出中世纪骑士的什么特点 2 什么是骑士文学?它对文学发展有什么意义?
圆桌骑士每个骑士的称号是什么
谁知道亚瑟王的十二圆桌骑士的故事
约瑟夫问题:n个骑士编号1,2,.,围坐圆桌旁找出最后留在圆桌旁的骑士编号(1)编
亚瑟王的圆桌骑士分别是哪些?
一个英文表达方法有个问题 要表达亚瑟王和他骑士们的儿子是用Sons of King Arthur and his kni
历史上的亚瑟王和骑士兰斯洛特 到底是个什么关系啊?
英国的名词,贵族、骑士、骑士精神、绅士,怎么理解?
在中古西欧,一名骑士是怎样培养出来的?骑士的主要装备有哪些?骑士有哪些必须遵守的法规,惯律或戒律?