《图论及其应用》优质课程建设的探索与实践

张清华　陈六新

摘要：针对我校研究生公共基础课《图论及其应用》优质课程建设的实际情况以及教学中存在的问题，该文总结了我们在《图论及其应用》课程的教学改革、教材建设、师资队伍建设、网站建设等方面建设研究生优质核心课程的经验。通过近几年的建设，目前课程在教学目标、教学内容、教学手段和考核评价等方面具有一定的优势和特色。

关键词：课程建设；图论；教学改革；教学内容

1概述

大量事物以及事物之间的关系，常可用图形来描述，如物质结构、通信网络、交通规划、工作调配、算法流程等都可以用点和线连起来所组成的图形来模拟。图论是数学的一个重要分支，是研究自然科学、工程技术、社会科学等问题的一个重要的现代数学工具。国内外有许多高等院校已为数学、计算机科学、通信工程、控制与管理科学等学科的研究生和信息与计算科学专业的本科生开设了图论课程。我校通信类、计算机类、自动化类、经管类、物理类、系统科学类等学科的研究生培养方案把《图论及其应用》作为学位课来开设。教学规模逐年扩大，每年有近600人愿意修这门课程，而大约有400人成功选课，受益面非常广泛。

然而，随着我校研究生规模扩大，研究生教育教学改革得深化，在着力提升研究生教学质量的关键时期，迫切需要加强课程建设，特别是《图论及其应用》这门公共基础课程的建設，更新和优化教学内容，实现信息化教学，以致培养新世纪的IT创新人才。《图论及其应用》课程的开设正是为着这个目的，它对拓宽学生的知识面，优化学生的知识和能力结构具有极其重要的意义。

随着最近教育部《关于全面提高高等教育质量的若干意见》和重庆市教委《关于推进协同创新，全面提高高等教育质量的若干意见》的改革举措相继出台，很多高校在面临扩大研究生规模、深化研究生教育教学改革、提升研究生教育质量和培养研究生创新能力的关键时期，迫切需要加强公共基础课的教学质量，夯实工科学生数学基础，特别是急需加强研究生课程建设，尤其是量大面广的公共基础课程的建设。为此，学校高度

重视该课程的建设和教学团队的发展，2011年学校将《图论及其应用》课程列为重庆邮电大学研究生教育创新计划重点项目来加以建设，目前该课程在教学内容体系、教学大纲、网络资源、教材建设等方面取得突出成果，课程教学团队年龄、学历、职称结构显著改善，该课程已初现优质课程的特征。

2《图论及其应用》课程当前存在的主要问题

就目前来讲，我校《图论及其应用》课程教学虽然取得了长足的进步，基本能够适应学生对课程基本知识的需求。但是，在课程建设、教材建设、信息化建设、师资队伍建设等方面还需要进一步完善，特别是作为以信息学科为特色的教学研究型大学的研究生教育的一门公共基础课，主要存在如下问题：

2.1教学内容需要进一步凸显工科专业特色

当前，《图论及其应用》课程教学内容还是有些重理论、重推导，对图论中的原理在信息学科中的应用渗透不够，应用背景挖掘不够。图论的概念、公式和定理比较多，定理的证明通常相对较难，在一定程度上造成教学枯燥难懂。因此，在教学中往往忽略了图论与多学科的横向交叉联系和实际应用背景，使得学生难以灵活运用图论模型来解决各种实际问题，特别是在授课过程中如何将图论算法的分析、复杂度分析、最大流算法、最短路径算法和网络优化等方面与电子信息学科的专业背景有机结合方面还有些欠缺，究其原因在于两个方面，第一很多教材对应用内容涉及太少，第二授课教师的学科背景知识本身较为缺乏。因此，加强教材建设和扩充教师相关学科背景知识是我们需要解决的问题。

2.2教学资源需要进一步完善

随着学校推出的一系列提高研究生教学质量举措，《图论及其应用》课程被列为校研究生创新计划重点项目进行建设，教学资源得到有效补充。虽然我们开发创建了图论课程教学网站，并有基本的教学内容，但是如何充分发挥课程网站的功能，急需补充优质课程要求的更高层次的教学资源：习题库、教学录像、试题库、实践讨论题库、考评系统等，需要进一步补充相应的教学资源。当前，课程网站的教学互动模块需要开发利用，实现更加有效的网络答疑、师生互动；同时需要共享课程资源、课程录像、多媒体教学课件等；开发系统实现远程访问与教学探讨，扩大课程的影响力，发挥课程辐射示范作用。因此，进一步完善教学资源，实现优质课程资源共享是需要重点解决的问题之一。

2.3教学研究和教学改革需要进一步深入

图论是一门覆盖内容非常广泛的交叉学科，图论的产生和发展得益于各学科的交叉和渗透。因此，图论提供的理论和方法应用于不同学科，各学科的发展又为图论提供新的概念、新的研究课题和新的研究方法。目前来讲，我们的教学还是主要围绕图论的基本数学理论，在教学内容上还需要进一步与通信工程、计算机科学与技术、软件工程、电子信息、系统科学、管理科学等学科进行交叉和渗透，追溯教学内容的根源，然后反哺不同学科的专业知识，提高学生积极性，力争打通图论知识与学生后继专业知识的通道，缩短基础知识与专业知识的距离。因此，需要从教学内容、教学方法、教学手段、考核方式等方面开展教学研究，加快教学改革步伐，探索适合信息类工科研究生的图论教学新模式。

3《图论及其应用》课程建设探索与实践

针对目前《图论及其应用》课程建设存在的一些典型问题，我们从教学目标、教学内容、教学方式和考试改革等方面进行探索和改革。

3.1重新拟定教学目标

通过本课程学习，要求学生掌握图论的基本理论及推理方法，为通信网络、电路设计、逻辑设计、人工智能、形式语言、计算机制图、程序涉及、信息安全以及信息检索等知识的学习打下坚实的理论基础。课程要求研究生掌握图论的基本理论和基本方法，工科研究生需要掌握：图的相关概念、欧拉图、汉密尔顿图、最短路径、树及其最优二叉树、平面图与着色、二部图与匹配、网络流与网络优化等基本内容，并用这些理论与方法解决一些科学研究中的实际问题，理解如何用图论知识解决现代信息科学和现代通信系统中实际问题的基本原理。学生通过本课程的学习，培养优良的数学素养、提升科学研究能力，提高科学计算能力，并能运用学到的知识和方法解决一些科研实际问题，为电子信息类研究生在后续的专业课程学习和科研工作奠定扎实的理论基础。

3.2优化教学内容体系与结构

本课程根据学校工科类研究生各专业对图论的要求，选择了较为系统的教学内容，突出图论的基本理论与方法，培养学生对离散对象的抽象思维与解决实际问题的能力，并为学习后继相关专业课程及从事科学研究和工程實践奠定理论基础。主要内容包括：

图论学习的预备知识：主要介绍图论学习中需要用到的等价关系、偏序关系、算法与复杂度分析等。

图的基本概念：主要介绍图论涉及的基本概念和基本理论，如同构、握手定理、简单图、图的矩阵表示、图的连通性等。

欧拉图与和汉密尔顿图：主要介绍欧拉图的定义及其判定，汉密尔顿图的定义及其判定，欧拉图和汉密尔顿图的应用。

树及其最短路径问题：主要介绍树的相关概念、二叉树、最优二叉树、有向图的最短路径算法等。

网络优化与Petri网：主要介绍网络流与截集，最大流及其算法，最小费用问题等。

独立集和支配集：主要介绍独立集与支配集的相关概念、相互关系，匹配、最大匹配、最优匹配和匈牙利算法等。

平面图与着色：主要介绍平面图、极大平面图和极小非平面图、对偶图及其着色等。

3.3教学方式和考核评价体系改革

《图论及其应用》作为工科研究生（不管学术型还是专业型）的公共基础课，我们当前主要采用教师为主导的教学模式，尝试采用分类教学，即让不同学科的学生组成不同的教学班（如分为电子信息类、计算机科学与软件工程类等），对部分教学内容适当调整。教师主要用我们自己制作的多媒体课件与板书相结合的教学方式，既体现了现代教学手段，也保留传统的板书效果。同时，采用启发式教学方法，让学生撰写图论相关的小论文，作为平时成绩，占30%；并利用我们建立的图论课程网站，公布相应的课程信息、考试大纲等。总体而言，《图论及其应用》课程经过十余年的建设，已形成了一套较为合理的教学方法和手段，主要有：

1）结合工科学生情况，编写出版《图论及其应用》教材，制作了一套对应的教学课件，将多媒体教学手段与传统教学手段结合，提高教学效率，增强教学效果。

2）引入一些应用实例，增强课程的实用性、趣味性，提高了学生的学习兴趣。

3）强调数学建模思想、加强数学与图论知识的融合，提高学生的问题分析能力。

4）分类教学，引导学生将理论知识与自己的专业研究相结合。

5）鼓励学生从接受学习到探究学习的转变。旨在培养研究生的创新意识、应用知识的迁移能力、对待事实证据的科学态度、对科学探究的理解、探究所需要的多种知识。

6）采用堂上讨论、写小论文等多种形式对课程学习进行考，核考查学生对基本理论的掌握情况以及分析解决问题的实际应用能力等。

本课程教师采用我们团队根据多年教学经验并结合学校学生实际情况编写出版的教材，驾驭课堂能力强，教学经验丰富，高质量完成课程教学任务，受到师生好评。

4目前形成的优势和特色

通过5年左右校级研究生优质课程建设和市级研究生优质课程的建设，目前《图论及其应用》课程已初具特色。

1）本课程是全校电子信息类研究生公共基础课（学位课），学生受益面广。我校通信类、计算机科学类、软件工程类、系统科学类等学科的研究生培养方案把《图论及其应用》作为公共基础课（学位课）来开设。教学规模逐年扩大，每年有近500人学生选修这门课程，学生受益面非常广泛。

2）学校高度重视本课程建设，教学资源相对完善。随着学生选课人数增加，学校在201 1年将《图论及其应用》课程作为重邮究生教育创新计划重点项目进行建设，成效显著，拥有相对完善的教学资源：重新制定的教学大纲、考试大纲；在清华大学出版社出版的《图论及其应用》研究生教材（2013）；自编配套的PPT课件；开发的课程网站（网址http：//slxy.cqupt.edu.cn/tulurd）。当前教学团队在分类教学、创设情境式、探究式教学等方面进行了教学改革，获得重庆市研究生教研项目支持（2012年、2015年各一项），具有一定的研究基础。

3）本课程有高水平的师资队伍和良好的教学条件。本课程教学团队的8人中，任课教师6人，学校教学管理和网站建设与维护人员2人，职称结构和学历结构非常好，集中在35-45岁阶段的教学和科研骨干，授课教师高级职称所占比例是100%，具有海外访学经历人员有3人。另外1名刚毕业的博士作为后备教师，1名中级职称老师负责网站建设与维护；团队教师具有丰富的教学经验和良好学科知识背景，教学团队凝聚力强。

4）本课程成为实用性极强的重要的数学工具。《图论及其应用》是通信网络、电子技术、计算机科学、系统工程与控制、网络理论、社会科学及经济管理等众多学科中起着不可替代作用的数学工具。通过本门课程的学习，使学生不仅能够掌握现代计算的一些基本理论知识，而且还能了解信息学科发展的前沿动态（如通信网络路由选择、网络规划和优化资源方法及应用等），提高学生的科研创新能力。

5结束语

《图论及其应用》作为工科类研究生后续课程如《算法分析与设计》、《运筹与控制》、《信号分析》、《人工智能》、《网络优化》等课程的先修公共基础课程，其重要性也是不言而喻的，很多研究生导师要求学生必须选修这门课程。针对该课程中概念比较多、论证方法独特而又千变万化的特征，再加上课时较少（48学时），而且选修的学生遍及全校几乎所有的工科专业，对这门公共基础课加以教学改革是我校研究生教学改革的重要方向。论文以建设重庆市优质课程为主线，介绍了一些相关作法，期待和大家共勉。