数学竞赛中的图论问题(3)

G所含的顶点个数n叫做图G的阶. 若干个点（称之为顶点）有些点之间有边相连，这就构成了一个图G. 而以点x为端点的边的条数称为点x的度，也叫顶x的次数，记作

v1 v2 v5 v1 e2 e3 e4 v2 v3 v4 v4 v3.

e1 图（1） x1

x2

x3

图（2）

K3，3

y1 y2 y3 y4 y5

图（3）

在图（2）中，连接顶点v1，v3的边共有三条：e1，e2，e3. 这样的边称为重边.在图里，有的边的两个端点重合，这样的边叫做环，例如图（2）中，边e4就是一个环.无环、无重边的图叫做简单图.例如图（1）和图（3）就是简单图，而图（2）则不是简单图.

设G是一个图，v是图G的一个顶点.图G中所有和v相邻的顶点的集合记作N（v），它叫做顶点v的邻域.所有以v为一端点的边数叫做顶点v的度，记作的d（v）.例如，图（1）中v1，v2，v3，v4，v5的度都为4，图（2）中，v1的度为6.注意环的度要算成2.对于简单图中任意顶点v，恒有0≤d（v）≤n-1.

设G是n阶简单图，如果G的任意两个顶点都相邻，则G叫做n阶完全图，记作Kn.例如图（1）就是5阶完全图K5.很显然，Kn的每个顶点的度都是n-1.顶点的度都是k的图叫做k正则图.

对简单图G，它的顶点集合V（G）可以划分为两个子集X和Y，使得X的

2

顶点之间以及Y的顶点之间都不相邻，而每条边的端点，一个在X中，另一个在Y中，则图G叫做二部图.例如，图（3）就是一个二部图.

设G是二部图，它的顶点集合V（G）可以划分为两个子集X和Y，使得X中每个顶点和Y的所有顶点都相邻，而X的顶点之间以及Y的顶点之间都不相邻，则G叫做完全二部图.如果X与Y所含顶点个数分别是|X|=n，|Y|=m，则记完全二部图G为Kn，m.例如图（3）就是完全二部图K3,5.

图的基本概念是从客观世界中抽象出来的.它提供了一种熟悉模型.在现实生活中可以找到很多图的例子.例如，在一个舞会上，参加舞会的任意两个人，要么相互认识，要么互不认识.要描述参加舞会的人民之间的相互认识关系就可以用图的概念.把参加舞会的人视为顶点，其集合记为V，对于u，v∈V，如果u和v所代表的两个人认识，则在顶点u和v之间连一条边，如果u和v所代表的两个人互不认识，则u和v之间不连边.这样就得到了图.

在熟悉了图的概念之后，就可以具体的介绍图论中的基本定理.

2.1度在数学竞赛中的应用

2.1.1 度的基本概念和欧拉定理

前面已经介绍了图论中的基本概念，因此，这里不再重复度的概念了.设图G是n阶图，在图G中得到的度和边数之间存在着密切的联系，即有下面的定理和推论.

定理1图G中所有点的度之和等于边数的2倍.

定理1是图论中最早出现的一个基本定理，它最早出现在著名数学家欧拉为解决哥尼斯堡七桥问题而撰写并于1736年发表的论文里，是解决哥尼斯堡七桥问题的主要依据.这个定理有许多重要的应用，因此，它是解决数学竞赛中有关问题的一个有力工具.

推论 图中奇次顶总数是偶数.

2.1.2 应用举例

例1 n人聚会，n>3，其中至少有一人没有和其他所有人握手.聚会中可能和

3

每个人都握手的人数之最大值是多少？（“希望杯”邀请赛试题）

解 由题意，把参加聚会的人视为顶点，其集合记作V，对于

，v∈V，如

果u和v所表示的两个人握了手，则令u和v相邻，得到n阶简单图记作G.则图G中至少有一个顶点u，使得

.这表明，图G不是完全图.

要求的是，聚会中和其他所有的人都握手的人数的最大值，即求图G中度为n-1的顶点个数之最大值.于是即求所有n阶非完全的简单图G中度为n-1的顶点个数之最大值m.

由于图G是非完全图，所以至少有两个顶点u和v是不相邻的，因此d(u)≤n-2，d(v)≤n-2.这表明，m≤n-2.

取一个n-2阶完全图Kn-2，另取两个顶点u和v.令Kn-2中每个顶点都和u与v相邻，而u与v不相邻，得到的图记作Kn-2+u+v.很明显，图Kn-2+u+v不是完全图，而且d(u)=d(v)=n-2，并且对除u，v外任意的顶点x均有d（x）=n-1.这表明m=n-2.即聚会中和每个人都握手的人数之最大值是n-2.

例2 有一个团体，由1982个人组成，其中任意四个人中都至少有一个人认识其他三个人.问该团体中认识其他所有人的成员最少有多少？（上海市竞赛题）

解 把该团体的成员视为顶点，其集合记作V.对于u，v∈V，如果u，v所表示的两名成员彼此认识，则令u和v相邻，否则令u和v不相邻，得到的是一个1982阶简单图G.由已知条件可知，如果1982阶简单图G的任意四个顶点中都至少有一个顶点和其他三个顶点相邻.求图G中至少有多少个度为1981的顶点？

当图G为完全图时，图G的每个顶点的度都是1981.所以有1982个度为1981的顶点.

当图G为非完全图时，图G中必有两个不相邻的顶点u和v，显然有d（u）≤1980，d（v）≤1980.因此，图G中度为1981的顶点的个数≤1980.如果图G中除u和v外还有两个顶点x和y不相邻，则u，v，x和y中不存在和其他三个顶点都相邻的顶点，与图G所具有的性质矛盾.因此图G中除u和v外任意两个顶点都相邻.这说明，对G中除u和v外的任意顶点x，都有d（x）≥1979.如果G中除u和v外的任意顶点x都和u与v相邻，则d（x）=1981.此时，G中度为1981的顶点个数为1980.设G中除u和v外有个顶点x和u与v不都相邻，则

4

有题意，G中除u，v和x之外的任意顶点y和u、v与x都相邻.因此，（u）d≤1980，d（v）≤1980，d（x）≤1980，且d（y）=1981.所以G中度为1981的顶点个数为1879,.这表明，如果1982阶简单图G中任意四个顶点中必有一个顶点和其他三个顶点都相邻，则G中至少有1979个度为1981的顶点.

所以，该团体中认识其他所有人的成员最少是1979.

例3 有7为男生与7为女生参加一次舞会，会后统计出各人的跳舞次数为（按从小到大的顺序）：

3，3，3，3，3，4，6，6，6，6，6，6，6，6 （1） 证明其中必有错误.（北京市竞赛题）

证明 用点表示人，如果两个人跳过一次舞，就在相应的两个点之间连一条线.跳舞次数的和就是图中各点的度的和，而（1）中有5个奇数，总和为奇数，这与定理1矛盾！

例4 在例3 中，如果统计的跳舞次数为3，3，3，3，3，5，6， 6，6，6，6，6，6，6，其中是否有错？这里约定男生不与男生跳舞，女生也不与女生跳舞.（北京市竞赛题）

解 我们用黑点表示男生，红点表示女生.在跳过舞的两个人之间用边相连（跳几次就连几次）.根据约定，黑点之间互不相连，红点之间也互不相连.所得的图为二部图，显然

所有黑点的度之和=所有红点的度之和=图中的边数 （2） 但题中给出的14个数中仅有一个数5不被3整除，这样（2）的一边被3整除；另一边恰有一个数不被3整除，从而不被3整除.矛盾！

例5晚会上大家握手言欢，试证握过奇次手的人数是偶数.（全国初中数学竞赛试题）

证 构作一图，以参加晚会的人为顶，仅当二人握手之时，在相应的二项间加一条边.于是没人握手的次数即为所造的图的相应顶之次数.由定理1的推论，奇次顶的个数是偶数，所以握过手的人数为偶数.

例6 大于7公斤的整公斤的重量都可以仅有一些3公斤和5公斤的两种砝码来称量.（《学校报》公开赛试题）

证 只需证明对任意给定的自然数n，存在二部图G(n)，其中X顶子集有n

5

个顶点，每顶都只有一次，Y顶子集中的项是3次或5次的.

下面用数学归纳法证明之：

当n=8时，结论显然成立，如图（4）

x1 x2 x3 x4 x5 x6 x7 x8 y1 y2

假设对于此，在

的

,结论以成立，顶子集中添加一项

图（4）

. 以下证明对，结论仍成立. 为

的

中顶是3

；由归纳法假设，在

次或5次的，分以下两种情形讨论：

(i)若

中皆三次顶，去

，

，,将其重合成一个顶

,再于

与

之间连一条边，最后把劈开成两个5次顶，则得满足要求的

(ii)若Y中有5次顶，设d(yi)?5，在yi与xk?1之间连一边，再把yi劈开成两个3次顶，则得满足要求的二分图G?k?1?.证毕.

2.2欧拉回路和欧拉迹在数学竞赛中的应用

在上节已经提到，度的概念和欧拉定理是著名数学家欧拉为解决所谓哥尼斯堡七桥问题而提出的.古城哥尼斯堡位于普瑞格尔河的两岸及河中的两个岛上，城市的各个部分由七座桥连接.十八世纪，哥尼斯堡属于东普鲁士（纤维苏联的加里宁格勒）.那时候，哥尼斯堡市民生活富足.每到星期天，市民们喜欢四处散布.于是便产生了这样的问题：是否可以设计一种方案，使得人们从家里出发，经过每座桥恰好一次，最后回到家里.尽管许多人试图解决这个问题，但是谁也

6

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库数学竞赛中的图论问题(3)在线全文阅读。