内容发布更新时间 : 2024/4/26 4:35:00星期一 下面是文章的全部内容请认真阅读。
初中数学第29章图论初步竞赛专题复习（人教版带答案）
5 c 第29 图论初步
2911* 某大型晚会有2018个人参加，已知他们每个人至少认识其中的一个人．证明必有一个人至少认识其中的二个人．
解析 2018这个数目较大，我们先考虑某小型晚会有5人参加，已知他们每个人至少认识其中的一个人．证明必有一个人至少认识其中的二个人．
用5个点 、 、 、 、 表示5个人，如果两个人彼此认识（本中的“认识”都是指相互认识），就在表示这两个人的顶点之间连一条边．对顶点功说，由于 所表示的人至少认识其他4个人的一个，不妨设 与 认识，即 和 相邻，同样，设 与 相邻，如图所示．对于顶点 说，无论它与 、 、 、 哪个相邻，都会出现一个顶点引出两条边的情况．于是问题得以解决．
用同样的方法可以证明，对2018个人说，命题成立．其实，把2018换成任意一个大于l的奇数，命题也成立．
2912* 在一间房子里有 （ 3）个人，至少有一个人没有和房子里每个人握手，房子里可能与每个人都握手的人数的最大值是多少？
解析 用 个顶点表示 个人，若某两个人握过手，就在他们相应的顶点之间连一条边，这样就得到了一个图 ．因为不是任何两个人都握过手，所以 的边数最多是完全图 （即 个点每两点之间恰连一条边）的边数减1，去掉的那条边的两个端点 和 所表示的两个人未握过手．所以房子里可能与每个人都握手的人数的最大值是 ．
2913*** 九名数学家在一次国际数学会议上相遇，发现他们中的任意三个人中，至少有两个人可以用同一种语言对话．如果每个数学家至多可说三种语言，证明至少有三个数学家可以用同一种语言对话．
解析 用9个点 ， ，…， 表示这九名数学家，如果某两个数学
家能用某种语言对话，就在他们相应的顶点之间连一条边并涂以相应的颜色．我们要证明的是存在三个顶点 、 、 ，使得边（ ， ）和（ ， ）是同色的．这样的， 、 、 这三名数学家就能用同一种语言对话．
下面就顶点 ，分两种情形
（1） 与 ，…， 均相邻，由于每个数学家至多能说三种语言，所以每一个顶点引出的边的颜色至多是三种．根据抽屉原理知，从 发出的8条边中至少有2条是同色的，不妨设为（ ， ）、（ ， ）．于是 、 、 所表示的三名数学家能用同一种语言对话．见图（ ）．
（2） 与 ， ，…， 中的至少一点不相邻，不妨设功与功不相邻．由于任意三个数学家中，至少有两个人可以用同一种语言对话，所以， ， ，…， 中的每一个不是和研相邻就是和功相邻，根据抽屉原理可知，其中至少有4个点与 或 相邻．不妨设 、 、 、 与 相邻，如图（ ），再对 引出的这4条边用抽屉原理可得，至少有2条边是同色的，设为（ ， ）、（ ， ）．于是 、 、 所表示的三名数学家能用同一种语言对话．
评注 若本题中的九改成八，则命题不成立．反例如图（ ）所示．图中每条边旁的数字表示不同的语种．
2914** 证明任何一群人中，至少有两个人，它们的朋友数目相同．
解析 设任意给定的一群人有 个．用顶点表示这 个人．当且仅当顶点 、 表示的两个人是朋友时令 、 相邻，得到 个顶点的简单图 ．
对 中任意 ，由于它可以和其他 个顶点相邻，所以顶点 的度 （ ）满足 ，即图 的顶点度只能是 个非负数0，1，…， 中的一个．如果图 的顶点的度都不相同，则图 具有0度顶点 和 度顶点 ． 度顶点和 中其他顶点都相邻，特别地和顶点 相邻．但0度顶点 和 中任何顶点都不相邻，矛盾．这就证明了 中必定有两个顶点，它们的度相同．也就是说，这群人必有两个人，他们的朋友一样多．
2915*** 有一个参观团，其中任意四个成员中总有一名成员原先见过其他三名成员．证明在任意四名成员中，总有一名成员原先见过所有成员．
解析 用图论语言表示即图 的任意四点中至少有一个顶点和其他三个顶点相邻．证明图 任意四个顶点中至少一个顶点和 中其他所有顶点都相邻．
用反证法．如果命题不成立，则 中有四个点 、 、 、 ，它们和图 中的其他所有顶点不都相邻．于是存在四个顶点 、 、 、 （不一定不同）它们依次与 、 、 、 都不相邻．如图．所以 不是 、 、 中的一个，且 与 是两个不同的顶点．
如果 与 不同，则 、 、 、 中没有一个顶点和其他三个顶点都相邻，和已知矛盾．所以 和 重合．同理可证， 和 重合．于是 和 、 、 都不相邻，和已知矛盾．
这就证明了图 中任意四个顶点中至少有一个顶点和 的其他所有顶点都相邻．
2916** 是否存在这样的多面体，它有奇数个面，每个面有奇数条棱？
解析 不存在这样的多面体．事实上，如果这样的多面体存在，那么用顶点表示这个多面体的面，并且仅当 、 所代表的两个面有共棱时，在图 相应的两顶点之间连一条边，依题意 是奇数，于是奇数个奇数和也是奇数．而这一个图中的顶点的和为偶数矛盾．
评注 关于图 的顶点和边数之间的关系，有如下定理图 中边数的两倍等于顶点度数之和．即若 中 个顶点为 ， ，…， ，边数为 ，则
．
2917* 名选手进行对抗赛，每名选手至多赛一场，每场两名选手参加，已赛完 场．证明至少有一名选手赛过三次．
解析 把选手看成顶点．当且仅当 、 所代表的两名选手比赛过时，令 、 相邻，得到含 个顶点的简单图．由于总共赛过 场，所以，