初中数学竞赛专题复习 第四篇 组合 第29章 图论初步试题 新人教版

我带领班子成员及全体职工，积极参加县委、政府和农牧局组织的政治理论学习，同时认真学习业务知识，全面提高了自身素质，增强职工工作积极性，杜绝了纪律松散第29章 图论初步29.1.1* 某大型晚会有2009个人参加，已知他们每个人至少认识其中的一个人证明：必有一个人至少认识其中的二个人解析 2009这个数目较大，我们先考虑：某小型晚会有5人参加，已知他们每个人至少认识其中的一个人证明：必有一个人至少认识其中的二个人用5个点、表示5个人，如果两个人彼此认识（本章中的“认识”都是指相互认识），就在表示这两个人的顶点之间连一条边对顶点功来说，由于所表示的人至少认识其他4个人的一个，不妨设与认识，即和相邻，同样，设与相邻，如图所示对于顶点来说，无论它与、哪个相邻，都会出现一个顶点引出两条边的情况于是问题得以解决用同样的方法可以证明，对2009个人来说，命题成立其实，把2009换成任意一个大于l的奇数，命题也成立29.1.2* 在一间房子里有（3）个人，至少有一个人没有和房子里每个人握手，房子里可能与每个人都握手的人数的最大值是多少？解析 用个顶点表示个人，若某两个人握过手，就在他们相应的顶点之间连一条边，这样就得到了一个图因为不是任何两个人都握过手，所以的边数最多是完全图（即个点每两点之间恰连一条边）的边数减1，去掉的那条边的两个端点和所表示的两个人未握过手所以房子里可能与每个人都握手的人数的最大值是29.1.3* 九名数学家在一次国际数学会议上相遇，发现他们中的任意三个人中，至少有两个人可以用同一种语言对话如果每个数学家至多可说三种语言，证明至少有三个数学家可以用同一种语言对话解析 用9个点，表示这九名数学家，如果某两个数学家能用某种语言对话，就在他们相应的顶点之间连一条边并涂以相应的颜色我们要证明的是：存在三个顶点、，使得边（，）和（，）是同色的这样的，、这三名数学家就能用同一种语言对话下面就顶点，分两种情形：（1）与，均相邻，由于每个数学家至多能说三种语言，所以每一个顶点引出的边的颜色至多是三种根据抽屉原理知，从发出的8条边中至少有2条是同色的，不妨设为（，）、（，）于是、所表示的三名数学家能用同一种语言对话见图（）（2）与，中的至少一点不相邻，不妨设功与功不相邻由于任意三个数学家中，至少有两个人可以用同一种语言对话，所以，中的每一个不是和研相邻就是和功相邻，根据抽屉原理可知，其中至少有4个点与或相邻不妨设、与相邻，如图（），再对引出的这4条边用抽屉原理可得，至少有2条边是同色的，设为（，）、（，）于是、所表示的三名数学家能用同一种语言对话评注 若本题中的九改成八，则命题不成立反例如图（）所示图中每条边旁的数字表示不同的语种29.1.4* 证明任何一群人中，至少有两个人，它们的朋友数目相同解析 设任意给定的一群人有个用顶点表示这个人当且仅当顶点、表示的两个人是朋友时令、相邻，得到个顶点的简单图对中任意，由于它可以和其他个顶点相邻，所以顶点的度（）满足，即图的顶点度只能是个非负数0，1，中的一个如果图的顶点的度都不相同，则图具有0度顶点和度顶点度顶点和中其他顶点都相邻，特别地和顶点相邻但0度顶点和中任何顶点都不相邻，矛盾这就证明了中必定有两个顶点，它们的度相同也就是说，这群人必有两个人，他们的朋友一样多29.1.5* 有一个参观团，其中任意四个成员中总有一名成员原先见过其他三名成员证明：在任意四名成员中，总有一名成员原先见过所有成员解析 用图论语言表示即：图的任意四点中至少有一个顶点和其他三个顶点相邻证明图任意四个顶点中至少一个顶点和中其他所有顶点都相邻用反证法如果命题不成立，则中有四个点、，它们和图中的其他所有顶点不都相邻于是存在四个顶点、（不一定不同）它们依次与、都不相邻如图所以不是、中的一个，且与是两个不同的顶点如果与不同，则、中没有一个顶点和其他三个顶点都相邻，和已知矛盾所以和重合同理可证，和重合于是和、都不相邻，和已知矛盾这就证明了图中任意四个顶点中至少有一个顶点和的其他所有顶点都相邻29.1.6* 是否存在这样的多面体，它有奇数个面，每个面有奇数条棱？解析 不存在这样的多面体事实上，如果这样的多面体存在，那么用顶点表示这个多面体的面，并且仅当、所代表的两个面有公共棱时，在图相应的两顶点之间连一条边，依题意是奇数，于是奇数个奇数和也是奇数而这一个图中的顶点的和为偶数矛盾评注 关于图的顶点和边数之间的关系，有如下定理：图中边数的两倍等于顶点度数之和即若中个顶点为，边数为，则29.1.7* 名选手进行对抗赛，每名选手至多赛一场，每场两名选手参加，已赛完场证明：至少有一名选手赛过三次解析 把选手看成顶点当且仅当、所代表的两名选手比赛过时，令、相邻，得到含个顶点的简单图由于总共赛过场，所以，图的边数是于是如果图中所有顶点的度都不超过2，则由上式得到，这不可能因此图中至少有一个顶点，它的度至少是3于是，顶点所表示的选手至少赛过三次29.1.8* 一航空线路共连结50个城市，现要求从一个城市到另一城市至多需换乘两次飞机，问航空线路最少要多少条（任两城市之间的航空线路数为0或1）？解析 不妨将50个城市看成50个点，它们之间连的线构成一连通图图论告诉我们，如果每一点的度（即出发的线条数）至少为2，则由于边数为点度之和的一半，其数值不小于50；若有一个点的度为1（显然连通图不存在度为0的孤立点），则可通过删去该点证明。边数必须至少为49，否则图就不连通（只需对剩下的图不断进行上述处理过程）于是找到一个城市为中转站，其他城市与之相连，构成一“星形”即可故线路最少要49条29.1.9 已知九个人，中，和两个人握过手，、各和四个人握过手，、各和五个人握过手，、各和六个人握过手证明：这九个人中一定可以找出三个人，他们相互握过手解析 用9个点，表示，这九个人，若两个人握过手，就在他们相应的顶点之间连一条边，这样便得到了一个图因为，所以存在一个不同于，的点与相邻显然5考虑与功相邻的另外5个点，若其中任意一点都不与相邻，则，这不可能故必有一点与相邻，从而、两两相邻即它们表示的三个人互相握过手29.1.10* 参加某次学术讨论会的共有263个人，已知每个人至少和三位与会者讨论过问题证明：至少有一个人和四位或四位以上的学者讨论过问题解析 用点，表示263个人，两个人讨论过问题，就在相应的点之间连一条边，得图在图中，任一顶点的次数3若没有一个顶点的次数4，则中的所有顶点的次数都是3于是，是一个奇数，而这应是一个偶数，所以至少有一个顶点的次数4于是命题得证29.1.11* 某地区网球俱乐部的20名成员举行14场单打比赛，每人至少上场一次求证：必有六场比赛，其12个参赛者各不相同解析 用20个点表示这20名俱乐部成员，14条边表示14场比赛，得图根据题意，2，20于是今在每个顶点处抹去条边（一条边可以同时在其两端点处被抹去），抹去的边数不超过故余下的图中至少还有6条边，且中每个顶点的次数都1，所以这6场比赛的参赛者各不相同29.1.12* 34个城市参加双人舞比赛（每个城市一男一女），赛前，某些选手互相握手同一城市的两人不握手后来，来自城的男选手问其他参赛选手他们与人握手的次数，得到的答案都不相同问城女选手和多少人握过手？解析 用顶点表示参赛选手对于、，当且仅当、所表示的两名队员握过手时，令它们相邻，得到一个68个顶点的简单图由于同一个的两名队员之间不握手，所以对任意，城男选手用表示图中除外尚有67个点，它们的度各不相同，因此必有一个点度为0，即和中其他顶点不相邻所以若顶点表示的选手和顶点所表示的选手来自一个城市，则从图中去掉和，得到含66个顶点的图则是中的顶点，并且除外，其他顶点的度也都不相同因此和前述证明相同，含有度分别为0和64的顶点和，它们在原来图中的度分别为1和65如此继续，可证033，图中含有顶点、，它们的度分别为和，而且所代表的选手来自同一城市，其中，所以因此城女选手握手次数为33评注 本题证明中，将的顶点编号，按度的非降次序（）排列，得到（，）称为图的度序列利用度序列解题是一种重要方法29.1.13* 有一个团体会议，有100人参加其中任意四个人都至少有一个人认识三人问：该团体中认识其他所有人的成员最少有多少？解析 先把问题翻译成图论语言把该团体的成员视为顶点对于任意两个顶点、所代表的成员，当且仅当彼此认识，则在、之间联一条边（即相邻）得到一个含100个顶点的简单图已知条件是，图中任意四个顶点中都至少有一顶点和其他三个顶点相邻要求图中度为99的顶点个数的最小值当图是完全图时，每个顶点的度都是99，所以有100个度为99的顶点当图是非完全图时，图中必有两个不相邻的顶点和显然，因此图中度为99的点的个数98如果中除和外另有两个顶点、不相邻，则、和中不存在和其他三个顶点都相邻的顶点，与题意矛盾因此中除、外任意两个顶点相邻这说明对中除、外的任意点，均有97如果中除、外的任何都和、相邻，则此时中度为99的顶点个数为98设中除、外有个顶点和、不都相邻，则有的性质知，中除、外的任意顶点和、都相邻因此98，98，98，99所以中度为99的顶点个数为97这表明含100个顶点的简单图中，如果任意四个顶点中必有一个顶点和其他三个顶点都相邻，那么中至少有97个度为99的顶点回到原问题，即得：该团体中认识其他所有人的成员最少是97个评注 本题中的成员数100改为任意的，其他条件不变，则结论为该团体至少有人认识其他所有人29.1.14* 毕业舞会有男女学生各人参加，每个男生都和一些但不是全部的女生跳过舞，每个女生也都和一些但非全部的男生跳过舞证明：总有两名男生、和两名女生、，使得和，和跳过舞，但和，和都未跳过舞解析 用顶点表示参加舞会的学生，男生的全体用来表示，女生的全体用来表示对任意的、，当且仅当所表示的男生和女生跳过舞时令、相邻的顶点之间以及的顶点之间都不相邻已知对任意的、，都有，要证明图中含有两条没有公共端点的边设是中度最大的顶点，在与不相邻的的顶点中任选由于和不相邻，且，所以和中某个相邻如果和所有与相邻的顶点相邻，则，与是中度最大的顶点矛盾因此，必有是的顶点但和不相邻于是边、没有公共端点评注 本题解法有一定典型性，抓住图中度最大的顶点来解决问题当然，有时也可以从图中度最小的顶点入手29.1.15* 设，是平面上的6点，其中任3点不共线如果这些点之间任意连结了13条线段，求证：必存在4点，它们每两点之间都有线段连结解折 将已连结的13条线段全染成红色，还未连上的两条用蓝线连上（因为所有两点连一线段时应该共有15条）于是必有一个同色三角形，现在的蓝色线只有两条，所以同色三角形必为红色的不妨设是红色的从、引向顶点各有3条，这9条线段中最多只有2条蓝色，起码有7条是红色的，因此，或者是，或者是，或者是，引向顶点的线段全是红色比如说，、全是红色，那么4点、的每2点连线全是红色的，命题得证29.1.16* 在某城有若干栋（2）独家住宅，其中每栋住宅住有1人在一个好天气，每个人都将自己的家搬迁了一次搬迁后每家仍住1人，只是大家都调换了住宅证明：在搬迁之后，可将这些住宅分别漆上蓝色、绿色和红色，使得对于每个主人来说，他的新居和旧居颜色不一样解析 将住宅一一编号，使得第一座住宅搬出来的人住进第二座住宅，第二座住宅出来的人住进第三座住宅于是一定存在一个自，使得第矗座住宅搬出的人住进第1座住宅这是个人形成一个“圈”如果志为偶数，显然只需要2种颜色，如果是奇数，3种颜色足够了然后再考虑其他人，最后形成一个个互相独立的“圈”（当然也可能只有一个），每个圈独自处理即可29.1.17* 某俱乐部共有99名成员，每一个成员都声称只愿意和自己认识的人一起打桥牌已知每个成员都至少认识67名成员证明一定有4名成员，他们可以在一起打桥牌解析 作一个图：用99个点表示99名成员，如果两名成员相互认识，就在相应的两个顶点之间连一条边已知条件是：对任意顶点，67欲证中含有一个4阶完全图在中任取一个顶点，由于67，所以存在顶点，使得与相邻且与不相邻的顶点至多为（99167）31个同样，与不相邻且与相邻的顶点也至多31个于是图中至少有（9931312）35个顶点和、均相邻如图所示，设顶点和顶点、均相邻由于67，并且中至多只有（3l+31+2）64个不同时和、均相邻的顶点，因此顶点至少还和一个与、均相邻的顶点相邻从而、是4个两两相邻的顶点于是命题得证评注l 若将题中的67人改为66人，则不一定能找出4个互相认识的人来反例如图所示将顶点集分成三个子集，）同一个子集中任意两顶点均不相邻，不同子集中的任意两点均相邻显然每个顶点的度都是66，任意4点中，至少有2点属于同一子集，从而它们不相邻也就是说图中不存在两两相邻的4顶点评注2 本题可推广为：俱乐部有（4）人，其中每人都至少认识其中的个人，则在这个人中必定可以找到4个人，他们是两两认识的29.1.18* 已知五个城市两两相连所得的10条道路中，至少有一个交叉路口，如图（）又已知三个村庄和三个城市相连所需的9条道路中，至少有一个交叉路口，如图（）利用上述结论，问：用15条道路把六个城市两两相连，至少会产生多少个交叉路口？解