人教版初中数学《第29章图论初步》竞赛专题复习含答案

《人教版初中数学《第29章图论初步》竞赛专题复习含答案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第29章图论初步29.1.1*某大型晚会有2009个人参加，已知他们每个人至少认识其中的一个人.证明：必有一个人至少认识其中的二个人.解析2009这个数目较大，我们先考虑：某小型晚会有5人参加，己知他们每个人至少认识其中的一个人.证明：必有一个人至少认识其屮的二个人.用5个点岭、岭、比、比、冬表示5个人，如果两个人彼此认识（本章中的“认识”都是指相互认识）,就在表示这两个人的顶点之间连一条边.对顶点功來说，由于片所表示的人至少认识其他4个人的一个，不妨设片与岭认识，即片和冬相邻，同样，设叫与旳相邻，如图所示.对于顶点也来说，无论它与儿、冬、叫、

2、儿哪个相邻，都会出现一个顶点引出两条边的情况.于是问题得以解决.用同样的方法可以证明，对2009个人来说，命题成立.其实，把2009换成任意一个大于1的奇数，命题也成立.29.1.2*在一间房子里有〃（n>3）个人，至少有一个人没有和房子里每个人握手，房子里可能与每个人都握手的人数的最大值是多少？解析用八个顶点表示八个人，若某两个人握过手，就在他们相应的顶点Z间连一条边，这样就得到了一个图G.因为不是任何两个人都握过手，所以G的边数最多是完全图（即舁个点每两点之间恰连一条边）的边数减1,去掉的那条边的两个端点y和M所表示的两个人未握过手.所以房

3、子里可能与每个人都握手的人数的最大值是«-2.29.1.3***九名数学家在一次国际数学会议上相遇，发现他们屮的任意三个人屮，至少有两个人可以用同一种语言对话.如果每个数学家至多可说三种语言，证明至少有三个数学家可以用同一种语言对话.解析用9个点岭，v2,・・•，$表示这九名数学家，如果某两个数学家能用某种语言对话，就在他们相应的顶点之间连一条边并涂以相应的颜色.我们要证明的是：存在三个顶点片、V-.V,,使得边（片，Vj）和（岭，vk）是同色的.这样的，岭、号、叫这三名数学家就能用同一种语言对话.下面就顶点岭，分两种情形：（1）片与卩2,…，

4、仏均相邻，由于每个数学家至多能说三种语言，所以每一个顶点引出的边的颜色至多是三种.根据抽屉原理知，从岭发出的8条边中至少有2条是同色的，不妨设为（儿，叫）、（岭，v3）.于是儿、V2.冬所表示的三名数学家能用同一种语言对话.见图（a）・（2）片与卩2，卩3，…'(c)卩9中的至少一点不相邻,不妨设功与功不相邻.由于任意三个数学家中，至少有两个人可以用同一种语言对话，所以，％，v4,…，％中的每一个不是和研相邻就是和功相邻，根据抽屉原理可知，其中至少有4个点与片或冬相邻.不妨设岭、比、叫、比与岭相邻，如图（b）,再对岭引出的这4条边用抽屉原理可得

5、，至少有2条边是同色的，设为（片，叫）、（片，岭）.于是岭、叫、岭所表示的三名数学家能用同一种语言对话.评注若本题中的九改成八，则命题不成立.反例如图（c）所示.图中每条边旁的数字表示不同的语种.29.1.4**证明任何一群人中，至少有两个人，它们的朋友数目相同.解析设任意给定的一群人有〃个.用顶点表示这〃个人.当且仅当顶点“、u表示的两个人是朋友时令弘、u相邻，得到〃个顶点的简单图G.对G中任意x,由于它可以和其他八-1个顶点相邻，所以顶点兀的度d（x）满足OWd（x）Wn-1,即图G的顶点度只能是农个非负数0,1,…，n—l屮的一个.如果图

6、G的顶点的度都不相同，则图G具有0度顶点"和—1度顶点v.n-度顶点和G中其他顶点都相邻，特别地和顶点"相邻.但0度顶点"和G中任何顶点都不相邻，矛盾.这就证明了G中必定有两个顶点，它们的度相同.也就是说,这群人必有两个人，他们的朋友一样多.29.1.5***有一个参观团，其中任意四个成员中总有一名成员原先见过其他三名成员.证明：在任意四名成员屮，总有一名成员原先见过所有成员.解析用图论语言表示即：图G的任意四点中至少有一个顶点和其他三个顶点相邻.证明图G任意四个顶点中至少一个顶点和G中其他所有顶点都相邻.用反证法.如果命题不成立，则G中有四

7、个点X、〉，、z、⑷，它们和图G中的其他所有顶点不都相邻.于是存在四个顶点“、『、z1/（不一定不同）它们依次与兀、八Z、⑷都不相邻.如图.所以”不是y、Z、W中的一个，II『与兀是两个不同的顶点.如果y与兀'不同，则兀、），、y中没有一个顶点和其他三个顶点都相邻，和已知矛盾.所以y和丫重合.同理可证，z‘和”重合.于是“和y、z、w都不相邻，和已知矛盾.这就证明了图g中任意四个顶点中至少有一个顶点和g的其他所有顶点都相邻.29.1.6**是否存在这样的多面体，它有奇数个面，每个面有奇数条棱？解析不存在这样的多面体.事实上，如果这样的多面体存

8、在，那么用顶点表示这个多面体的面，并且仅当岭、乌所代表的两个面有公共棱时，在图G相应的两顶点之间连一条边，依题意d（u）是奇数，于是奇数个奇数和也是奇