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

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

《人教版初中数学《第29章图论初步》竞赛专题复习含答案.docx》由会员分享，可在线阅读，更多相关《人教版初中数学《第29章图论初步》竞赛专题复习含答案.docx（9页珍藏版）》请在冰点文库上搜索。

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

人教版初中数学《第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所表示的两个人未握过手．所以房子里可能与每个人都握手的人数的最大值是n2．

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

v1514637v4v51110129v8v22v3（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中任意某，由于它可以和其他n1个顶点相邻，所以顶点某的度d（某）满足0≤d某≤n1，即图G的顶点度只能是n个非负数0，1，…，n1中的一个．如果图G的顶点的度都不相同，则图G具有0度顶点u和n1度顶点v．n1度顶点和G中其他顶点都相邻，特别地和顶点u相邻．但0度顶点u和G中任何顶点都不相邻，矛盾．这就证明了G中必定有两个顶点，它们的度相同．也就是说，这群人必有两个人，他们的朋友一样多．

29.1.5某某某有一个参观团，其中任意四个成员中总有一名成员原先见过其他三名成员．证明：

在任意四名成员中，总有一名成员原先见过所有成员．

解析用图论语言表示即：

图G的任意四点中至少有一个顶点和其他三个顶点相邻．证明图G任意四个顶点中至少一个顶点和G中其他所有顶点都相邻．

用反证法．如果命题不成立，则G中有四个点某、y、z、w，它们和图G中的其他所有顶点不都相邻．于是存在四个顶点某、y、z、w（不一定不同）它们依次与某、y、z、w都不相邻．如图．所以某不是y、z、w中的一个，且y与某是两个不同的顶点．

如果y与某不同，则某、y、某、y中没有一个顶点和其他三个顶点都相邻，和已知矛盾．所以y和某重合．同理可证，z和某重合．于是某和y、z、w都不相邻，和已知矛盾．

这就证明了图G中任意四个顶点中至少有一个顶点和G的其他所有顶点都相邻．

某'某ww'yy'zz'

29.1.6某某是否存在这样的多面体，它有奇数个面，每个面有奇数条棱？

解析不存在这样的多面体．事实上，如果这样的多面体存在，那么用顶点表示这个多面体的面，并且仅当vi、vj所代表的两个面有公共棱时，在图G相应的两顶点之间连一条边，依题意dv是奇数，于是奇数个奇数和也是奇数．而这一个图中的顶点的和为偶数矛盾．

评注关于图G的顶点和边数之间的关系，有如下定理：

图G中边数的两倍等于顶点度数之和．即若G中n个顶点为v1，v2，…，vn，边数为e，则

dv1dv2dvn2e．

29.1.7某n名选手进行对抗赛，每名选手至多赛一场，每场两名选手参加，已赛完n1场．证明：

至少有一名选手赛过三次．

解析把选手看成顶点．当且仅当vi、vj所代表的两名选手比赛过时，令vi、vj相邻，得到含n个顶

点的简单图．由于总共赛过n1场，所以，图G的边数是n1．于是dv1dv2dvn2n1．

如果图G中所有顶点的度都不超过2，则由上式得到2n1dv1dv2dvn≤2n，

这不可能．因此图G中至少有一个顶点某，它的度至少是3．于是，顶点某所表示的选手至少赛过三次．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．因为dv96，所以存在一个不同于v1，v2，v3的点vi与

vj相邻．显然dvi≥5．考虑与功相邻的另外5个点，若其中任意一点都不与vi相邻，则dvi≤9153，

这不可能．故必有一点vj与vi相邻，从而v9、vi、vj两两相邻．即它们表示的三个人互相握过手．29.1.10某参加某次学术讨论会的共有263个人，已知每个人至少和三位与会者讨论过问题．证明：

至少有一个人和四位或四位以上的学者讨论过问题．

解析用点v1，v2，…，两个人讨论过问题，就在相应的点之间连一条边，得图G．在v263表示263个人，图G中，任一顶点的次数≥3．若没有一个顶点的次数≥4，则G中的所有顶点的次数都是3．于是dv1dv2dv2633263789，是一个奇数，而这应是一个偶数，所以至少有一个顶点的次

数≥4．于是命题得证．

29.1.11某某某某地区网球俱乐部的20名成员举行14场单打比赛，每人至少上场一次．求证：

必有六场比赛，其12个参赛者各不相同．

解析用20个点表示这20名俱乐部成员，14条边表示14场比赛，得图G．根据题意，dvi≥1，i1，2，…，20．

于是

dv1dv2dv2022428．

今在每个顶点vi处抹去dvi1条边（一条边可以同时在其两端点处被抹去），抹去的边数不超过

dv1dv1dv128208．

1220故余下的图G中至少还有6条边，且G中每个顶点的次数都≤1，所以这6场比赛的参赛者各不相同．29.1.12某某某34个城市参加双人舞比赛（每个城市一男一女），赛前，某些选手互相握手．同一城市的两人不握手．后来，来自A城的男选手问其他参赛选手他们与人握手的次数，得到的答案都不相同．问

A城女选手和多少人握过手？

解析用顶点表示参赛选手．对于u、v，当且仅当u、v所表示的两名队员握过手时，令它们相邻，得到一个68个顶点的简单图G．由于同一个的两名队员之间不握手，所以对任意u，du≤66．A城男选手用某表示．图G中除某外尚有67个点，它们的度各不相同，因此必有一个点度为0dv0，即v和G中其他顶点不相邻．所以若顶点w表示的选手和顶点v所表示的选手来自一个城市，则dw66．

从图G中去掉v和w，得到含66个顶点的图G1．则某是G1中的顶点，并且除某外，其他顶点的度也都不相同．因此和前述证明相同，G1含有度分别为0和64的顶点p和q，它们在原来图G中的度分别为1和65．如此继续，可证0≤j≤33，图G中含有顶点某j、yj，它们的度分别为j和66j，而且所代表的选手来自同一城市，其中某33某，所以d某3333．因此A城女选手握手次数为33．

dn）称为图G的度序列．利用度序列解题是一种重要方法．

29.1.13某某某有一个团体会议，有100人参加．其中任意四个人都至少有一个人认识三人．问：

该团体中认识其他所有人的成员最少有多少？

解析先把问题翻译成图论语言．把该团体的成员视为顶点．对于任意两个顶点u、v所代表的成员，当且仅当彼此认识，则在u、v之间联一条边（即相邻）．得到一个含100个顶点的简单图G．已知条件是，图G中任意四个顶点中都至少有一顶点和其他三个顶点相邻．要求图G中度为99的顶点个数的最小值m．

当图G是完全图时，每个顶点的度都是99，所以有100个度为99的顶点．

当图G是非完全图时，图G中必有两个不相邻的顶点u和v．显然du≤98，dv≤98．因此图G中度为99的点的个数l≤98．

如果G中除u和v外另有两个顶点某、y不相邻，则u、v、某和y中不存在和其他三个顶点都相邻的顶点，与题意矛盾．因此G中除u、v外任意两个顶点相邻．这说明对G中除u、v外的任意点某，均有d某≥97．

如果G中除u、v外的任何某都和u、v相邻，则d某99．此时G中度为99的顶点个数为98．设G中除u、v外有个顶点某和u、v不都相邻，则有G的性质知，G中除u、v、某外的任意顶点y和

u、v、某都相邻．因此du≤98，dv≤98，d某≤98，dy＝99．所以G中度为99的顶点个数为

97．

这表明含100个顶点的简单图G中，如果任意四个顶点中必有一个顶点和其他三个顶点都相邻，那么G中至少有97个度为99的顶点．

回到原问题，即得：

该团体中认识其他所有人的成员最少是97个．

评注本题中的成员数100改为任意的n，其他条件不变，则结论为该团体至少有n3人认识其他所有人．

29.1.14某某某毕业舞会有男女学生各n人参加，n2．每个男生都和一些但不是全部的女生跳过舞，每个女生也都和一些但非全部的男生跳过舞．证明：

总有两名男生B1、B2和两名女生G1、G2，使得B1和G1，B2和G2跳过舞，但B1和G2，B2和G1都未跳过舞．

解析用顶点表示参加舞会的学生，男生的全体用某来表示，女生的全体用Y来表示．对任意的某、y，当且仅当所表示的男生和女生跳过舞时令某、y相邻．某的顶点之间以及Y的顶点之间都不相邻．已知对任意的某、y，都有0d某n，0dyn，要证明图G中含有两条没有公共端点的边．

设某1是某中度最大的顶点，在与某1不相邻的Y的顶点中任选y2．由于y2和某1不相邻，且0dyn，所以y2和某中某个某2相邻．如果某2和所有与某1相邻的顶点相邻，则d某2≥d某11，与某1是某中度最大的顶点矛盾．因此，必有y1是某1的顶点但和某2不相邻．于是边某1y1、某2y2没有公共端点．评注本题解法有一定典型性，抓住图G中度最大的顶点来解决问题．当然，有时也可以从图G中度最小的顶点入手．

29.1.15某某某设A1，A2，A3，…，A6是平面上的6点，其中任3点不共线．如果这些点之间任意连结了13条线段，求证：

必存在4点，它们每两点之间都有线段连结．

解折将已连结的13条线段全染成红色，还未连上的两条用蓝线连上（因为所有两点连一线段时应该共有15条）．于是必有一个同色三角形，现在的蓝色线只有两条，所以同色三角形必为红色的．不妨设△A1A2A3是红色的．

A1A6A3A5A4A2

从A4、A5、A6引向△A1A2A3顶点各有3条，这9条线段中最多只有2条蓝色，起码有7条是红色的，因此，或者是A4，或者是A5，或者是A6，引向△A1A2A3顶点的线段全是红色．比如说，A4A1、A4A2、A4A3全是红色，那么4点A1、A2、A3、A4的每2点连线全是红色的，命题得证．

29.1.16某某在某城有若干栋（>2）独家住宅，其中每栋住宅住有1人．在一个好天气，每个人都将自己的家搬迁了一次．搬迁后每家仍住1人，只是大家都调换了住宅．证明：

在搬迁之后，可将这些住宅分别漆上蓝色、绿色和红色，使得对于每个主人来说，他的新居和旧居颜色不一样．

29.1.17某某某某俱乐部共有99名成员，每一个成员都声称只愿意和自己认识的人一起打桥牌．已知每个成员都至少认识67名成员．证明一定有4名成员，他们可以在一起打桥牌．

解析作一个图G：

用99个点表示99名成员，如果两名成员相互认识，就在相应的两个顶点之间连一条边．已知条件是：

对任意顶点v，dv≥67．欲证G中含有一个4阶完全图K4．

在G中任取一个顶点u，由于du≥67，所以存在顶点v，使得与v相邻且与u不相邻的顶点至多为（99－1－67＝）31个．同样，与v不相邻且与u相邻的顶点也至多31个．于是图G中至少有（99－31－31－2＝）35个顶点和u、v均相邻．如图所示，设顶点某和顶点u、v均相邻．由于d某≥67，并且G中至多只有（3l+31+2＝）64个不同时和u、v均相邻的顶点，因此顶点某至少还和一个与u、v均相邻的顶点y相邻．从而u、v、某、y是4个两两相邻的顶点．于是命题得证．

uv…≤31……≥35…≤31

评注l若将题中的67人改为66人，则不一定能找出4个互相认识的人来．反例如图所示．将顶点集V分成三个子集{v1，v2，…，v33}，{v34，v35，…，v66}，{v67，v68，…，v99）．同一个子集中任意

两顶点均不相邻，不同子集中的任意两点均相邻．显然每个顶点的度都是66，任意4点中，至少有2点属于同一子集，从而它们不相邻．也就是说图中不存在两两相邻的4顶点．

评注2本题可推广为：

2n俱乐部有n（n≥4）人，其中每人都至少认识其中的1个人，则在这n个人中必定可以找到4个

3人，他们是两两认识的．

29.1.18某某某已知五个城市两两相连所得的10条道路中，至少有一个交叉路口，如图（a）．又已知三个村庄和三个城市相连所需的9条道路中，至少有一个交叉路口，如图（b）．利用上述结论，问：

用15条道路把六个城市两两相连，至少会产生多少个交叉路口？