早教吧作业答案频道 -->数学-->
一道图论题求证:在一群不少于三人的人中,若任何两人都刚好只有一个共同认识得人,证明这群人中总有一人是所有人都认识的.
题目详情
一道图论题
求证:在一群不少于三人的人中,若任何两人都刚好只有一个共同认识得人,证明这群人中总有一人是所有人都认识的.
求证:在一群不少于三人的人中,若任何两人都刚好只有一个共同认识得人,证明这群人中总有一人是所有人都认识的.
▼优质解答
答案和解析
我用反证法来证明.事实上要满足“任何两人都刚好只有一个共同认识得人”这个条件的这群人必须是奇数.
首先用一个点来代表一个人,如果A认识B,就在AB间连一条线,这样整个关系生成一个无向图G.
那么由“任何两人都刚好只有一个共同认识得人”,能得出G中没有4边形,即不存在4点A,B,C,D使得,A与B,B与C,C与D,D与A之间均有线相连.
设连线最多的点为P,与它相连的点为Q1~QK,不与它相连的点为R1~RL(L>0).
1.根据P与Q1~QK中的每个点形成的点对都“只有一个共同认识得朋友”,而该朋友又不在R1~RL中的这个属性,能够得出Q1~QK这K个点必满足K
为偶数且这些点之间的连线情况必定是分为K/2个组,每组2个点它们之间有连线,除此之外Q1~QK间无其它连线;否则会有某对点的“共同认识得朋友”超过1个.
2.根据P与R1~RL中的每个点形成的点对都“只有一个共同认识得朋友”,而该朋友又不在R1~RL中的这个属性,能够得出每个R1~RL中的点只与
P1~PK中的一个点有连线;否则会有某对点的“共同认识得朋友”超过1个.
3.根据Q1~QK中每个点与R1~RL中每个点都“只有一个共同认识得朋友”,再利用前面1与2的结论可以得出Q1~QK中的每个点都与R1~RL中的点有
连线;否则会有某对点的“共同认识得朋友”超过1个.
4.再取Q1~QK中按照1分组的其中两组中的每个点与R1~RL中每个点都“只有一个共同认识得朋友”,再利用前面1,2,3的结论,就能得出存在
某对点的“共同认识得朋友”超过1个的结论,矛盾!
首先用一个点来代表一个人,如果A认识B,就在AB间连一条线,这样整个关系生成一个无向图G.
那么由“任何两人都刚好只有一个共同认识得人”,能得出G中没有4边形,即不存在4点A,B,C,D使得,A与B,B与C,C与D,D与A之间均有线相连.
设连线最多的点为P,与它相连的点为Q1~QK,不与它相连的点为R1~RL(L>0).
1.根据P与Q1~QK中的每个点形成的点对都“只有一个共同认识得朋友”,而该朋友又不在R1~RL中的这个属性,能够得出Q1~QK这K个点必满足K
为偶数且这些点之间的连线情况必定是分为K/2个组,每组2个点它们之间有连线,除此之外Q1~QK间无其它连线;否则会有某对点的“共同认识得朋友”超过1个.
2.根据P与R1~RL中的每个点形成的点对都“只有一个共同认识得朋友”,而该朋友又不在R1~RL中的这个属性,能够得出每个R1~RL中的点只与
P1~PK中的一个点有连线;否则会有某对点的“共同认识得朋友”超过1个.
3.根据Q1~QK中每个点与R1~RL中每个点都“只有一个共同认识得朋友”,再利用前面1与2的结论可以得出Q1~QK中的每个点都与R1~RL中的点有
连线;否则会有某对点的“共同认识得朋友”超过1个.
4.再取Q1~QK中按照1分组的其中两组中的每个点与R1~RL中每个点都“只有一个共同认识得朋友”,再利用前面1,2,3的结论,就能得出存在
某对点的“共同认识得朋友”超过1个的结论,矛盾!
看了 一道图论题求证:在一群不少于...的网友还看了以下:
写出大于五分之一,小于四分之一的三个分数.分子相同的三个分数:今天晚上要! 2020-03-30 …
形状大小相同重量不同的两个球体从空中落下形状大小相同重量不同的两个球体从空中落下,考虑到阻力,两个 2020-04-13 …
甲袋中有大小相同的三个白球和四个红球,乙袋中有大小相同的四个白球个四个红球,甲袋中有大小相同的三个 2020-04-27 …
人对于天气的冷热的感觉,除了与风力等其他因素有关,如图14所示为在我国北方,小明分别在不同的两个早 2020-05-13 …
一个物体受到两个力的作用,如果两个力的三要素完全相同,那么这两个力是()A.一对相互作用力B.同一 2020-05-13 …
一个物体受到两个力的作用,如果两个力的三要素完全相同,那么这两个力是()A.一对相互作用力B.同一 2020-05-13 …
一个物体受到两个力的作用,如果两个力的三要素完全相同,那么这两个力是()A.一对相互作用力B.同一 2020-05-13 …
同一直线上,方向相同的两个力的合力大小等于,合力的方向,同一直线上,方向相反的两个力的合力大小等于 2020-05-13 …
下列说法错误的是()A.符号不同的两个数互为相反数B.任何一个数都有相反数C.若a+b=0,则a, 2020-05-14 …
关于Mathematica绘图的问题.用Mathematica的Show[]函数,应该可以把定义域 2020-05-16 …