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

人教版初中数学《第29章图论初步》竞赛专题复习(含答案) - 第29章 图论初步 29.1.1* 某大型晚会有2022个人参加，他们每个人至少认识其中的一个人．证明：必有一个人至少认识其中的二个人． 解析 2022这个数目较大，我们先考虑：某小型晚会有5人参加，他们每个人至少认识其中的一个人．证明：必有一个人至少认识其中的二个人． 用5个点v1、v2、v3、v4、v5表示5个人，假如两个人彼此认识〔本章中的“认识”都是指互相认识〕，就在表示这两个人的顶点之间连一条边．对顶点功来说，由于v1所表示的人至少认识其他4个人的一个，不妨设v1与v2认识，即v1和v2相邻，同样，设v3与v4相邻，如下图．对于顶点v5来说，无论它与v1、v2、v3、v4哪个相邻，都会出现一个顶点引出两条边的情况．于是问题得以解决． v1v5v2v3v4 用同样的方法可以证明，对2022个人来说，命题成立．其实，把2022换成任意一个大于l的奇数，命题也成立． 29.1.2* 在一间房子里有n〔n>3〕个人，至少有一个人没有和房子里每个人握手，房子里可能与每个人都握手的人数的最大值是多少？ 解析 用n个顶点表示n个人，假设某两个人握过手，就在他们相应的顶点之间连一条边，这样就得到了一个图G．因为不是任何两个人都握过手，所以G的边数最多是完全图Kn〔即n个点每两点之间恰连一条边〕的边数减1，去掉的那条边的两个端点v和v?所表示的两个人未握过手．所以房子里可能与每个人都握手的人数的最大值是n?2． 29.1.3*** 九名数学家在一次国际数学会议上相遇，发现他们中的任意三个人中，至少有两个人可以用同一种语言对话．假如每个数学家至多可说三种语言，证明至少有三个数学家可以用同一种语言对话． 解析 用9个点v1，v2，…，v9表示这九名数学家，假如某两个数学家能用某种语言对话，就在他们相应的顶点之间连一条边并涂以相应的颜色．我们要证明的是：存在三个顶点vi、vj、vk，使得边〔vi，vj〕和〔vi，vk〕是同色的．这样的，vi、vj、vk这三名数学家就能用同一种语言对话． 下面就顶点v1，分两种情形： 〔1〕v1与v2，…，v9均相邻，由于每个数学家至多能说三种语言，所以每一个顶点引出的边的颜色至多是三种．根据抽屉原理知，从v1发出的8条边中至少有2条是同色的，不妨设为〔v1，、〔v1，．于v2〕v3〕是v1、v2、v3所表示的三名数学家能用同一种语言对话．见图〔a〕． v2v3v1v9(a)v1v2(b)v3v4v5v6 v1514637v4v51129v8v22v3(c)v68v7 〔2〕v1与v2，v3，…，v9中的至少一点不相邻，不妨设功与功不相邻．由于任意三个数学家中，至少有两个人可以用同一种语言对话，所以，v3，v4，…，v9中的每一个不是和研相邻就是和功相邻，根据抽屉原理可知，其中至少有4个点与v1或v2相邻．不妨设v3、v4、v5、v6与v1相邻，如图〔b〕，再对v1引出的这4条边用抽屉原理可得，至少有2条边是同色的，设为〔v1，v3〕、〔v1，v4〕．于是v1、v3、v4所表示的三名数学家能用同一种语言对话． 评注 假设此题中的九改成八，那么命题不成立．反例如图〔c〕所示．图中每条边旁的数字表示不同的语种． 29.1.4** 证明任何一群人中，至少有两个人，它们的朋友数目一样． 解析 设任意给定的一群人有n个．用顶点表示这n个人．当且仅当顶点u、v表示的两个人是朋友时令u、v相邻，得到n个顶点的简单图G． 对G中任意x，由于它可以和其他n?1个顶点相邻，所以顶点x的度d〔x〕满足0≤d?x?≤n?1，即图G的顶点度只能是n个非负数0，1，…，n?1中的一个．假如图G的顶点的度都不一样，那么图G具有0度顶点u和n?1度顶点v．n?1度顶点和G中其他顶点都相邻，特别地和顶点u相邻．但0度顶点u和G中任何顶点都不相邻，矛盾．这就证明了G中必定有两个顶点，它们的度一样．也就是说，这群人必有两个人，他们的朋友一样多． 29.1.5*** 有一个参观团，其中任意四个成员中总有一名成员原先见过其他三名成员．证明：在任意四名成员中，总有一名成员原先见过所有成员． 解析 用图论语言表示即：图G的任意四点中至少有一个顶点和其他三个顶点相邻．证明图G任意四个顶点中至少一个顶点和G中其他所有顶点都相邻． 用反证法．假如命题不成立，那么G中有四个点x、y、z、w，它们和图G中的其他所有顶点不都相邻．于是存在四个顶点x?、y?、z?、w?〔不一定不同〕它们依次与x、y、z、w都不相邻．如图．所以x?不是y、z、w中的一个，且y?与x是两个不同的顶点． 假如y?与x?不同，那么x、y、x?、y?中没有一个顶点和其他三个顶点都相邻，和矛盾．所以y?和x?重合．同理可证，z?和x?重合．于是x?和y?、z、w都不相邻，和矛盾． 这就证明了图G中任意四个顶点中至少有一个顶点和G的其他所有顶点都相邻． x'xww'yy'zz' 29.1.6** 是否存在这样的多面体，它有奇数个面，每个面有奇数条棱？ 解析 不存在这样的多面体．事实上，假如这样的多面体存在，那么用顶点表示这个多面体的面，并且仅当vi、vj所代表的两个面有公共棱时，在图G相应的两顶点之间连一条边，依题意d?v?是奇数，于是奇数个奇数和也是奇数．而这一个图中的顶点的和为偶数矛盾． 评注 关于图G的顶点和边数之间的关系，有如下定理：图G中边数的两倍等于顶点度数之和．即假设G中n个顶点为v1，v2，…，vn，边数为e，那么 d?v1-d?v2--d?vn-2e． 29.1.7* n名选手进展对抗赛，每名选手至多赛一场，每场两名选手参加，已赛完n?1场．证明：至少有一名选手赛过三次． 解析 把选手看成顶点．当且仅当vi、vj所代表的两名选手比赛过时，令vi、vj相邻，得到含n个顶点的简单图．由于总共赛过n?1场，所以，图G的边数是n?1．于是 d?v1-d?v2--d?vn-2?n?1?． 假如图G中所有顶点的度都不超过2，那么由上式得到 2?n?1-d?v1-d?v2--d?vn?≤2n， 这不可能．因此图G中至少有一个顶点x，它的度至少是3．于是，顶点x所表示的选手至少赛过三次． 29.1.8** 一航空线路共连结50个城市，现要求从一个城市到另一城市至多需换乘两次飞机，问航空线路最少要多少条〔任两城市之间的航空线路数为0或1〕？ 解析 不妨将50个城市看成50个点，它们之间连的线构成一连通图．图论告诉我们，假如每一点的度〔即出发的线条数〕至少为2，那么由于边数为点度之和的一半，其数值不小于50；假设有一个点的度为1〔显然连通图不存在度为0的孤立点〕，那么可通过删去该点证明。

边数必须至少为49，否那么图就不连通〔只需对剩下的图不断进展上述处理过程〕．于是找到一个城市为中转站，其他城市与之相连，构成一“星形”即可．故线路最少要49条． A2A3A50A5…A1A49A4 29.1.9 九个人A1，A2，…，A9中，A1和两个人握过手，A2、A3各和四个人握过手，A4、A5、A6、A7各和五个人握过手，A8、A9各和六个人握过手．证明：这九个人中一定可以找出三个人，他们互相握过手． 解析 用9个点v1，v2，…，v9表示A1，A2，…，A9这九个人，假设两个人握过手，就在他们相应的顶点之间连一条边，这样便得到了一个图G．因为d?v9-6，所以存在一个不同于v1，v2，v3的点vi与vj相邻．显然d?vi?≥5．考虑与功相邻的另外5个点，假设其中任意一点都不与vi相邻，那么 d?vi?≤9?1?5?3， 这不可能．故必有一点vj与vi相邻，从而v9、vi、vj两两相邻．即它们表示的三个人互相握过手． 29.1.10* 参加某次学术讨论会的共有263个人，每个人至少和三位与会者讨论过问题．证明：至少有一个人和四位或四位以上的学者讨论过问题． 解析 用点v1，v2，…，两个人讨论过问题，就在相应的点之间连一条边，得图G．在v263表示263个人，图G中，任一顶点的次数≥3．假设没有一个顶点的次数≥4，那么G中的所有顶点的次数都是3．于是d?v1-d?v2--d?v263-3?263?789，是一个奇数，而这应是一个偶数，所以致少有一个顶点的次数≥4．于是命题得证． 29.1.11*** 某地区网球俱乐部的20名成员举行14场单打比赛，每人至少上场一次．求证：必有六场比赛，其12个参赛者各不一样． 解析 用20个点表示这20名俱乐部成员，14条边表示14场比赛，得图G．根据题意， d?vi?≥1，i?1，2，…，20． 于是 d?v1-d?v2--d?v20-2?14?28． 今在每个顶点vi处抹去d?vi-1条边〔一条边可以同时在其两端点处被抹去〕，抹去的边数不超过 ?d?v?1-d?v-1--?d?v-1-28?20?8． 1220故余下的图G?中至少还有6条边，且G?中每个顶点的次数都≤1，所以这6场比赛的参赛者各不一样． 29.1.12*** 34个城市参加双人舞比赛〔每个城市一男一女〕，赛前，某些选手互相握手．同一城市的两人不握手．后来，来自A城的男选手问其他参赛选手他们与人握手的次数，得到的答案都不一样．问A城女选手和多少人握过手？ 解析 用顶点表示参赛选手．对于u、v，当且仅当u、v所表示的两名队员握过手时，令它们相邻，得到一个68个顶点的简单图G．由于同一个的两名队员之间不握手，所以对任意u，d?u?≤66．A城男选手用x表示．图G中除x外尚有67个点，它们的度各不一样，因此必有一个点度为0?d?v-0?，即v和G中其他顶点不相邻．所以假设顶点w表示的选手和顶点v所表示的选手来自一个城市，那么d?w-66． 从图G中去掉v和w，得到含66个顶点的图G1．那么x是G1中的顶点，并且除x外，其他顶点的度也都不一样．因此和前述证明一样，G1含有度分别为0和64的顶点p和q，它们在原来图G中的度分别为1和65．如此继续，可证0≤j≤33，图G中含有顶点xj、yj，它们的度分别为j和66?j，而且所代表的选手来自同一城市，其中x33?x，所以d?x33-33．因此A城女选手握手次数为33． 评注 此题证明中，将G的顶点编号，按度的非降次序〔d1≤d2≤…≤dn〕排列，得到〔d1，d2，…，第 页 共 页。