图论课程的教学感悟

2014-03-31隋丽丽张守成韩元良

华北科技学院学报 2014年11期

隋丽丽，张守成，韩元良，于健

(华北科技学院基础部，北京东燕郊 101601)

0 背景

我校开设这门课程已有7年时间，是一门比较有历史的理工专业的公共选修课。图论方法一直是科学家追求的目标之一。正如每个数学家必须精通微积分一样，每个有作为的计算机科学技术工作者必须要有图论方面的较高造诣。图论的应用领域及其广泛，凡是涉及排列组合优化问题的，都可以用图论中的知识去解决。因此有人说图论的重要性不论怎样估计，也不会过分。图论已经是国内很多高校理工科专业必修的一门课程，用来提高学生分析问题的能力，并为解决专业问题提供一种工具。

1 教学中的方式方法

1.1 图论学习的必要性

图论在计算机中的应用已广为人知，除此之外，在实际的生活生产中，也有大量问题可以用图论的知识和方法来解决，高校里面的很多专业都要用到图论的方法。例如，在工程管理中，为完成某项任务，各工序之间怎样衔接，才能使得生产任务完成得既快又好;一个地区的通讯网络要如何架设，交通网络要如何布局?在经济管理中，一个旅行团要参观多个景点，应该如何安排路线?物质的运输要如何安排才能使得运输成本最低?在计算机技术方面，图论中的各种算法是程序设计的基础和原理。为了让施工人员能够对施工计划的时间，先后顺序一目了然，我们可以根据施工计划绘制相应的双代号网络图，图论的研究对象是离散型的变量，在现实生活生产中，学生感受的离散型变量比微积分中的连续型变量更多，更普遍。

例如，价格，收费，工期(按天数)等，那么相应地，对离散型变量的体会也更加深刻，学习起来更加自然亲切。图论的研究工具直观形象，一个由点和边组成的图表示现实世界的各种关系，简单明了，学生易于理解。

《图论及其应用》是全院工程类各专业的一门选修课。此门课程的教学目的是使学生掌握图论中常用的基础理论知识，并掌握以此为基础的常用的图论算法及其应用，使学生能够灵活运用常见的计算机基本方法，从而在今后的工作中能够具有独立地分析和解决各类实际问题的能力。

1.2 结合教学经验，应用案例教学

案例教学首创于哈佛大学商学院，在经贸、管理、法学等学科领域的相关专业得到应用并取得显著成效。目前理工科专业还较少运用案例教学方法，主要困难是:理工科专业的案例教学实践较晚，可供借鉴的成功经验较少;难以获得兼顾真实性和教学时限等要求的教学案例;理工科领域体系庞大，专业繁多，不同专业之间案例共享性较差。作为我校工工程类专业的一门选修课——图论及其应用，因其专业背景广，应用多面，而存在众多成功的应用案例，若将这些成功案例用于实践教学环节，《图论及其应用》课程将在培养高素质的应用型人才方面发挥更大的作用。

本校开设的图论及其应用课程要求学生掌握的原理相对来说也比较浅显，只需要学生了解这个有力工具，为今后的继续学习提供一种可参考的工具。譬如最小生成树原理，如果按照数学专业学生的教学要求，原理内容，证明方法，证明过程，以及相关算法都需详细讲解，但作为选修课，在讲解过程中，只需联系工程实际问题，讲解其应用方向，这样的内容浅显易懂，不至于让学生望而生畏。教学过程中，为了激发学生的兴趣和动力，应该结合现实生活和专业实际，从案例分析引入基本概念和原理，在简明扼要，直观形象地讲解概念和原理以后，再回到案例分析，解决实际问题。一般引入的案例追求普遍性，典型性，生活化，而应用的案例则偏向专业性，生产化，挑战性。

如在第一堂课就可以简单介绍图论中很典型的有趣问题，像(立陶宛)哥尼斯堡城七桥问题，也包括爱尔兰数学家哈密顿(Halmiton)提出的“周游世界”的游戏，一笔画问题，最短邮路问题等，介绍这些案例的背景，内容，保留结论，极大地激发学生的求知探索欲，向学生传输图论源于自然，也源于简单，消除他们的畏难情绪［1－4］。在后续的教学中，可在讲解图的连通性和连通度内容时，和同学一起解决绪论中提出的问题;在讲解匹配章节时，就可引入像人员安排问题，货郎送货等问题;在讲解连通度时，可介绍投递员问题;讲染色问题时，可提出地图染色至少需要几种颜料的问题［5－8］。这些实际有趣的问题会让学生真正的参与到教学活动中，主动思考得到的答案更深刻，从而收获更多，提高了教学质量。

1.3 与专业的结合

图论的应用几乎渗透到了每个理工专业，因此教师在讲课中注意和学生专业的结合，会使选修这门课的相关专业学生有主人翁意识，增强学习欲望。目前图论知识的应用比比皆是。比如在讲解图的顶点和边的时候，就可以介绍利用这一节的内容去描述岩石的裂隙缝网，刻画其特征，这在安全、采矿以及土木建筑专业都是非常关键的一个处理片段;在讲最短路径算法的时候，就可以讲解其思想方法在编程方面的应用，计算机、管理等专业的同学都会受益匪浅。