作业帮 > 数学 > 作业

图论的证明题证明9个人中若非至少有4人互相认识,则至少有3个人互相不认识题目取自《图论与袋鼠结构》的习题中

来源:学生作业帮 编辑:作业帮 分类:数学作业 时间:2020/09/19 09:46:41
图论的证明题
证明9个人中若非至少有4人互相认识,则至少有3个人互相不认识
题目取自《图论与袋鼠结构》的习题中
(1).有某人认识的人少于5个,不认识的人至少有4个,如A不认识B,C,D,E.
如果B,C,D,E中有2人不认识,则他们与A,3个人互相不认识;
如果B,C,D,E都认识,则他们4人互相认识.
(2).每个人认识的人不少于5个.
首先,9个人认识的人数的总和一定是偶数,因为若A,B认识,这个关系A在记数是计了1次,B在计数时也计了1次.每个关系对总和的贡献都是2.如果每个人恰认识5人,则9个人认识的人数的总和等于9*5=45,矛盾.
所以,至少有1个人A认识6人.由熟知的结果,这6人中或有3人互相不认识,或有3人互相认识,这3人与A,4人互相认识.
这是图论中的拉姆赛问题,本题就是证明拉姆赛数R(3,4)=9.
6人中或有3人互相不认识,或有3人互相认识,是拉姆赛数R(3,3)=6.