一道图论题求证:在一群不少于三人的人中,若任何两人都刚好只有一个共同认识得人,证明这群人中总有一人是所有人都认识的.
来源:学生作业帮 编辑:作业帮 分类:数学作业 时间:2024/10/03 02:55:01
一道图论题
求证:在一群不少于三人的人中,若任何两人都刚好只有一个共同认识得人,证明这群人中总有一人是所有人都认识的.
求证:在一群不少于三人的人中,若任何两人都刚好只有一个共同认识得人,证明这群人中总有一人是所有人都认识的.
我用反证法来证明.事实上要满足“任何两人都刚好只有一个共同认识得人”这个条件的这群人必须是奇数.
首先用一个点来代表一个人,如果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个的结论,矛盾!
有11个人,其中任何3人中有2人认识,证明在这11人中至少有一人认识其余10人中的5个人
一道图论题:一个旅行团中任意4位中至少有一个旅客认识另外3人,证明任意4人中有1人他早就认识旅行团中其余的每个人
有一个团体会议,有n人参加,在其中任意m人中(n>m),至少有a个人认识其它b个人,问该团体中认识其它所有人的成员至少有
两道六年级奥数问题第一道某班有60人,任意两人要么互相不认识,要么互相认识.证明,这60人中,必有两人认识的人数相同.第
汉语是:你认识的人中谁最有天赋
30人中恰好有两人生日相同的概率,我的认识错在哪里?
某次会议有25人参加,每人至少认识1个人.在这25人中至少有两人认识的人数相同你知道为什么吗?
求48人中只有三人生日相同的概率?48人中只有两组人生日相同的概率?
一群人中最安静的人往往最有实力
求一道纠结的数学题在一家三口人中,每两个人的平均年龄加上余下一人的年龄分别得43,58,55,那么这三个人中最大年龄与最
英汉互译 :我的朋友约翰是我认识的人中最滑稽的一个 是译...
四个人中,有且只有2人都出生于周一的概率为