图论在数学竞赛中的应用

乔友付

（河池学院数学系 广西 宜州 546300）

图论在数学竞赛中的应用

乔友付

（河池学院数学系 广西 宜州 546300）

本文利用图论的思想和基本知识，有效的解决了数学竞赛中的有关某些对象以及这些对象之间的某几种关系的问题，从而让学生了解应用图论解决数学竞赛问题的思想方法和技巧。

图论；数学竞赛；应用

图论起源于民间的“数学游戏”，其中最著名的是欧拉关于哥尼斯堡七桥问题的论文，并由此确立了他在图论领域的创始人的地位。图论的产生解决了许多用传统数学方法难以解决的问题。经过三百多年的发展，图论已是当代应用数学领域最活跃的学科之一，图论思想对于提高分析，解决问题的能力是十分有益的，在中学数学竞赛中，经常出现一些以图论为背景的试题。这些问题一般不需要高深的数学工具，往往需要深入的思考，和图论的思想方法。如果研究的问题是关于若干个对象以及这些对象之间的若干种关系，并且要证明它们具有某种性质P，可把问题转化为有关图论的问题，为了证明原问题具有性质P，则归结为证明该“图”具有某种结构Q即可。下面讨论图论中的一些简单概念和基本知识在数学竞赛题中的应用。

1 度在某些问题的应用

在数学竞赛遇到的问题涉及到多个对象（人或事物等），而对象之间又恰好有且仅有两种不同的关系。运用其他方法难以解决或不能解决，这时就可以尝试用图论中度数的有关知识去着手思考和帮助解决这些问题。

定理1 设G是n阶图，则G中n个顶点的度之和等于边数e的两倍，即

例1 某地区网球俱乐部的20名成员举行14场单场，每人至少上场一次。证明：必有六场比赛，其中12个参赛者各不相同。

证明：用20个点ν1,ν2,…,ν20代表20名成员，两名选手比赛过，则在相应的顶点间连一条边，得图G。由题意，图G中有14条边，且d(νi)≥1,i=1,2,…,20.

由定理1可得d(ν1)+d(ν2)+…+d(ν20)=2×14＝28.

在每个顶点νi处抹去d(νi)-1条边，由于一条边可能同时被两个端点抹去，所以抹去的边数最多为(d(ν1)-1)+…+(d(ν20)-1)=28-20=8.

故抹去这些边后所得的图G′至少还有14-8=6条边，且图G′中每个顶点的度至多是1，从而这6条边所相邻的12个顶点是各不相同的。即，这6条边所对应的6场比赛的参赛者各不相同。

2 平面图中欧拉公式的巧用

图论中的欧拉公式的应用在数学竞赛中却经常出现，对欧拉公式的灵活应用有利于解决解决图论平面图的数学竞赛问题。

定理2 （欧拉公式）设图G是有ν个顶点，e条边和f个面的连通平面，则

欧拉公式的一个重要应用就是可以决定一个平面简单图中最多的边数。因为一个面上至少有3条边，f个面的边界至少有3f条边。另外，一条边最多是2个面的边界，所以2e≥3f，即。代入欧拉公式，有,从而可得e≤3ν-6。

例2 有n个车站组成的公路网，每个车站至少有6条公路引出，求证：必有两条公路在平面上相交。

分析：“车站”和两站连接的“公路”可以看做图论中的二元关系，要证明两条公路在平面上相交，可转化为证图 具有某些性质。

证明：n个车站用n个顶点表示，每两个车站有公路相同，则相应两顶点间连一边，得图G，由题意知，G中每一点度≥6。若G是平面图，则由于6n≤2e,即，所以有

这个矛盾表明G不是平面图。所以，至少有两条公路在平面上相交。

3 拉姆赛定理

对于一些二元关系的问题可以用度数的有关知识加以解决，但是在一些问题中我们作图G时只考虑两元素之间连线或不连线，可能不方便问题的思考，我们可以用另外的刻画方式进行处理，对边染红、蓝两色，这样就得到了n阶完全图Kn，再根据n阶完全图Kn的性质就可以用来解决此类型的数学竞赛问题。

定理3 设n≥6，则任何一个两色完全图Kn一定含有一个单色三角形。

例3 证明在任何6个人中总有三个人相互认识，或者互不认识。

分析：该问题反映出人与人之间或相互认识或或相互不认识这种二元关系，这正好符合用图论方法研究问题的特征。由于所证结果是存在三人相互认识或相互不认识，若两人握手，就在相应顶点之间连一条边，否则，就不连边，这样在论述方面不是很方便。于是若两人认识，在相应顶点之间连一条边，并染成红色（即连一条红边）；若两人不认识，也在相应顶点之间连条边，并染成蓝色（即连一条蓝边），从而就形成了一个染有红、蓝两色的K6。于是，可将待证问题转化为：在二色K6中一定存在同色三角形。

证明：6个顶点表示6个人，6个顶点间任意两点之间连线，得到6阶完全图 。设x和y是6阶完全图K6的两个顶点。如果x和y表示的两个人认识，则xy边染成红色，否则边xy染成蓝色，于是K6是—2色完全图。根据定理3知K6含有单色三角形。设为Δuνw，如果Δuνw是红色，则顶点u,ν,w所表示的三个人相互认识；如果Δuνw是蓝色，则顶点u,ν,w所表示的三个人相互不认识；即表明在任何6个人中，总有三个人认识，或者不认识。

4 匹配的应用

匹配理论中，主要关注二部图，具体来说，设图G是二部图，X和Y是图G的顶点集合的一个分划，其中X中顶点之间以及Y中顶点之间都不连边。如果图G具有匹配 ，使得X中每个顶点都是M饱和的。也就是说，X中每个顶点在M下都和Y中顶点匹配，则说X可以匹配到Y中。

定理4 二部图G＝(X,Y)，则G中有饱和X中的所有顶点的匹配M的充分必要条件为对∀S⊆X，有表示S中顶点的度的和)。

例4 有n位绅士与n位太太参加一次舞会，每一位绅士恰好认识δ位太太，每位太太也恰好认识δ位绅士。证明可以适当安排，使得每位太太均与她所认识的绅士跳舞。

证明：绅士和太太均用点表示，分别组成点集Y，X，在相认识的人之间连线，得二部图G=(X,Y)，图中每个点的度数均为δ，要使每位太太均与她认识的绅士跳舞，即转化为证明G中存在一个匹配M，使M饱和X中的所有顶点。

我们只要验证图G满足定理4的条件即可。而事实上，对∀S⊆X，每个顶点的度数均为δ，从而问题得证。

5 结束语

从以上例证来看，在运用图论知识解决数学竞赛问题，可基本分为三个步骤：首先，对竞赛问题进行数学抽象，做出相应的图G；其次，根据图论的有关理论，把问题转化为有关的图论问题；最后，证明该图 G具有某些特定的性质，回到竞赛问题本身，得出结论。

［1］陈传理,张同君.竞赛数学教程[M].北京：高等教育出版社,2005.

［2］王朝瑞.图论.[M].3版.北京：北京理工大学出版社,2001.

［3］黄国勋.奥林匹克数学方法选讲[M].上海：上海教育出版社,2002.

［4］魏暹荪.数学竞赛中的图论问题[J].陕西师范大学继续教育学报,2002,19(2)：100-102.

［5］降毅.用图论的方法解两道智力题[J].河套大学学报,2004,1(1)：14-16.

［6］方倩珊.探究数学趣题渗透图论思想[J].思茅师范高等专科学校学报,2006,22 (6)：56-58.

［7］吕同富.拉姆赛型问题的研究及应用[J].佳木斯大学学报,2004,22(2)：281-283.

乔友付（1978—），男，安徽霍邱人，硕士，讲师，主要研究方向为图论及其应用。

本文由广西新世纪教改项目(2010JGB070; 2011JGB321)资助。

江广霞］