信息与计算科学专业图论教学改革研究

孔翔宇　王贞　孙滢

【摘要】本文针对图论的教学现状，结合信息专业的特点，提出了建立课程群，讲义编写等教学改革措施。同时也提出了课堂教学和实践教学的教学方法。

【关键词】图论 教学改革 教学方法

【基金项目】宁夏回族自治区高等学校教育教学改革项目：《神经网络计算》专题研究型教学模式探索与实践（宁教高[2012]348号）。

【中图分类号】G633.67 【文献标识码】A 【文章编号】2095-3089（2014）01-0140-01

图论是组合数学和离散数学的重要组成部分。图论起源于著名的哥尼斯堡七桥问题[1-2]。它以图为研究对象，把研究的事物抽象成若干点，将事物间存在的关系用线来表示，如果两事物间存在关系，就用一条边将它们连接起来，经过上述方法所做的图形就是图论中的图。自然科学和社会科学中诸多领域的关系都可以用图论中的图来表示，对于这些问题建立相应模型之后再去研究往往能够得到良好的结果，故对于图论中图的研究就显得特别重要，得到了众多专家和学者的关注。

一、图论课程的教学现状

由于图论在许多领域有着重要的应用[3-4]，许多大学都把图论作为一门专业课单独开设，作为数学、计算机、电子、管理等专业高年级本科生和研究生的必修或选修课。图论在教学过程中具有如下特点：

1.图论中基本概念、定理非常多，概念不易理解，定理证明又特别难，这就在一定程度上使教学枯燥难懂。

2.图论研究的许多问题都具有实际应用背景，但往往很难转化成图论模型，不容易求解，从而造成了学生对图论学习很有兴趣，但因为不能求解而产生厌学心理。

3.图论课程涉及的算法非常多，对于每个问题几乎都有不同的算法。例如最小生成树的求法就有克鲁斯克尔算法，管梅谷的破圈法、Prim算法等十几种算法，如果要求学生编程求解实际问题，那么对学生的算法分析能力以及程序设计能力就提出了很高的要求。

通过在本校讲授该课程发现学生并不满足于图论算法的证明和纸上求解，迫切需要掌握如何利用计算机来实现算法并求解实际问题。这就促使我们探讨图论课程的教学改革。

二、图论课程的教学改革

根据信息与计算科学专业人才培养要求以及图论课程的教学现状，提出如下教学改革措施。

1.建立课程群

任何一门课程都不是孤立的，总是存在一门或者若干门课程与它相关，因此很多高校通过建设课程群来构建完整的知识体系，优化课程安排，在较少的人力物力下达到最高的教学目标。图论课程的教学目标是培养学生算法分析、设计和实际问题的应用能力，而“程序设计”、“数据结构”、“算法分析设计”等课程也是培养学生的算法分析、设计能力，这和图论课程的教学目标是相同的。所以，可以将这些课组合在一起建立课程群。通过课程学习，学生不但掌握了丰富的图论知识，算法分析与设计能力也将会得到进一步巩固和加强。

2.做好教材建设，编写适合教学目标的图论讲义、教材

教材建设是任何一门课程建设的重中之重，教材主要包括教学中使用的教材或讲义、辅导教材等。为适应新的更高的教学目标编写课程讲义。具体教材改革如下：

（1）将目前各大高校普遍使用的图论教材中50%左右的定理证明略去，不再详细证明，仅对一些经典证明进行详细阐述，重点分析图论课程所涉及的算法思想。

（2）在课程课时有限的条件下，如何发掘学生的自学能力是教师要思考的问题。这就要求教师为学生提供实例较多的参考书籍。

（3）对同一问题采用不同的算法，分析所得结果的差异。重点讨论为什么会产生这种差异。

三、图论课程的教学方法

一种新的课程教学思路必须有一套新颖的、行之有效的教学方法与之配套，所以必须重视探索恰到好处的教学方法。

1.课堂教学

课堂教学是教学过程的重中之重，在教学中可以采取如下方法加强课堂教学效果：

（1）上好圖论课程的第一次课。第一次课的教学效果往往会决定学生是否会对这门课程有兴趣，是否愿意认真学习这门课。对图论课程的第一次课，可以从一些有趣的实际问题入手，如哥尼斯堡七桥问题、中国旅行商问题、中国邮路问题、图的着色等。这些问题简单易懂，清晰明了，十分有趣。更主要的是，这些实际问题可以把图论中的主要研究内容串联在一起，从而让使学生对图论这门课程有直观的了解。

（2）加强课堂互动。图论的很多问题来源于现实世界的生产生活，在学生的校园学习生活中也能找到相应的例子。在课堂上，使学生成为课堂教学的主体，让学生在黑板上演示问题相应算法的求解步骤，这对学生理解算法思想和求解过程将起到重要作用。

（3）加强算法的分析对比实验。为了使学生对图论中的算法复杂度有直观认识，通常在分析完图论算法复杂度之后，对部分问题进行计算机仿真实验，通过反馈回来的算法运行时间来验证算法的复杂度。

2.实践教学

为了促进学生对图论的学习兴趣，要积极引导学生阅读论文和文献综述，为今后的专业发展夯实基础，在教学中要开展丰富的实践教学内容。这里讨论的实践教学不单指实验课。具体在实践教学中可以采取如下方法：

（1）在求解问题时，通过培养学生查阅文献的能力，指导学生阅读相关论文。

（2）图论中有许多至今仍没得到解决的问题或者是解决得不好的问题，国内外相关专家和学者对这些问题的研究一直没有中断，可以向学生介绍相关问题，一起探讨，培养学生产生浓厚的学习兴趣。

（3）在学习完一章或者一部分内容之后，可以对这些教学内容以小论文的形式提交作业，作为考试成绩的一部分。

四、结束语

通过对图论课程的一系列教学改革，提高了学生的学习热情，更好的实现了教学目标。如何更深层次的解决图论课程改革问题是进一步需要解决的问题。

参考文献：

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

[2]杜承铭. 本科应用型人才培养目标的选择、构建及实现[J]. 教育与职业，2006，（32）：20-22.

[3]张宪超，陈国良，万颖瑜. 网络最大流问题研究进展[J]. 计算机研究与发展，2003，40（9）：1281-1292.

[4]钱建国. 浅谈算法实例在图论教学中的作用[J]. 莆田学院学报，2004，11（3）：70-71.

作者简介：

孔翔宇（1982-），男，吉林榆树人，在读博士，讲师，主要研究方向最优化理论、智能算法、高等教育学。