亚瑟王(传说中的英国国王)在王宫中召见他的2n名骑士,其中某些骑士之间互相有仇,已知每个骑士的仇人不超过n－1个,证明：摩尔林(亚瑟王的谋士)能够让这些骑士围着圆桌坐下,使每个骑士都不与他的仇人相邻．

分类: 作业答案 • 2022-01-09 18:05:45

问题描述：

答

证明:用2n个顶点表示这2n个骑士,如果骑士x和y不是仇人,那么在x和y之间连接一条边.问题转化为证明图中有一个包含所有顶点的环,即哈密顿环.用反证法,假设图中没有哈密顿环.那么我们可以在图中添加若干条(可以为0)边,使...