?/p>
29
?/p>
图论初步
29.1.1*
某大型晚会有
2009
个人参加,已知他们每个人至少认识其中的一个人.证明:必有一个人?/p>
少认识其中的二个人.
解析
2009
这个数目较大,我们先考虑:某小型晚会?/p>
5
人参加,已知他们每个人至少认识其中的一
个人.证明:必有一个人至少认识其中的二个人?/p>
?/p>
5
个点
?/p>
?/p>
?/p>
?/p>
表示
5
个人,如果两个人彼此认识(本章中的“认识”都是指相互认识?/p>
?/p>
就在表示这两个人的顶点之间连一条边.对顶点功来说,由于
所表示的人至少认识其他
4
个人的一
个,不妨?/p>
?/p>
认识,即
?
相邻,同样,?
?
相邻,如图所示.对于顶点
来说,无论它
?/p>
?
?
?
哪个相邻,都会出现一个顶点引出两条边的情况.于是问题得以解决?/p>
用同样的方法可以证明,对
2009
个人来说,命题成立.其实,把
2009
换成任意一个大?/p>
l
的奇数,
命题也成立.
29.1.2*
在一间房子里?/p>
?/p>
>3
)个人,至少有一个人没有和房子里每个人握手,房子里可能与?/p>
个人都握手的人数的最大值是多少?/p>
解析
?/p>
个顶点表?/p>
个人?/p>
若某两个人握过手?/p>
就在他们相应的顶点之间连一条边?/p>
这样就得到了
一个图
.因为不是任何两个人都握过手,所?
的边数最多是完全?
(即
个点每两点之间恰?
一条边?/p>
的边数减
1
?/p>
去掉的那条边的两个端?/p>
?/p>
所表示的两个人未握过手?/p>
所以房子里可能与每
个人都握手的人数的最大值是
?/p>
29.1.3***
九名数学家在一次国际数学会议上相遇,发现他们中的任意三个人中,至少有两个人可以
用同一种语言对话.如果每个数学家至多可说三种语言,证明至少有三个数学家可以用同一种语言?/p>
话.
解析
?/p>
9
个点
?
,…,
表示这九名数学家,如果某两个数学家能用某种语言对话,就在他?
相应的顶点之间连一条边并涂以相应的颜色?/p>
我们要证明的是:
存在三个顶点
?/p>
?/p>
?/p>
使得?/p>
?/p>
?/p>
)和?/p>
?
)是同色的.这样的,
?
?
这三名数学家就能用同一种语言对话?/p>
下面就顶?/p>
,分两种情形?/p>
?/p>
1
?/p>
?
,…,
均相邻,由于每个数学家至多能说三种语言,所以每一个顶点引出的边的颜色?
多是三种?/p>
根据抽屉原理知,
?/p>
发出?/p>
8
条边中至少有
2
条是同色的,
不妨设为
?/p>
?/p>
?/p>
?/p>
?/p>
?/p>
?/p>
?/p>
?