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

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

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

3、都握手的人数的最大值是n 2.29.1.3 *九名数学家在一次国际数学会议上相遇，发现他们中的任意三个人中，至少有两个人可以用同一种语言对话.如果每个数学家至多可说三种语言，证明至少有三个数学家可以用同一种语言对 话.解析 用9个点m, V2,，V9表示这九名数学家，如果某两个数学家能用某种语言对话，就在他们相应的顶点之间连一条边并涂以相应的颜色.我们要证明的是：存在三个顶点vi、vj、v使得边（vi ,Vj ）和（V , 丫卜）是同色的.这样的，M、,、vk这三名数学家就能用同一种语言对话.卜面就顶点V1 ,分两种情形:（1） $与V2,，V9均相邻，由于每个数学家至多能说三种语言，所以每一

4、个顶点引出的边的颜色至 多是三种.根据抽屉原理知，从M发出的8条边中至少有2条是同色的，不妨设为（V1,V2）、（W,V3）.于是M、V2、V3所表示的三名数学家能用同一种语言对话.见图（(a)(b)(c)（2） V1与V2, V3,，V9中的至少一点不相邻，不妨设功与功不相邻.由于任意三个数学家中，至少有两个人可以用同一种语言对话，所以，V3, V4 ,，V9中的每一个不是和研相邻就是和功相邻，根据抽屉原理可知，其中至少有4个点与V1或V2相邻.不妨设V3、V4、V5、V6与V1相邻，如图（b）,再对M引出的这4条边用抽屉原理可得，至少有 2条边是同色的，设为（V1 , V3）、（V1, V

5、4）.于是V1、V3、V4所表示的三名数学家能用同一种语言对话.评注 若本题中的九改成八，则命题不成立.反例如图（ c）所示.图中每条边旁的数字表示不同的语 种.2.1.4 4*证明任何一群人中，至少有两个人，它们的朋友数目相同.解析 设任意给定的一群人有 n个.用顶点表示这n个人.当且仅当顶点u、V表示的两个人是朋友时 令u、v相邻，得到n个顶点的简单图 G.对G中任意x,由于它可以和其他 n 1个顶点相邻，所以顶点 x的度d （ x）满足0w d x w n 1 ,即图G的顶点度只能是n个非负数0, 1,，n 1中的一个.如果图 G的顶点的度都不相同，则图 G 具有0度顶点u和n 1度顶点

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

7、 （不一定不同）它们依次与 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的其他所有顶点都相邻.2.1.6 6*是否存在这样的多面体，它有奇数个面，每个面有奇数条棱？解析 不存在这样的多面体.事实上，如果这样的多面体存在，那么用顶点表示这个多面体的面，并且仅当m、Vj所代表的两个面有公共棱时，在图G相应的两顶点之间连一条边，依题意 d v是奇数

8、，于是奇数个奇数和也是奇数.而这一个图中的顶点的和为偶数矛盾.评注 关于图G的顶点和边数之间的关系，有如下定理：图G中边数的两倍等于顶点度数之和.即若G中n个顶点为Vi , V2 ,，Vn ,边数为e,则d vi d V2d Vn 2e.2.1.7 7*n名选手进行对抗赛，每名选手至多赛一场，每场两名选手参加，已赛完 n 1场.证明：至少有一名选手赛过三次.解析 把选手看成顶点.当且仅当Vi、Vj所代表的两名选手比赛过时，令M、Vj相邻，得到含n个顶点的简单图.由于总共赛过n 1场，所以，图G的边数是n 1 .于是d Vi d V2d Vn 2 n 1 .如果图G中所有顶点的度都不超过 2,则

9、由上式得到2 n 1 d v1 d v2d Vn < 2n ,这不可能.因此图G中至少有一个顶点x ,它的度至少是3.于是，顶点x所表示的选手至少赛过三次.2.1.8 8*航空线路共连结 50个城市，现要求从一个城市到另一城市至多需换乘两次飞机，问航空线路最少要多少条（任两城市之间的航空线路数为0或1） ?解析 不妨将50个城市看成50个点，它们之间连的线构成一连通图.图论告诉我们，如果每一点的度（即出发的线条数）至少为 2,则由于边数为点度之和的一半，其数值不小于50;若有一个点的度为1 （显然连通图不存在度为 0的孤立点），则可通过删去该点证明。边数必须至少为49,否则图就不连通（只

10、需对剩下的图不断进行上述处理过程）.于是找到一个城市为中转站，其他城市与之相连，构成一 “星形”即可.故线路最少要 49条.A3A2A1A,A50A52.1.9 9已知九个人Ai, %,，与中，A和两个人握过手，M A3各和四个人握过手，A4、A、A6、A各和五个人握过手，A8、A9各和六个人握过手.证明：这九个人中一定可以找出三个人，他们相互握过手.解析 用9个点Vi, V2,，V9表示Ai, A2,，与这九个人，若两个人握过手，就在他们相应的顶点之间连一条边，这样便得到了一个图G.因为d V9 6,所以存在一个不同于 必，V2 , v3的点M与Vj相邻.显然d Vi >5.考虑与功相

11、邻的另外 5个点，若其中任意一点都不与V相邻，则d vi < 9 1 5 3,这不可能.故必有一点 Vj与v相邻，从而V9、v、Vj两两相邻.即它们表示的三个人互相握过手.2.1.10 0*参加某次学术讨论会的共有263个人，已知每个人至少和三位与会者讨论过问题.证明：至少有一个人和四位或四位以上的学者讨论过问题.解析 用点V, , V2 ,，V263表示263个人，两个人讨论过问题，就在相应的点之间连一条边，得图G .在图G中，任一顶点的次数 3.若没有一个顶点的次数4,则G中的所有顶点的次数都是3.于是d V1d V2d V263 3 263 789,是一个奇数，而这应是一个偶数，

12、所以至少有一个顶点的次数>4.于是命题得证.2.1.11 1*某地区网球俱乐部的 20名成员举行14场单打比赛，每人至少上场一次.求证：必有六场比赛，其12个参赛者各不相同.解析 用20个点表示这20名俱乐部成员，14条边表示14场比赛，得图G .根据题意，d Vi > 1 , i 1,2,，20.于是d v1d v2d v202 14 28.今在每个顶点m处抹去d Vi 1条边（一条边可以同时在其两端点处被抹去），抹去的边数不超过d V1 1 d V2 1d V20 1 28 20 8 .故余下的图G中至少还有6条边，且G中每个顶点的次数都w 1,所以这6场比赛的参赛者各不相同.

13、2.1.12 2* 34 个城市参加双人舞比赛 （每个城市一男一女），赛前，某些选手互相握手. 同一城市的 两人不握手.后来，来自A城的男选手问其他参赛选手他们与人握手的次数，得到的答案都不相同. 问A城女选手和多少人握过手？解析 用顶点表示参赛选手.对于 u、v,当且仅当u、v所表示的两名队员握过手时，令它们相邻，得到一个68个顶点的简单图 G.由于同一个的两名队员之间不握手，所以对任意u, d u W66. A城男选手用x表示.图G中除x外尚有67个点，它们的度各不相同，因此必有一个点度为0 d v 0 ,即v和G中其他顶点不相邻.所以若顶点w表示的选手和顶点 v所表示的选手来自一个城市，

14、则d w 66 .从图G中去掉v和w ,得到含66个顶点的图Gi .则x是Gi中的顶点，并且除x外，其他顶点的度也都不相同.因此和前述证明相同，Gi含有度分别为0和64的顶点p和q,它们在原来图 G中的度分别为1和65.如此继续，可证 0W j W33,图G中含有顶点xj、yj ,它们的度分别为j和66 j ,而且所代表的选手来自同一城市，其中x33 x,所以d x33 33,因此A城女选手握手次数为 33.评注 本题证明中，将G的顶点编号，按度的非降次序（d1wd2ww dn）排列，得到（d1, d2 ,，dn）称为图G的度序列.利用度序列解题是一种重要方法.2.1.13 3*有一个团体会议

15、，有 100人参加.其中任意四个人都至少有一个人认识三人.问：该团体中认识其他所有人的成员最少有多少？解析 先把问题翻译成图论语言.把该团体的成员视为顶点.对于任意两个顶点u、v所代表的成员，当且仅当彼此认识，则在 u、v之间联一条边（即相邻）.得到一个含100个顶点的简单图 G .已知条 件是，图G中任意四个顶点中都至少有一顶点和其他三个顶点相邻.要求图 G中度为99的顶点个数 的最小值m .当图G是完全图时，每个顶点的度都是99,所以有100个度为99的顶点.当图G是非完全图时，图 G中必有两个不相邻的顶点 u和v .显然d u w 98 , d v < 98 .因此图G中度为99的

16、点的个数| w 98 .如果G中除u和v外另有两个顶点x、y不相邻，则u、v、x和y中不存在和其他三个顶点都相邻的 顶点，与题意矛盾.因此 G中除u、v外任意两个顶点相邻.这说明对G中除u、v外的任意点x,均有 d x >97.如果G中除u、v外的任何x都和u、v相邻，则d x 99 .此时G中度为99的顶点个数为98.设G中除u、v外有个顶点x和u、v不都相邻，则有G的性质知，G中除u、v、x外的任意顶点y和u、v、x都相邻.因此d u <98, d v <98, d x <98, d y =99,所以G中度为99的顶点个数为97.这表明含100个顶点的简单图 G中，

17、如果任意四个顶点中必有一个顶点和其他三个顶点都相邻，那么G中至少有97个度为99的顶点.回到原问题，即得：该团体中认识其他所有人的成员最少是97个.评注 本题中的成员数100改为任意的n ,其他条件不变，则结论为该团体至少有n 3人认识其他所 有人.2.1.14 4*毕业舞会有男女学生各 n人参加，n 2.每个男生都和一些但不是全部的女生跳过舞，每个女生也都和一些但非全部的男生跳过舞.证明：总有两名男生B1、B2和两名女生G1、G2，使得B1和Gi , B2和G2跳过舞，但Bi和G2, B2和Gi都未跳过舞.解析 用顶点表示参加舞会的学生，男生的全体用X来表示，女生的全体用Y来表示.对任意的x

18、、y,当且仅当所表示的男生和女生跳过舞时令x、y相邻.X的顶点之间以及 Y的顶点之间都不相邻.已知对任意的X、丫，都有0乂 n,0dy n,要证明图G中含有两条没有公共端点的边.设为是X中度最大的顶点，在与Xi不相邻的Y的顶点中任选y2，由于y2和Xi不相邻，且0 d y n,所以y2和X中某个X2相邻.如果X2和所有与天相邻的顶点相邻，则 d X2 > d Xi i ,与为是X中度最大的顶点矛盾.因此，必有yi是Xi的顶点但和X2不相邻.于是边Xiyi、X2y2没有公共端点.评注 本题解法有一定典型性，抓住图G中度最大的顶点来解决问题.当然，有时也可以从图G中度最小的顶点入手.2.1.

19、15 5* 设A, A2, A3,，4是平面上的6点，其中任3点不共线.如果这些点之间任意连结了 i3条线段，求证：必存在 4点，它们每两点之间都有线段连结.解折 将已连结的i3条线段全染成红色，还未连上的两条用蓝线连上（因为所有两点连一线段时应该共有i5条）.于是必有一个同色三角形，现在的蓝色线只有两条，所以同色三角形必为红色的.不妨设 AA2A3是红色的.A从A4、与、A6引向 AiA2A3顶点各有3条，这9条线段中最多只有 2条蓝色，起码有7条是红色的，因此，或者是 A4,或者是 A,或者是A6 ,引向 AA2A3顶点的线段全是红色.比如说，AA、A4A2.A4A3全是红色，那么4点A、

20、A2、A3、4的每2点连线全是红色的，命题得证.2.1.16 6*在某城有若干栋（>2）独家住宅，其中每栋住宅住有i人.在一个好天气，每个人都将自己的家搬迁了一次.搬迁后每家仍住i人，只是大家都调换了住宅.证明：在搬迁之后，可将这些住宅分别漆上蓝色、绿色和红色，使得对于每个主人来说，他的新居和旧居颜色不一样.解析 将住宅一一编号，使得第一座住宅搬出来的人住进第二座住宅，第二座住宅出来的人住进第三 座住宅于是一定存在一个自， 使得第矗座住宅搬出的人住进第i座住宅.这是个人形成一个“圈”.如果志为偶数，显然只需要 2种颜色，如果&是奇数，3种颜色足够了.然后再考虑其他人，最后形成一个

21、个互相独立的“圈”（当然也可能只有一个），每个圈独自处理即可.2.1.17 7*某俱乐部共有99名成员，每一个成员都声称只愿意和自己认识的人一起打桥牌.已知每个成员都至少认识 67名成员.证明一定有 4名成员，他们可以在一起打桥牌.解析 作一个图G：用99个点表示99名成员，如果两名成员相互认识，就在相应的两个顶点之间连一条边.已知条件是：对任意顶点v, d v >67.欲证G中含有一个4阶完全图K4 .在G中任取一个顶点u,由于d u >67,所以存在顶点v,使得与v相邻且与u不相邻的顶点至多为 （99 1 67 = ） 31个.同样，与v不相邻且与u相邻的顶点也至多 31个.于是图G中至少有（99-31 312 = ） 35个顶点和u、v均相邻.如图所示，设顶点 x和顶点u、v均相邻