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

内容发布更新时间 : 2024/12/25 2:24:00星期一 下面是文章的全部内容请认真阅读。

第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条.