将2006 个人分成若干不相交的子集,每个子集至少有 3 个人,并且:
问题描述：
将2006 个人分成若干不相交的子集,每个子集至少有 3 个人,并且:
1.将2006 个人分成若干不相交的子集,每个子集至少有 3 个人,并且:
(1)在每个子集中,没有人认识该子集的所有人.
(2)同一子集的任何 3 个人中,至少有 2 个人互不认识.
(3)对同一子集中任何 2 个不相识的人,在该子集中恰好只有 1 个人认识这两个人.则满足上述条件的子集最多能有___________个
一定要有完整的过程
答
06年的pascal语言提高组试题填空第一个,
运用图论的思想
用一个结点代表一个人,如果两个人互相认识就用线连上,不认识就不连；
原题的要求就变成了这样：
1,没有一个结点与其他所有点相连
2,每个子集中,任何三个结点中,至少两个不相连
3,同一子集中的任意不直接相连的两点,彼此之间有只通过一个结点的路径
然后拿一张纸,一只笔,画啊
三个结点,不行；
四个结点,不行；
五个结点,连成五边形可以了
说明每个子集至少有五个结点,然后就简单了
2006div5:=401
答案是401个