数学竞赛中图论问题的相关分析

郁文娟

【摘 要】图论不仅是数学竞赛中的重要组成部分，同时在其他领域中也有应用到，如在计算机技术以及物理学中应用相当广泛。可以利用图论的相关知识来解决这些领域中出现的各类问题，因为它可以利用数学模型的形式把这些问题呈现出来，更直观和清晰，利于人们对问题的认识和理解，从来更加快速方便的解决问题。本文主要分析在数学竞赛中，图论问题应用的重要性。

【关键词】图论问题；数学竞赛；应用分析

中图分类号： O157.5 文献标识码： A 文章编号： 2095-2457（2018）30-0152-002

DOI：10.19694/j.cnki.issn2095-2457.2018.30.066

Correlation analysis of graph theory in Mathematical Contest

YU Wen-juan

（School of modern science and technology， Taiyuan University of Technology， Taiyuan Shanxi 030027，China）

【Abstract】Graph theory is not only an important part of the mathematical contest， but also has been applied in other fields， such as computer technology and physics is widely used. Graph theory can be used to solve all kinds of problems in these fields， because it can be used in the form of mathematical models to present these problems， more intuitive and clear， conducive to people's understanding and understanding of the problem， has always been faster and more convenient to solve the problem. This paper mainly analyzes the importance of the application of graph theory in mathematical competition.

【Key words】Graph theory problem； Mathematical contest； Application analysis

1 數学竞赛中应用图论问题的意义

图论问题在18世纪初期就已经开始有运用，由于现代计算机的出现，图论的应用则越来越广泛，包括结构化学、计算机网络以及数学竞赛等。使用图论可以提供给我们一个快速解决问题的方式和角度。数学题中应用题相对偏多，而应用题往往都是在实际背景下产生出来的题型，在数学竞赛中是一种相对比较重要且难度较大的题型，主要考查学生如何通过数学相关的知识来解决和分析实际问题的能力，而这个能力则是通过解决数学图论的能力来展现。

1.1 图论在数学竞赛中的应用与生活紧密相关

图论是研究空间模式德昂以及现实世界中的数量之间的关系。数学这门学科想要对问题处理的结果取得更加精确的结论，不能单靠一个不清晰的定义，而要追求更严密的概念。同时，利用图论中的相关概念以及定义来思考和解决问题，也可以更加直观的、更加自然的让问题得到很好的解决。

1.2 图论实现了科学技术在数学中的有效转化

人们在用数学的方式解决每一个实际问题时，其本质就是简化所表达的问题，然后将其中的抽象知识用一个数学模型的方式简单的展现出来，利用一些先进的技术，如计算机技术来求解模型，最后再重复的推理以及完善结果的准确度，直至满足事情原本所需的要求。

1.3 数学竞赛中使用图论促进数学教学的创新改革，适应社会的发展进度

数学教学的创新改革对社会发展的意义并不完全是传授相关知识给学生，而是要促进学生更好的掌握数学这门学科的技能以及思想方法。然而，想要改善我们目前对数学教学的方式，既可以让学生有效的学到知识，又可以提高教学效率和成果，利用数学图论竞赛是极其重要以及必要的。

2 数学竞赛中常出现的与图论相关的问题

2.1 图的贯通性问题

在考察图的贯通性时，一般会存在两种题型，第一，至少应该除掉几条边来破坏原图中的贯通性；第二，即使将原图连通，在除掉有限条边的情况下，这个图是否依然可以连通。

2.2 图的遍历问题

不管在实际生活中，还是在理论依据上存在的某些问题，都有一部分跟遍历性有着紧密联系，如有名的哥尼斯堡七桥中出现的问题是最早引出遍历问题的。哥尼斯堡城的城区分为四个部分，它们之间由七座桥相互连接而成，怎样既可以将这七座桥都走完并且每座桥只能走一次，同时又可以环绕全程？1736年，欧拉用抽象分析法将问题简化为图论问题，这也是历史上的首个图论问题，顺利的将这个问题得以解决。其实这个问题的实质就是要在图中找到一条封闭式的路，这条路要包含这个图中所有的边，所以就可以将这个问题简化为“一笔画”的问题。

3 解决数学竞赛中图论问题的常用方法

数学与图论跟其他有着完善理论和问题解决办法的体系不同，其分支不同，问题涉及比较广泛，同时有着多样的问题解决方法，一般情况下，一类问题往往存在一种解法，然而不同的解法间缺少一些相关的联系。有一句老话说道，“工欲善其事，必先利其器”，数学竞赛中要使用图论问题，就得先对图论进行了解、探索，其中要了解图论存在哪些问题以及常见的处理问题的方法，再具体进行运用。而在图论问题中，主要研究其组合最值以及存在性两个问题。

3.1 组合最值问题

解决组合最值问题时，往往还存在一些通过利用图形特点来解决组合最值的问题，因为其自变量是离散量，并且要求的最小值或最大值的量与自变量的函数关系不允许用同一个解析式来表达，所以就使得先前代数最值的问题与解决组合最值的问题有所不同。常见的解决办法主要有以下几点：

3.1.1 构造法

关于构造图论问题，通常会先将其进行转换，主要运用各类图的性质及自身特征的方式，此外，有时也会采用染色的方式进行标注，将具有不同性质但类别相同的图区别分开，简化问题，以避免图论问题出现在数学竞赛中，加深竞赛的难度。

3.1.2 調整法

要将调整法运用到图论问题中，必须先要确定存在可以取最值的结构组合，然后在取最值时要充分观察以及分析研究，选择组合对象可能满足的特质，同时要用调整法来体现出它所具备的特质，在不具备该特质的情况下，应当及时调整改编组合对象的结构，促使其能够满足题目要求的条件，但会使相应的函数值变大或变小，以致出现矛盾，最后通过在取最值时，满足组合对象相应的条件来解出这个最值。

3.2 存在性问题

存在性问题的解决方法主要采用反证法、抽屉原理、计数法以及极端原理等方法。

3.2.1 反证法

如果要证明命题的的结论是成立的，但通过其他常规方法证明又比较困难时，可以采用反证法，即从这个结论的否定面着手，通过一系列推理研究致使该结论是矛盾的，则可以证明此结论成立。

3.2.2 抽屉原理

抽屉原理是将需要讨论的元素按一定特质分类，当取出足够多的元素时，再运用抽屉原理将范围缩小，从而推导出属于同一类的某几种元素，它们均同时具备某种特质，由此推导出题目的结论。运用抽屉原理时通常会出现以下几个特点：第一、题目中所讨论的元素具备任意性；第二、题目的结论至少要有一类是具备某种特质的，是一个存在性命题；第三、结论不需要确定，但需存在。

3.2.3 计数法

某些组合问题从表面上观察并不是图论问题，但可以结合图论中提到的有关概念，运用图论中有关定理和性质来解决问题

3.2.4 极端原理

极端原理是以极端元素为出发点，经过理论推理，得出结论，或是从得到结论的否定面着手，通过极端元素推理，得出此推理导致矛盾的结果，进而推导出此结论成立。

4 如何在数学竞赛中合理利用图论

4.1 扩大视野，通过案例列举的方式，代入需要掌握的知识点

为促进学生更好的吸收知识点，所以，在教学前就要找到合适的方法。而图论则是数学竞赛中最有利的工具。数学竞赛中使用图论的方法，对参赛学生自身的能力也有一定的要求，所以，为了更充分的了解到这些知识面，就需要在教学过程中通过案例分析进行讲解，从这些案例中代入知识点，提高学生学习的氛围及兴趣，增加学生自身的代入感，让他们的精力都集中在教学中来，最终达到提高学生学习效果以及教学质量的目的。

4.2 为促进学生的执行力，可以引入软件教学的形式

从先前数学竞赛中体现出来的有关图论的知识点观察到，由于比赛中题目的数据相对较多，所以，如果单纯依靠人工计算的方式来计算数据，这就会使出现的问题越来越复杂，因此，这就必须应用计算机技术的方式，方便高效的处理，提高这些复杂数据的解决能力，让学生能更轻松的学习知识，同时提高学习兴趣。可以引入软件教学的方式进行解决，避免物力、人力的浪费。而在引入教学软件时，只需要运用一些简单、基础、易懂的软件就行，比如Excel表格等，就不需要额外去学难度较大的软件，反而增加学习的困难。

4.3 重视并发掘培养学生的应用性及发散性思维

将图论应用到数学竞赛中，相比于其他的竞赛来说，其是一项通讯性的竞赛，具有比较开放的特点。从研究数学竞赛中用图论解决问题的结果来看，其结果多种多样，很多参赛选手因此不清晰结果的准确性，所以会对这个方案的使用产生犹豫。在这个时候，我们应该充分了解自己，发掘出自己的应用性和发散性思维，对结果不断探讨，找到正确的结果。因为数学竞赛中存在的问题较多，同时也有很多解决办法，所以，不可能解出一个答案是可以让所有人都满意。不同的问题存在，就有不同解决问题的思路，在解决过程中，会遇到很多知识点，所以这就要求学生重视并培养自身的发散性以及应用性思维，促进学生更加全面的对所有的知识点进行认知和理解，然后探讨出一个绝大部分人都足够满意的结果。

5 结语

数学竞赛中的问题专业、抽象并且难度较大，所以就促使其具有一定的趣味以及教育性。在准备使用图论时，首先要先掌握图论的使用原理、方法以及使用过程中存在的问题以及问题的解决方法。在竞赛中使用图论能增强学生对书本上知识的理解，从而简单方便的解决社会活动中存在的各种问题，不仅培养学生分析问题的能力，还培养他们通过分析问题，扩散思路，从而提高解决问题的能力。针对教师，用一些教育软件以及教育案例融入到教学中，不仅可以提高教师的教学水平，还可以提高学生对知识的清晰度和掌握能力。参加一场数学竞赛，通过事前的准备及学习，学生们可以学到很多书本上以及生活中常见的解决问题的方法。

【参考文献】

[1]周文清.数学竞赛中的集合问题[J].中等数学，2017（12）：8-12.

[2]郭梦夏.数学竞赛中图论问题的探究[J].时代教育，2017（23）：173.

[3]刘勇.图论知识在数学竞赛中的应用[J].数学大世界（中旬），2017（08）：37.

[4]钱培星.浅谈数学竞赛中的图论问题[J].课程教育研究，2017（07）：123-124.