摘 要：随着网络的发展，图论的作用越来越重要。现如今，国内许多高校都将图论作为一门重要课程开设。本文以具体实例为视角谈谈图论教学中的理论联系实际，让学生真正感受到图论的实用价值，激发学生的学习兴趣。

关键词：图论;组合数学;理论联系实际

1 前言

离散数学是应用数学的一个重要组成部分，图论是离散数学的重要分支。圖论在各方面有很重要的应用，尤其是数学建模方面，大部分社会实际问题都是离散问题。图论教学也越来越受到大家的重视。 如何教好图论课程是一个值得思考的问题。

图论既然作为数学分支，理应用数学严格的表达式给一个明确定义，而不是用文字描述或者画个实际图举例说明。因此针对数学专业的学生，教师来教授图论这门课时用数学化的严格定义。培养学生用数学的语言来描述问题，而数学也能加深对图的定义的理解，对将来做图论相关方面的研究打下良好的基础。

图论是以图为研究对象，图论中的图是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用顶点代表事物，用连接两顶点的边表示相应两个事物间具有这种关系。国内外大部分图论教材都是如下定义的：

图是指有序的三元组G=（V，E，Ф），其中V称为顶点集，E称为边集，而Ф是V到E中元素无序对簇V×V的函数，称为关联函数。

在计算机科学和互联网技术的推动下，近几十年里图论取得了一系列发展成果。许多大师级数学家都因为在图论领域的突出贡献而斩获国际大奖，比如1984年Wolf奖得主Erd?s，1998年Fields奖得主Gowers，2006年Fields奖得主Tao，2012年Abel奖得主Szemerédi。图论尤其是极值图论方面的研究产生了一些革命性的方法，比如概率方法，正则引理，离散傅里叶分析等。现如今，图论的理论和方法越来越受到各行各业的关注，它已逐渐成为解决工程、信息、交通、经济等领域实际问题的重要工具[1，3]。因此国内许多高等院校都将图论作为一门重要课程开设，面向高年级本科生以及研究生。

图论的问题往往听上去很容易，但是要解决却是非常棘手。一段时间下来，很多学生就会产生厌学心理。如果能在图论教学中做到理论联系实际（事实上，图论中的很多问题都来源于现实生活），让学生真正感受到图论的实用价值，或许会好很多。伴随着计算机的发展，图论学科也有了长足的进步。图论最重要的就是应用，图论中很重要的一部分内容，就是其中的经典问题及其有效算法，例如最短路问题的 Dijsktra 算法，最小生成树的 Kruskal 算法和 Prim 算法，二部图最大匹配的匈牙利算法，最大流的标号算法等等。在教学过程中，要求学生深刻理解这些基本算法，并尝试去编写算法的程序代码。同时，在此基础上，也可以适当地提出一些派生问题，启发学生学习如何设计算法，比如在学习最小生成树的算法时，可以要求学生设计求最小森林的算法。在现实生活中，解决其它实际问题的算法往往是以这些基本算法作为子算法，或在此基础上进行适当修改而成的。因此，通过图论的学习，可以提高学生对算法的理解和设计能力，强化程序代码的编写能力。

本文以具体实例为视角谈谈如何在图论教学中做到理论联系实际，引导学生积极思考，让学生体会到发现问题和解决问题的乐趣，从而激发学生的学习兴趣。

2 实例

下面这个例子来自[2]，一般称为宴会定理。

问题[1]在任何宴会上，总有两个人在该宴会上恰有相同的朋友数。

学生看到这个定理的时候，或多或少会有些惊讶。这个定理与当下很时髦的社交网络（比如微信朋友圈）联系很紧密。下面给出简洁证明。

证明：不妨记参加宴会的人分别为。每个认识的人数只能是，由于和不能同时出现。这样每个人认识的人数只有种可能。把这种可能性作为笼子，个人作为鸽子运用鸽笼原理可知必然存在两个人认识的人数一样多。

上述证明用到组合数学中一个重要原理—鸽笼原理，也称抽屉原理，最早是由德国数学家狄利克雷发现的。其本质是在用平均值思想，比如班上这次数学考试平均分为80分，那么一定有人成绩大于等于80分，也一定有人成绩小于等于80分。但是究竟谁的成绩大于等于80分，谁的成绩小于等于80分并不清楚。

下面再看一个与社交网络紧密联系的图论问题。

问题[2]假设认识是相互的，任意6人集会一定有3人互相认识或者有3人互相不认识。

证明：不妨记这6个人为，下面考虑与认识的人构成的集合以及与不认识的人构成的集合。由鸽笼原理可知或者或者。若，若S中有两人认识，则他们与一起构成三人互相认识，否则S中任意两人都不认识，这样会产生三人互相不认识。若，若T中有两人不认识，则他们与一起构成三人互相不认识，否则T中任意两人都认识，这样会产生三人互相认识。

3 结束语

图论是一门很重要的学科，有很重要的应用。目前，国内很多高校都有图论的教学课程和从事图论研究的科研工作者。学好了图论课程，学生在以后的工作中，会增加一门很重要的技能，在利用数学模型解决实际问题的时候，能够开拓思路，建立比较好的数学模型。以上两个例子只是图论与现实世界紧密联系的一些例子的代表。如果我们能在图论教学中多举这样的例子，相信会逐步消除学生的厌学心理，让学生真正感受到图论的作用，真正体会到学习图论的乐趣。

参考文献

[1]范益政，汪毅，龚世才，等.图论导引[M].北京：人民邮电出版社，2007：35.

[2]Wells D.Are These the Most Beautiful[J].Math Intelligencer，1990，12（3）：37-41.

[3]徐俊明.图论及其应用[M].合肥：中国科学技术大学出版社，2004.

作者简介

刘猛（1990-），男，汉族，河南信阳人，博士，安徽大学数学科学学院，讲师，主要从事组合数学与图论方向研究。