求解一下问题,各位帮帮忙
今有2K(K>=2)个人去完成K项任务。已知每个人均能与另外2K-1个人中的的K个人中的任何人组成小组(每组两个人)去完成他们共同熟悉的任务,证明这2K个人一定能够分成K...
今有2K(K>=2)个人去完成K项任务。已知每个人均能与另外2K-1个人中的的K个人中的任何人组成小组(每组两个人)去完成他们共同熟悉的任务,证明这2K个人一定能够分成K组(每组两个人),每组完成一项他们共同熟悉的任务。
展开
2012-12-29
展开全部
设 V={v|v是去完成任务的人},
E={(u,v)|u,v∈V且u≠v且u,v能组成小组}
则得2k阶无向简单图G.由已知条件,任意u,v∈V,
d(u)+d(v)≥2k
由定理15.7的推论可知,G为哈密顿图。于是存在哈密顿回路。设C=vi1vi2...为其中的一条哈密顿回路,在C中相邻的顶点都能组成二人小组。所以可以分成k组。
E={(u,v)|u,v∈V且u≠v且u,v能组成小组}
则得2k阶无向简单图G.由已知条件,任意u,v∈V,
d(u)+d(v)≥2k
由定理15.7的推论可知,G为哈密顿图。于是存在哈密顿回路。设C=vi1vi2...为其中的一条哈密顿回路,在C中相邻的顶点都能组成二人小组。所以可以分成k组。
参考资料: http://cs.fjzs.edu.cn/ketang/lssxshort/part4/chapter15/ex15_07.htm
已赞过
已踩过<
评论
收起
你对这个回答的评价是?
亚远景信息科技
2024-12-11 广告
2024-12-11 广告
ASPICE,全称Automotive SPICE,中文译为汽车软件过程改进及能力评定,是评估和改进汽车软件开发流程的国际标准。它旨在提高软件开发的质量和效率,确保软件符合质量要求及安全、法规标准。ASPICE基于过程能力和过程改进两大核心...
点击进入详情页
本回答由亚远景信息科技提供
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询