亚瑟王(传说中的英国国王)在王宫中召见他的2n名骑士,其中某些骑士之间互相有仇,已知每个骑士的仇人不超过n-1个,证明:摩尔林(亚瑟王的谋士)能够让这些骑士围着圆桌坐下,使每个骑士都
来源:学生作业帮助网 编辑:作业帮 时间:2024/06/30 07:48:38
![亚瑟王(传说中的英国国王)在王宫中召见他的2n名骑士,其中某些骑士之间互相有仇,已知每个骑士的仇人不超过n-1个,证明:摩尔林(亚瑟王的谋士)能够让这些骑士围着圆桌坐下,使每个骑士都](/uploads/image/z/11595594-66-4.jpg?t=%E4%BA%9A%E7%91%9F%E7%8E%8B%28%E4%BC%A0%E8%AF%B4%E4%B8%AD%E7%9A%84%E8%8B%B1%E5%9B%BD%E5%9B%BD%E7%8E%8B%29%E5%9C%A8%E7%8E%8B%E5%AE%AB%E4%B8%AD%E5%8F%AC%E8%A7%81%E4%BB%96%E7%9A%842n%E5%90%8D%E9%AA%91%E5%A3%AB%2C%E5%85%B6%E4%B8%AD%E6%9F%90%E4%BA%9B%E9%AA%91%E5%A3%AB%E4%B9%8B%E9%97%B4%E4%BA%92%E7%9B%B8%E6%9C%89%E4%BB%87%2C%E5%B7%B2%E7%9F%A5%E6%AF%8F%E4%B8%AA%E9%AA%91%E5%A3%AB%E7%9A%84%E4%BB%87%E4%BA%BA%E4%B8%8D%E8%B6%85%E8%BF%87n%EF%BC%8D1%E4%B8%AA%2C%E8%AF%81%E6%98%8E%EF%BC%9A%E6%91%A9%E5%B0%94%E6%9E%97%28%E4%BA%9A%E7%91%9F%E7%8E%8B%E7%9A%84%E8%B0%8B%E5%A3%AB%29%E8%83%BD%E5%A4%9F%E8%AE%A9%E8%BF%99%E4%BA%9B%E9%AA%91%E5%A3%AB%E5%9B%B4%E7%9D%80%E5%9C%86%E6%A1%8C%E5%9D%90%E4%B8%8B%2C%E4%BD%BF%E6%AF%8F%E4%B8%AA%E9%AA%91%E5%A3%AB%E9%83%BD)
亚瑟王(传说中的英国国王)在王宫中召见他的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
希望回答对你有所帮助!