计算机专业生图课程的

摘 要 ：本文根据计算机专业硕士研究生的具体情况结合图论课程自身的特点,以作者多年讲授这门课程的经验,立足于同学们以后的学习和工作,对图论课程的教学提出了一些改革的建议.

关 键 词 ：图论；图论及其应用；计算机专业；研究生

中图分类号：G643 文献标志码：A 文章编号：1674-9324（2013）18-0197-02

目前在绝大多数的高校,都对计算机专业的研究生开设有《图论》或《图论及其应用》的课程.由于是非数学专业的学生,课程的学时较少,根据我们的调查,学时多在32～48学时之间.本文根据作者多年给计算机专业的研究生讲授图论课的教学经验,结合学生的具体情况以及图论课程自身的特点,提出了在教学中的一些改革思路.

一、图论中的定理及其证明的教学问题[1]

由于图论课程中的定理、结论特别多,证明方法千差万别,有些证明既难又长.这给老师的教学带来一定的困难,也使学生学习难度增大、变得枯燥乏味.以往我们在授课中沿用其它数学课程的教学方式,只要教学大纲里有的内容,几乎对所有的定理都给予证明.但通过多次的教学实践,我们发现效果并不理想,主要表现在同学们学习图论课时把绝大多数的精力花在定理的证明上,因而觉得这门课很枯燥,还有一部分同学为此产生了畏难情绪.通过与学生及其导师的交流,结合图论课程的特点,我们认识到所教学生是非数学专业的学生、加之学时又有限（成都信息工程学院为计算机专业研究生所开设的图论课程,为40个学时）,对理论证明方面的要求不必太高,他们更感兴趣的是图论的基本概念、基本理论、重要的结论以及应用.因此,在以后的教学中采取少讲或不讲一些不重要的定理及其结论,对不重要的定理均不予证明,而对一些虽然重要,但证明太难或太冗长的定理证明也不讲,只是把结论告诉大家.例如在平面图的开始部分,重点讲解“Euler公式,K5与K3,3是不可平面的”这些定理的内容及证明.之所以这样是因为这些结论的内容很重要,在证明“K5与K3,3是不可平面的”要用到Euler定理,而在介绍Kuratowski定理时又要用到“K5与K3,3是不可平面的”这些结论.这三个结论的证明有十分简洁的方法,如对Euler定理的证明我们选择的是对面数用归纳法的证明方法,[2]这种方法在图论的证明中很具有代表性,其证明方法也很容易理解.而对其它众多的结论我们只是有选择地说明其意义,而不一一地加以证明.在讲匹配理论时,我们只讲Tutte定理,[3,4]而不讲定理的证明,此定理虽然重要,但其证明过于繁复和冗长.对Kuratowski定理,我们也只介绍定理,并通过例题帮助学生加深对此定理的理解,对定理不加以证明.这样一来,学生的学习负担减轻了,学起来也不会太抽象,老师也有更多的时间传授学生们感兴趣的问题,如在平面图中的平面性算法等.

二、关于概念名称不统一的问题

近几年出版的图论教材和图书比较多,但有一个共同的问题就是概念的名称不统一,不同的书对同样的概念使用不同的名称.如：偶图[2]、二部图[3]、二分图[4]说的都是同一个概念,又如匹配[2]、对集[5]也是相同的概念,像这样的例子可以举很多.这给老师的教学和学生的学习带来了一定的困难.因此,我们在教学中给出它的英文名称,如偶图、二部图、二分图的英文都是bipartite graph,而匹配和对集的英文名称是matching.在讲述这些概念时首先讲清楚它的意思,并画图加以说明,同时将它们的英文名称告诉大家,最后给学生介绍用得比较多的中文名称.在学生掌握了这些概念的意思后,对不同的中文翻译就可以较容易理解了.这样在以后的学习和工作中,若遇到这个概念,无论是中文的哪个名称还是英文的理解起来都比较容易.特别是在阅读参考书及参考文献时,对学过的概念,若用不同的中文名称,也能很快的理解.而在教学过程中,有些学生反映,一些概念的英文名称更容易理解和记忆.

三、突出重点,避免重复

虽然计算机专业的研究生来自于不同的学校和专业,但是许多学生在读本科时已经学习过《离散数学》、《数据结构》等课程,这些课程会讲授一些图论的知识,有的会涉及到图论课程中的内容.因此在第一次上课时,我们首先向学生了解以前学习图论知识的情况,在教学中突出重点,避免重复.例如,最短道路问题在《离散数学》、《数据结构》、《运筹学》等课程均做过介绍,大家都知道求解最短道路的Dijkstra算法,因此在讲课时主要讲解最短道路的意思,最短道路问题在现实中的应用,最后再多介绍几种求最短道路的算法.在阐明最短道路的意思后,列举一些例题,说明最短道路的应用,如Cisco路由器中的IOS软件就要用到求最短道路的算法,这让同学们觉得,他们现在学习的知识不仅仅是纯理论的东西,而是与他们生活和工作是紧密联系在一起的.在近几年的教学中,我们发现虽然许多学生在以前的学习中接触过求最短道路的Dijkstra算法,但他们对Dijkstra算法具体是怎样实现的并不清楚,因此近几年我们在讲授Dijkstra算法时的另一个工作是讲解算法的思想及具体的实施过程.最后再简单介绍求最短道路的Warshall-Floyd算法、Dantzig算法、最优化原则,说明它们能解决的问题,运算复杂度.在最短道路这一部分,我们的重点是向学生阐明它的应用.因为大家都学过最短道路的Dijkstra算法,而对算法的内容我们不做详细地讲解.这样既节约了时间,又可以介绍更多大家感兴趣的知识.

四、理论与应用相结合

对大多数人而言,纯理论问题总是比较抽象,在教学中,尽量做到理论与应用相结合,而计算机专业的学生对应用更感兴趣.

在讲完树的相关理论后,我们立即讲最小生成树.首先说明最小生成树是有解的,在有解的情况下,如何求解——用Kruskal算法.再介绍最小生成树的应用,最后讲一讲求解最小生成树的其它算法.

在讲授完Euler图的相关理论后,接着就介绍中国邮路问题（Chinese Postman Problem）,明确告诉学生中国邮路问题是有解的.所有的教材对此问题的具体求解方法没有做详细的介绍,加之学时有限,我们也不讲其详细的求解方法,只是介绍求解的大概思路.重点是介绍它的应用.最后将相关文献告诉学生,以便学生在以后的工作和学习中遇到此问题便于查找和求解.最后再将中国邮路（Chinese Postman Problem）的最新研究情况——多邮递员中国邮路问题（k-Postman Chinese Postman Problem）给大家做个简介,同样讲清楚它的意思,将相关文献告诉学生.

在讲授完Hamilton图的理论后,说明旅行售货员问题——求最优的Hamilton圈.告诉学生：目前还没有求解旅行售货员问题的有效算法,但有方法获得相当好（不一定最优）的解,最后再告诉学生相关参考文献.

我们发现这样的教学方式学生学习起来比较容易,同学们也比较感兴趣,对他们进一步的学习和工作帮助比较大.如在教学中我们就遇见这样的情况,有个同学在学图论课的同时,在课题中遇见了求解“旅行售货员问题”.在学习了图论课程后,对此问题有个清楚的认识,而且很快可以提出解决方案.他明确告诉课题组的同事：目前还没有求解旅行售货员问题的有效算法,但有算法获得相当好（不一定最优）的解,当节点数目很有限时,可以用穷举的方法得到最优解.

由于我们针对学生的特点,有选择地传授图论的相关知识,加之与学生及其导师及时沟通,改进我们的教学内容,使得这门课受到较多学生的欢迎,选修这门课程的同学也逐年增多.看到这样的结果,我们也很有成就感.

图论是一门很有趣、内容很多,又有很广现实应用的一门课程.对计算机专业的研究生来说,如果这门课程讲授得当,不仅可以丰富同学们的数学知识,还可以对学生以后的学习和工作提供较大的帮助.因此在教学中不断地改革和创新,是很有必要的.