最后6个人如何构图?(关于将2006个人分成若干个不相交的子集.
题目
最后6个人如何构图?(关于将2006个人分成若干个不相交的子集.
将2006个人分成若干个不相交的子集,每个子集至少有3个人,并且:
(1)每个子集中,没有人全部认识其他人;
(2)同1子集的任意3个人中至少有2个互不认识;
(3)对同1子集中任何2个互不认识的人,在该子集中恰有1个人同时认识这2个人.
问:满足上述条件的子集最多有多少个?
我知道是401个,我也知道前2000人每5人一组分400组.最后6个人无论怎样构造图都不能同时满足3个条件!望哪位高手能说说6个人怎么构图才行?
答案
6个人不行
由条件2,图各顶点的度应该相同
由条件3,图中不能有4边型
设顶点的度是a,边数是b,对6个顶点的图来说
6a=2b
a=b/3
边是3的倍数
最小的是6,度是2,每个点有两条边,就是6边形,显然条件3不满足
9,度是3,每个点有3条边相连,就是6边型连接对顶点.此时出现4边型,不满足条件3
对于度数更大的情况总会出现三角形,四边形,不满足条件.
因此6顶点不行
举一反三
我想写一篇关于奥巴马的演讲的文章,写哪一篇好呢?为什么好
最新试题
- 在气温25摄氏度,气压96.8kPa的现场采集空气15L,试将其换算为标准状态下的采气体积
- 在世界上是in the world 还是in world.有什么区别?
- 求鲁迅《药》的读后感,800字以上.
- 函数f(x)=1/3x^3-2ax+3a^2x在(0,1)内有极小值,则实数a的取值范围
- shall we_have some bananas a.too b.also c.either d.neither
- Cos all i ever do is try to be,all that i can be Girl you know your hurting me,all the things
- 稠环芳香烃的命名
- 若tanθ=2,则1sin^2θ-cos^2θ=
- 如果x=1时,式子px3+qx+1的值为2013,则当x=-1时,式子px3+qx+1的值是_.
- 1 已知椭圆:X平方除以16+Y平方除以4=1 的左右焦点F1和F2,点P在直线l:X-√3Y+8+2√3=0上.当角F1PF2取最大值时,|PF1|除以|PF2|的值为
热门考点