人教版初中数学竞赛专题复习计划《第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条．

已知九个人

，，，

中，

和两个人握过手，

、各和四个人握过手，

、、

、

各和五个人握过手，、各和六个人握过手．证明：这九个人中必然能够找出三个人，他们相互

握过手．

解析用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．这样连续，可证0≤≤33，图中含有极点、，它们的度分别为和，并且所代表的选手来自同一城市，此中，所以．所以城女选手握手次数为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，所以存在极点，使得与相邻且与不相邻的极点至多为（99－1－67＝）31个．相同，与不相邻且与相邻的极点也至多31个．于是图中最罕有（99－31－31－2＝）35个极点和、均相邻．以以下列图，设极点和极点、均相邻．因为≥67，并且中至多只有（3l+31+2＝）64个不一样样时和、均相邻的极点，所以极点最少还和一个与、均相邻的极点相邻．从而、、