内容发布更新时间 : 2024/5/18 6:57:34星期一 下面是文章的全部内容请认真阅读。

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