乔友付

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

图论在数学竞赛中的应用

乔友付

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

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

图论；数学竞赛；应用

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

1 度在某些问题的应用

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