ABSTRACT

Based on the professional background of information and computing science and the teaching practice of graph theory, this paper puts forward the measures of teaching reform of graph theory from the original idea of graph theory. At the same time, the examination method, training plan revision and textbook compilation of graph theory are discussed.

Keywords:Graph Theory, Teaching, Information and Computing Science

信息与计算科学专业图论教学探讨

华洪波

淮阴工学院数理学院，江苏 淮安

收稿日期：2019年8月8日；录用日期：2019年8月23日；发布日期：2019年8月30日

摘 要

本文基于信息与计算科学的专业背景和图论教学实践，从图论本原思想入手，提出了图论课堂教学改革的措施。同时对图论学科考核方式、培养计划修订、教材编写等进行了探讨。

关键词 :图论，教学，信息与计算科学专业

Copyright © 2019 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

图论是组合数学的一个重要分支，以图为最基本的研究对象。图论中的图是一个抽象的数学结构，由代表事物的点和表示事物之间联系的边组合而成，其应用领域十分广阔，与许多学科有交叉，比如网络理论、博弈论、物理学、化学、信息论、电子计算机、控制论、运输网络、社会科学以及管理科学等诸多领域。特别是二十一世纪以来，图论成为解决新兴问题的重要工具。

目前，图论已经成为许多工科院校的必修或选修课程。图论起源于实际问题，所以图论教学应强调数学应用能力的培养，它解决问题的方法不同于数学分析、高等数学等课程，没有连续性和固定套路，非常灵活。它迫切需要教师改变填鸭式的理论证明、概念陈述等授课方式，在课堂上要重视图论本原思想的渗透，让学生领悟图论的思想，从而激发学生的学习兴趣，培养学生解决问题的能力。本文针对图论的课程特点，结合多年的教学实践，从以下几个方面对我校信息与计算科学专业的图论课程教学进行一些探讨。

2. 图论教学的现状

信息与计算科学专业是我校重要的品牌专业，它以信息领域为背景，是一门数学与信息金融相结合的交叉学科专业。我校信息与计算科学专业的学生具有良好的数学基础，同时该专业的许多课程，“运筹学”、“离散数学”、“数学建模”等课程都涉及到图论理论。

我校在信息与计算科学专业大四学生中开设图论选修课。由于图论课程中存在大量的概念，定理证明构造性强，抽象复杂。而大四的学生面临考研和就业的诸多压力，更多的精力和时间放在考研复习上，如何有效地激发学生的学习兴趣，引导学生积极思考，培养他们解决实际问题的能力，这让图论教师面临巨大的挑战。以往的图论教学主要存在如下问题：首先，图论课时只有32课时，图论课程自身存在大量概念和复杂的算法以及难以证明的定理，学生没有时间去课前预习和课后复习，在短时间内，很难理解课堂内容，从而感到图论课索然无味；其次，我校目前的课程设计与培养计划有诸多不科学。图论课程的教学目标是为培养学生图论算法分析、设计和应用能力，与之密切相关的课程，“程序设计”“算法分析”以及“数学建模”应该与图论课程同步开设。而我们的学生大三之前就学完了“离散数学”“运筹学”等课程，里面涉及到部分浅显的图论知识，学生会有眼高手低的现象。再说，图论课程考核方式单一，仍然是以传统的笔试为标准，试题的类型基本上是书中例题和习题的翻版，考试的结果体现不了学生解决实际问题的能力。最后，目前的图论教材有的内容过于理论化，内容体系复杂，对我校信息与计算课专业不太合适，有的内容过于简单，与前续课程有诸多重复。

由此，笔者在图论教学中一直在思考以下几个问题：如何在学时紧缺情况下高效完成图论基本理论课教学，让学生把握好图论的基本思想和解题技巧？如何教会学生用图论方法建立数学模型解决实际问题？如何设计新颖的实践教学形式让学生主动积极地学习？

3. 图论教学的探索与改革

基于图论教学的现状和我校信息与计算科学专业的培养计划，我们提出一些改革措施。

3.1. 设计好教学内容

在图论的第一节课时，我们可以介绍图论的发展史，图论专家的故事以及图论的基本思想，让学生对图论课程有个全面清晰的认识。在具体的教学过程中，我们凝练出如下几个策略。

首先，深挖理论的实际背景。

在讲授基本理论时，要展示基本概念的来龙去脉，激发学生的兴趣，提高学习效率。比如，在介绍树图时，我们可以画一张小说《红楼梦》的家谱图，梳理荣国府中的主要人物关系，将每个人用一个顶点来表示，父子间连一条边，从而引出树的定义。讲授平面图时，我们引入印刷电路板设计问题，讲授图的着色时，引入化学品储藏问题。

其次，注重学科间的思想渗透。

信息与计算科学专业的学生已有概率论、模糊数学及计算机理论基础，我们在课堂上将所学图论知识渗透到其他学科中，使学生掌握图论中常用的基础理论知识，并且能够灵活运用，从而在未来的工作中能够独立地分析和解决各类实际问题。

例如，将树形图应用到概率论中，在树的各顶点上标明各相关事件，枝上为各事件相应的概率，这样就构成了一株概率树。利用概率树的方法讨论概率中的乘法公式和全概率公式，简洁明了，浅显易懂。将图论的最大树算法与模糊数学的聚类分析结合，讨论植被的区划，分析地质灾害的分区，某地区农产品的分区，汛期的划分，船舶分段装备等等。讲最短路径算法的时候，就讲解其思想方法在编程方面的应用。另外，了解班级同学考研的方向，将图论的理论渗透到所属学科，激发学生学习图论的激情。

最后，讲授图论的基本思想。图论解题的具体方法是灵活的，离散的，在教学的过程中要有意识地训练学生的证明思想。图论中常用的基本思想有：归纳法思想，反证(归谬)法思想，极图思想，图变换思想，构造或算法思想 [1] 。有时它们需要结合使用。其中归纳和反证法是最普遍的两种方法。

例1 ( [2] ) 设G为 $\Delta \ge k$ 的树，则G至少有k个顶点度为1。

证明：反证法：假设G中度为1的顶点个数s小于k，则

$2\epsilon \left(G\right)={\displaystyle \underset{v\in V\left(G\right)}{\sum }d\left(v\right)\ge 2\left[v\left(G\right)-\left(s+1\right)\right]+k}+s=2v\left(G\right)-s+k-2\ge 2v\left(G\right)-1$

其中 $\epsilon \left(G\right),v\left(G\right)$ 分别表示图G的边数和顶点数。而又因为图G为树，所以 $\epsilon \left(G\right)=v\left(G\right)-1$ ，综合两式可以得到 $2v\left(G\right)-2\ge 2v\left(G\right)-1$ ，显然矛盾。

有时会将几种思想结合使用，比如极图思想和反证法综合运用。

例2 ( [2] ) 证明：若G是简单图且 $\sigma \ge k$ ，则G有一条长为k的路。其中σ为G的最小度。

证明：若P为G中的一条最长路，它的长l小于k，设P为 $v_1{v}_2{v}_3\cdots v_l{v}_{l+1}$ ，由假定 $d_G\left(v_l\right)\ge \sigma \ge k>l$ ，从而在P中存在另外一个顶点 $v_0$ 与 $v_{\text{1}}$ 邻接，于是 $v_0{v}_1{v}_2{v}_3\cdots v_l{v}_{l+1}$ 是G中比P更长的路，与P为G中的一条最长路矛盾，故 $l\ge k$ 。我们可以在P中取一段长为k的路，故G有一条长为k的路。

通过探究图论的基本思想，在教学中应有效挖掘图论中潜在的思维模式，培养学生运用图的基本理论思考和解决实际问题的能力，全方位提高学生的综合素质。

3.2. 调整培养计划

图论理论课时少，短时间内不好安排实验课时。基于这种现状，我们可以将信息和计算科学专业的培养计划好好梳理，建立课程群，比如，图论与运筹学、离散数学、Matlab，算法设计构建一个系统的课程群，学生通过前期课程的学习掌握了基本的算法思想，建议图论课程与Matlab课程同步开设，图论课程在课程群中利用其算法丰富、应用问题多而广的特点，给学生提供算法分析与设计的实践机会。

3.3. 改革考核方式

目前的考核方式还是平时课堂表现30%，期末理论考试70%的方式，体现不了图论课程的特色，图论来源于实际问题，应该对学生的应用能力有所考核 [3] 。笔者尝试平时以大论文的方式给学生留大作业，四人一个小组，分工合作，鼓励他们学会查找文献，将实际问题转化为图论模型，并用图论算法求解，通过Matlab编程，最终解决所给问题。并将评分记录作为平时成绩的依据。同时鼓励学生参加创新创业竞赛，诸如挑战杯、电子大赛、软件设计大赛等丰富的科技活动，凡是运用图论相关的方法选题的，都会获得平时分。以此来提高学生学习兴趣，培养他们的知识转化能力。期末考试不再使用闭卷考试形式，而是采用开卷考试，部分理论题，部分开放性的题。理论题主要考察学生对图论思想的把握，开放题主要考察学生课外拓展和主动学习的情况。

4. 编写新的教材

以前的教材存在大量的概念和理论证明，缺少应用案例，知识陈旧，与信息时代脱钩，学生学起来晦涩，索然无味 [4] 。所以图论课程的教材建设迫在眉睫。新编教材首先应该推出图论学科前沿课题，结合互联网背景，大数据背景，生物信息背景等相关的图论知识，激发学生的求知欲；其次，除图的基本理论外，增加图论与其他数学学科，比如模糊数学，数据结构，信息论以及数值分析的交叉及相互渗透，将图论知识渗透到在其他更多应用领域；最后，弱化证明，重点讲解证明思想和算法思想。重点讲图论算法的编程实现 [5] 。

5. 总结

通过图论教学的改革和探索，学生的积极性明显提高，今后继续结合图论学科特点和学术前沿，致力改革。培养学生观察问题，分析问题和解决问题的能力。

致谢

感谢各位匿名评审宝贵的建议，使得论文得以完善，同时也感谢所有编辑高效的工作。

基金项目

本研究由江苏省高校“青蓝工程”项目资助。

文章引用

华洪波. 信息与计算科学专业图论教学探讨
Discussion on Graph Theory Teaching in Information and Computing Science[J]. 教育进展, 2019, 09(05): 540-543. https://doi.org/10.12677/AE.2019.95089

参考文献