求解一下问题,各位帮帮忙
今有2K(K>=2)个人去完成K项任务。已知每个人均能与另外2K-1个人中的的K个人中的任何人组成小组(每组两个人)去完成他们共同熟悉的任务,证明这2K个人一定能够分成K...
今有2K(K>=2)个人去完成K项任务。已知每个人均能与另外2K-1个人中的的K个人中的任何人组成小组(每组两个人)去完成他们共同熟悉的任务,证明这2K个人一定能够分成K组(每组两个人),每组完成一项他们共同熟悉的任务。
展开
1个回答
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-08-28 广告
2024-08-28 广告
在当今竞争激烈的商业环境中,企业需要不断提高自身的竞争力,以保持市场份额和增加利润。通过人效提升,企业可以更有效地利用有限的资源,提高生产力和效益,从而实现盈利目标。中智咨询提供全方位的组织人效评价与诊断、人效提升方案等数据和管理咨询服务。...
点击进入详情页
本回答由中智咨询提供
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询