离散数学中图论部分教学的研究

李建平

摘 要 在我们学院的信息与计算专业中，数据结构、算法分析以及数据库原理等课程都要涉及到离散数学中图论的知识，因此，离散数学中关于图论部分的教学尤为重要。根据图论的概念、公式以及定理比较多的特点，为了避免教学的枯燥难懂，本文从以下三个方面进行了探讨：结合知识背景、引入数模思想、开展大创项目。

关键词 趣味教学 数模思想 大创项目

中图分类号：G424 文献标识码：A DOI：10.16400/j.cnki.kjdkx.2018.01.061

Research on the teaching of graph theory in Discrete Mathematics

——Based on information and computing major

LI Jianping

（Faculty of Applied Mathematics， Guangdong University of Technology， Guangzhou， Guangdong 510090）

Abstract In the information and computing major of our college， the knowledge of graph theory in Discrete Mathematics is applied in some courses such as data structure， algorithm analysis and database principles etc. So， It is very important for the teaching of graph theory in Discrete Mathematics. According to the characteristics of graph theory and avoiding the dull teaching， this paper discusses from the following three aspects： combining background of graph theory， introducing the thought of mathematics modeling and developing the innovative projects for Students.

Keywords interest teaching； the thought of mathematics modeling； the innovative projects

0 引言

离散数学中的图论是数学的一个重要分支，是研究自然科学、工程技术、社会科学等问题的一个重要的现代数学工具，在数据结构、算法分析和数据库原理等课程学习中都占据了很重要的地位。它是通过点和线组成的拓扑图形，较为方便的模拟自然界和人类社会的各种系统并建立相应的数学模型，根据图的性质进行分析，提供研究各种系统的理论。图是数据结构和算法学中最强大的框架之一，所有类型的结构或系统几乎都可以用图来表现。图论知识被广泛应用到各种领域，如万维网、社交网络、交通网络、通信网络、图像处理中的属性图、化学分子结构以及生态系统中的食物链等都可以用图来描述他们之间的复杂关系。随着计算机的发展，图论得到了迅猛发展，更进一步向各个学科渗透。图论知识与线性规划、动态规划等优化理论和方法相互渗透。图论中有着丰富的算法如求单源最短路径的迪杰斯特拉算法，SPFA算法，求负权回路的BELLMAN算法，多源最短路径的FLOYD算法，拓扑排序算法，最小生成树的PRIM和KRUSKAL算法等等。图论算法提供了对很多问题都有效的一种简单而系统的建模方式，很多问题都可以转化为图论问题，然后用图论的基本算法加以解决；这门课程的学习，不仅可以培养学生的抽象思维能力、逻辑推理能力、创新能力、分析问题和解决问题的能力，也为学生的后续课程打下了坚实的基础。

1图论教学方法探讨

我们学院信息计算专业要求学生具有良好的数学素养，掌握信息科学和计算科学的基本理论和方法，旨在培养能在信息与计算机领域从事理论和应用研究以及软件开发设计工作的高素质应用型人才。开设的多门计算机方面的课程，如数据库原理、数据结构、算法设计与分析等都要涉及到图论知识，因此离散数学中的图论部分的教学显得尤为重要。但是圖论的概念、公式和定理比较多，定理的证明通常相对较难，在一定程度上造成教学枯燥难懂。通过对图论部分的教学的不断探索和学生的交流，本文对本部分知识的教学进行了以下的探讨。

1.1 引入图论背景，创设学习情境，实行趣味教学

图论中概念、定理比较多，初学者不易掌握。在进行图论课概念的教学时，要善于结合生活实际，把概念具体化，使学生觉得这些抽象的概念就在自己的身边，伸手即可摸到。例如：在讲欧拉图时，可以先从2007年河南新乡回龙景区新增景点——“七座桥”的100万元的现金大奖的问题，引申回到经典的哥尼斯堡七桥问题，以及爱尔兰数学家哈密顿（Halmiton）提出的“周游世界”的游戏，最后回到大家熟悉的一笔画问题，从而引出欧拉图的概念及其应用。在讲解匹配章节时，引入教师课表安排问题，快递员送货等问题。在讲解连通度时，介绍投递员问题以及网络的安全性问题；讲染色问题时，可提出化学品的贮置问题，考试日程安排以及教室与课程安排问题等。从图论的背景以及现实生活中的实际问题等有趣味的例子引入到枯燥的概念与定理中，让学生感到学有所用，主动去思考，主动去寻求答案，从而真正参与到教学活动中，这样可以充分地调动学生的求知欲和学习乐趣，从而使学生对所学的知识将更加深刻，收获将更多，因此教学质量与教学效果将得到提升。

1.2 引入数模思想，结合具体事例，撰写课程论文

数学建模是一种数学的思考方法，是运用数学的语言和方法，通过抽象，简化建立能近似刻画并解决实际问题的一种强有力的数学手段。它将一个实际的问题简化为一个可以用数据和很简短的语言能表示出来的问题，然后通过数学工具解决这个问题的过程。在实际问题中，物体或人可以用图的顶点来表示，它们之间的相互联系可以用顶点之间的连线表示，通过这样的转化，一些实际问题就可以变成简单的图论问题。因此在圖论的教学过程中，通过一些简单的模型介绍数学建模的思想及方法，将数学建模的思维和方法融入图论教学中，通过具体的实例，让学生建立简单的数学模型。例如，在介绍最小树的Prim算法与Kruskal算法时，可以引入实例图书馆的学习资源如何优化配置，农村交通建设，最优布线问题等。在介绍匈牙利算法以及Kuhn-Munkers算法时，可以引入学校的教师课表如何安排，大学生就业问题以及大龄男女婚配问题等实例。在讲图论部分的算法分析时布置大作业，让学生分组讨论，对某一具体实例进行分析，建立简单的数学模型，找出相应的算法，完成课程论文。通过这些实例的建模与练习，学生进一步掌握了图论部分的经典算法，初步了解算法和数模思想，增加了学生的动手能力和学习兴趣，为后面课程的学习奠定了坚实的基础。

1.3 开展大创项目，培养创新意识，实施实践教学

为了提高大学生的创新实践能力，学校开展了大学生创新创业项目。 适应新时代的发展，将离散数学中的图论知识与大创项目相结合，开展图论方面的大学生创新创业项目申请，建立创新团队，这样可以培养学生的创新意识，将实践教学模式应用到图论部分的教学。课堂上，将传统教学模式与探讨式教学相结合，加强老师与学生之间、学生与学生之间相互探讨，对学生的疑惑进行答疑，发挥学生的学习主观能动性，培养学生分析问题和解决问题的能力。课堂外，主要实施实践教学，借鉴“翻转课堂”的教学模式，让学生通过图书馆、网上资源对新知识自主学习。教会学生查阅相关文献，带领学生了解学科发展动态，培养学生的论文查阅意识和能力，并带领学生撰写小论文，为课程论文和毕业论文奠定基础，培养学生的创新意识和科研意识，为部分学生继续深造奠定研究基础。在学生大创项目完成过程中，遇到实际问题，鼓励他们运用图论知识建立基本的数学模型，编写相应的程序来解决问题。将大创项目与图论知识结合，将探讨式教学与实践教学运用到课堂中，既巩固了图论的理论知识，加深了对图论知识的理解，也培养了学生的创新意识，锻炼了学生的编程能力和实践能力，为毕业设计和就业做好铺垫。

2结语

对我们学院信息与计算专业的学生来说，离散数学中的图论部分是重要而又不易掌握的知识点。随着计算机与科技的发展，离散数学中的图论知识越来越重要，越来越多的应用领域。离散数学中图论部分的学习，不仅可以奠定学生的良好数学素养，更可以提高他们的算法分析与实现能力，为后续的数据结构、算法分析以及数据库原理等课程打下坚实的基础。因此，我们需要更加积极探索如何更好地上好离散数学中的图论部分。

参考文献

[1] J.A. Bondy， U.S.R. Murty， Graph Theory[M].Springer，2008.

[2] Chartrand G，Oellermann 0 R.Applied and algorithmic graph theory[M].New York：McGraw—Hill，1993.

[3] 屈婉玲，耿素云，张立昂.离散数学[M].高等教育出版社，2008.

[4] 孙玲琍，李治.关于《离散数学》图论教学的思考[J].计算机科学，2010.37：117-118.

[5] 翟明清.浅析图论教学[J].大学数学，2011.27：203-206.

[6] 孙培，刘凯，曾俊杰，杨本朝.在图论课程中融入数学建模思想的教学改革初探[J].大学数学，2015.8：118-119.