图论知识在数学竞赛中的应用

云南省安宁市安宁中学 刘 勇

图论知识在数学竞赛中的应用

云南省安宁市安宁中学 刘 勇

本文中主要对数学竞赛中经常出现的顶点的度和欧拉问题做了探究，在了解了相关知识之后，通过对例题的研究分析来发现这些知识在数学竞赛中是如何运用的，增强学生在数学竞赛中对此类问题的运用能力。

数学竞赛；顶点的度；欧拉问题

一、图论在数学竞赛中的地位

数学竞赛起源于匈牙利，我国自1956年举办数学竞赛以来，一直致力于数学人才的发现与培养，数学竞赛的举办提高了中学生学习数学的积极性，培养了学生热爱数学的兴趣。数学竞赛所涉及的内容主要为四大方面：代数、平面几何、初等数论、组合。组合在竞赛中主要考查的内容为计数、组合最值、图论、逻辑推理和组合结构，在组合计数和组合结构中，往往需要用到图论的知识来解决问题，由此可见图论在组合中的重要性。

图论的起源和发展离不开趣味数学问题，被大众所公认的图论起源是一个有趣的数学问题——哥尼斯堡的七桥问题。数学竞赛的举办是为了能够对知识活学活用，解决现实中的实际问题，图论问题正好具备了这样的条件，因此出现在了数学竞赛中。

近些年以来，图论在数学竞赛中多次出现，一方面是因为图论自身的不断发展，图论的问题也越来越多：另一方面是因为图论的问题不涉及太深的理论知识，只需要通俗易懂的方式就可以解决问题。图论满足了选拔优秀数学人才的宗旨，所以图论在数学竞赛中体现得越来越重要。

二、顶点的度在数学竞赛中的应用

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

解 ：用20个顶点来表示20条边，成员之间如果进行了单打比赛，就在对应的两顶点之间连一条边，从而得到图。设各顶点的度为并且有di≥1。可得：

例2 国际乒乓球男女混合双打大奖赛有24对选手参加，赛前一些选手握了手，但是同一对选手之间不握手。赛后某个男选手问每个选手的握手次数，每人的回答各不相同，问这名男选手的女搭档和多少人握了手？

三、欧拉问题在数学竞赛中的应用

例3 如图1是一栋房子的平面图，现在客人需要从A出发，走过所有的门和所有的房间，最后从B出来，请问是否存在这样的走法？

图1

图2

解：不存在这样的走法。

我们把A和B以及每间房都用一个点来表示，两房间之间有门的地方用一条边来连接，这样就可以得到了图G，如图2所示。在图中，奇顶点的个数为4，所以图不存在一笔画完，即客人不能够从A通过所有的门走遍所有的房间。

例4 设n＞3，考虑在同一圆周上的（2n-1）个互不相同的点所成的集合E。将E中一部分点染成黑色，其余的点不染色。如果至少有一对黑点，以它们为端点的两条弧中有一条的内部（不包含端点）恰含中个点，则称这种染色方式为“好的”。如果将E中个点染黑的每一种染色方式都是好的，求的最小值。

（1）当2n-1能够整除3时，图G正好由3个圈组成，每个圈的顶点分别为：

[1]乔友付．图论在数学竞赛中的应用[J]．科技视界，2012（1）．

[2]熊斌，郑仲义．数学奥林匹克小丛书高中卷．图论[M]．上海：华东师范大学出版社，2011(12)．