《图论及其应用》课程建设探索
徐 俊 明
摘 要 本文叙述了图论的飞速发展和它的广泛应用, 在高等理工院校中开设《图论及其应用》课程对深化教学改革, 更新教学内容, 优化学生的知识结构, 培养跨世纪人才的必要性和重要性。同时结合作者开设此课程的多年教学实践, 介绍对该课程进行教材建设和在教学方法上的一些新的探索和尝试。
一、引 言
自然界和人类社会中的大量事物以及事
物之间的关系, 常可用图形来描述。例如, 物质结构、电气网络、城市规划、交通运输、信息传输、工作调配、事物关系等等都可以用点和线连起来所组成的图形来模拟。研究图的基本概念和性质, 图的理论及其应用是构成图论的主要内容。
任何一个包含了某种二元关系的系统都可以用图论的方法来分析, 而且它具有形象直观的特点。图论中应用的图形与几何上的图形不同, 每条边均可赋以权(这个“权”可取为一个正数值, 用来表示矩离、流量、费用等等) , 组
许多高等院校已为数学系、电子学系和计算机
科学系本科生开设了图论课程。我校计算机科学系就是其中之一。数学系王树禾教授授课多
[1]
年, 并专门编写出版了教材《图论及其算法》供计算机科学系使用。但在全校范围内开设这门课程供各专业本科生选修的高等院校, 在国内尚无先例, 在国外也不多见。国家教委目前还没有此类课程的教学大纲, 从1989年开始, 我校率先为全校本科生开设了《图论及其应用》选修课程。选修的学生热情很高, 兴趣很
浓, 选修学生人数最多一次达130人。在教学实践的基础上, 笔者编写了《图论及其应用》讲
成加权图, 用来研究系统特性, 进行决策分析, 义, 先后做了三次修改, 反映较好。中国图论研确定最优设计, 调整经济管理和试验方法等究会副理事长李乔教授在审阅讲义时高兴地等。给我校数学系、教务处和出版社写推荐信, 信总之, 图论是研究自然科学、工程技术、经济管理以及社会问题的一个重要的现代数学工具, 因而受到全世界数学界和其他科学界越来越广泛的重视, 从八十年代开始, 国内外有
徐俊明:中国科学技术大学数学系副教授
中这样评价《图论及其应用》讲义:“它系统论述了图论中各主要专题的基本理论和有代表性的多种应用, 对各专题的经典结果都力求给出最新的简单证明(有时给出多种证明) , 并着
用》选修课教材, 徐俊明同志的书稿是教学实
践的产物, 有水平、有特色, 完全能满足上述教学需要, 特向数学系、教务处和出版社的有关负责同志推荐尽快在科大出版社出版。”目前, 学校教务处和出版社已将此讲义正式列入出
意加强各专题间的贯通联系, 使读者感受到图论这个数学学科虽然年轻, 但一方面其内涵丰富多彩, 引人入胜, 具有理论深度; 另一方面又有非常广泛的多种多样的应用。另外, 作者从有向图出发来展开内容, 不同于美国、英国、加
拿大以及国内所有图论教材主要论述无向图, 版计划。本文将简要说明开设此课程的目的和而把有向图作为附加内容的处理方式, 这无疑意义, 并结合几年来的教学实践, 介绍在教学是一种有意义的尝试。科大目前正需要为数学和教材建设上的一些探索和体会。系高年级和面向全校高年级的《图论及其应
二、从图论爆炸性发展看开设此课程的意义
图论产生和发展历经了二百多年的历史, 历史作了详尽的回顾与研究。大体上可以划分为三个阶段。1936年以后是第三阶段。由于生产管理、
第一阶段是从1736年到十九世纪中叶。军事、交通运输、计算机和通讯网络等方面的这时的图论处于萌芽阶段, 多数问题是围绕着游戏产生的, 最具有代表性的工作是著名的瑞
. .
士数学家L . Eu ler 于1736年的K o n igsberg 七桥问题。他的那篇论文被公认为图论历史上第一篇论文。
第二阶段从十九世纪中叶到1936年。这个时期中图论问题大量出现, 如四色问题(1852年) 和H am ilton 问题(1856年) 。同时出现了以图为工具去解决其它领域中一些问题的成果。最有代表性的工作是K irchhoff (1847年) 和Cayley (1857年) 分别用树的概念去研
需要提出一系列问题, 特别是许多离散性问题的出现大大促进了图论的发展。进入七十年代以后, 特别是大型电子计算机的出现, 使大规模问题的求解成为可能, 图的理论及其在物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、社会科学及经济管理等几乎所有学科领域中各方面的应用研究都得到“爆炸性发展。”图论越来越受到全世界数学界和其它科学界的广泛重视。各种国际学术交流活动十分活跃。大型国际会议频频召开, 国际《图论杂志》也于1977年创刊。目前, 发表图论论文的专业杂志有十几份之多, 其论文数目每年呈指数型上升。图论以及应用的专著已多得无法统计。就其图论本身来讲, 现已发展成《代数图论》、《拓扑图论》、《随机图论》、《计数
究电网络方程组问题和有机化学的分子结构
问题。“图(Grap h ) ”这个词第一次出现是在1878年的英国《自然》杂志中。进入本世纪三十年代, 出现了一大批精彩的新理论和结果,
如M enger 定理(1927年) , Ku ratow sk i 定理图论》、《算法图论》、《无限图论》等多个分支多(1930年) 和R am sey 定理(1930年) 等等。这个学术派别[3]的现代数学学科。些理论和结果为图论作为一个数学分支奠定由于图论的重要性, 越来越多的高等院校
. .
了基础。1936年, 匈牙利数学家D . K o n ig 写已把它列为数学、计算机科学、电子学和科学出了第一篇图论论文到1936年第一本图论专管理等专业本科生的必修课和选修课。以考察著《有限图与无限图的理论》。至此, 图论作为数学的一个分支已基本形成。从1736年的第一篇图论论文到1936第一本图论专著, 整整
[2]
经历了二百年。《图论1736～1936》对这段
高校本科生的数学基础和综合应用能力为主
的美国大学生数学建模竞赛, 从1985年开赛以来共二十二个竞赛题中, 有1 4的问题须借助于图论这个数学工具才能解决。目前, 我国
高等院校理工科非数学专业所学的数学课程, 如《高等数学》、《线性代数》所授内容基本上都是二十世纪以前的数学内容, 对现代数学和现代数学方法基本上没有涉及。在这个迈向新世纪的年代, 我们面临加快现代化建设, 深化教学改革的任务。教学领域迫切需要加强课程建设, 引进当代科技发展的新成果, 更新和优化教学内容, 培养跨世纪的人才。《图论及其应用》课程的开设正是为着这个目的, 它对拓宽学生的知识面, 优化学生的知识和能力结构很有必要。
几年来的教学实践也说明了这一点, 不少学生对这门课所提供的新的数学概念、数学模型以及新的思想和方法惊叹不已。选修这门课
的学生分布在全校几乎每个系, 从低年级到高
年级, 从本科生到研究生, 真正成了一门跨学科、跨年级的选修课。许多学生表现出极大的热情, 收获很大。例如, 9012的于清娟同学, 9201的喻甫祥同学选修了这门课后, 在1994年全国大学生数学建模竞赛中利用图论方法解决《锁具装箱》问题均获一等奖。于清娟同学还获当年美国数学建模竞赛二等奖。由于她的出色成绩和坚实的数学基础, 1995年被聘为校数学建模集训队任教练, 并领队参加美国数学建模竞赛, 获特等奖。在1994年, 我校参加数学建模集训队的选手中, 70%以上同学选修过此门课。现在, 《图论及其应用》这门课程已作为该培训班的必修课程。
三、对教材建设的探索
目前流行的图论教材有好几十种。笔者认向图入手, 引进图的概念, 强调无向图是一类
为这些教材中有的内容过于理论化, 有的内容特殊的有向图——对称有向图。同时, 我们在已经陈旧, 有的内容过于简单, 均不适合于作叙述与边方向有关的概念和理论(例如, 路、为选修课的教材。既要考虑到我校学生数学基回、圈、直径和连通等) 时, 将图理解为有向图; 础较好, 求知欲望强烈, 勇于钻研的特点, 又要而在叙述与边方向无关的概念和理论(例如, 兼顾各学科学生选修的需要, 编写一本深度和树、平面图、匹配、染色等) 时, 将图理解为无向广度适中且具有我校特色的选修课教材很有图。几年来的教学实践说明, 这样做并不增加必要。笔者在多年开设这门课程的教学实践基难度, 反而觉得很自然和方便。比如, 在叙述图础上, 经多次修改, 形成《图论及其应用》教材。空间理论时就有这种感觉。主要在以下几个方面做了一些尝试和探索。在材料的选取上, 除安排一些经典结论和
应用外, 重点是吸收二十世纪七十年代以后的
1. 突出现代特色
最新研究方法、研究成果和应用。即使是经典
图论做为现代数学的一个分支, 应突出它结论, 我们给出的证明都是最新的简单证明。的现代特色。从图论的发展历史来看, 无向图在前, 有向图在后。图论中许多重要概念和理论结果虽然产生于无向图, 但现在许多重要结果已被推广到有向图。传统教材(包括英、美、加拿大等国) 在叙述图论概念和结果时, 多数只叙述无向图, 而将有向图作为附加内容另辟成章。这样不但分离了有向图与无向图之间的联系, 而且会显得内容陈旧, 有时也会带来诸多不便。依照图论本质和发展趋势, 我们从有
例如, M enger 定理产生于1927年, 证明却是1984年的; Ku ratow sk i 定理产生于1930年, 证明却是1989年的。这样把学生推向科研和应用的前沿, 置身于现代科学之中。
图论的爆炸性发展, 导致了图论内容日益丰富多彩。欲将所有内容都包括在供一学期使用的教材中是不可能的。遵循“少而精”的原则, 利用最新研究成果指导选用材料。现代研究表明[4], 图论中有许多问题属于最困难一类
到标号算法。这样, 最小连接问题、人员安排问
题、最优安排问题、运输方案的设计、最优运输方案的设计、中国邮递员问题和货郎担问题等应用问题之间的密切联系就被揭示出来了。 3. 各学科的交叉和渗透
的问题, 而且解决的可能性不大, 但有非常广阔的应用前景。如H am ilton 问题, 染色问题等。我们在教材中只介绍它们的最初等的结果而不去深入讨论。反之, 连通性概念及其相关的理论在图论中发挥的作用越来越大, 应用前景也越来越广阔, 我们便在教材中加大了这部分的份量。
各学科相互交叉又相互渗透是现代科学的一大特点, 图论是体现这个特点的现代数学
2. 增强系统性
之一。图论的产生和发展得益于各学科的交叉
图论在数学科学中属于离散数学, 因此它和渗透。例如, 图论中最基本概念“树”就是来具有离散数学的许多特点。图论中许多概念和理论的产生和发展是相互独立的, 因而被分成许多相互独立的专题。传统的教材几乎都保持了这个特点, 给人的印象是图论是一些离散材料的堆砌, 毫无系统性。
源于化学、电子学和纯数学。图论提供的理论和方法应用于不同学科, 各学科的发展又为图论提供新的概念、新的研究课题和新的研究方法。这样反复循环才使图论有今天的发展。
《图论及其应用》教材除介绍图论在数学
要想形成一个自成体系的图论教材并非其他领域(如组合数学、矩阵论、拓扑学、群论、一件容易的事, 其中有许多是学术研究上的问线性规划、运筹学等) 应用外, 重点介绍图论在题, 还有材料安排上的问题。笔者在做了深入电子学、管理科学和计算机科学等方面的应地研究之后, 决心大胆尝试, 进行改革, 重新组用。在图论与其他数学分支的相互交叉和相互织安排材料, 力争使其系统性和科学性。那么渗透上也做了一些探讨。例如, 利用线性空间是什么概念和理论支撑了图论呢? 著名的图论专家C . T hom assen [5]指出:“关于图的最基本的、最经常被使用的结果大概是M enger 定理”。这对我启发很大。笔者在教材中以连通性为主线, 依次着重讨论支撑树、图空间、平面图、网络流、连通度、匹配与染色等主要概念和相关的理论。特别讨论了最大流最小截定理、
. .
M enger 定理、H all 定理、K o n ig 定理和T u tte 定理之间的等价关系, 把这些相关章节的内容系统地联系在一起, 形成一个不可分割的统一体。
理论和方法讨论图空间。特别是深入讨论了网络理论中的最大流最小截定理、图论中的
. .
M enger 定理与矩阵论中的H all 定理和K o
矩阵论、运n ig 定理之间的等价关系, 把图论、
筹学、线性规划紧密地联系在一起, 借助于同构概念把图与群联系在一起。当然, 这些联系决不是偶然的巧合, 恰恰是从不同的角度揭示了图论的数学本质。当然这些内在联系的理解需要有一定的数学修养, 对于非数学专业的学生可能有些困难。但笔者认为, 作为图论教材,
揭示一些图论的数学本质对学生进一步理解
理论部分是这样, 应用部分也力争作到这图论、理解数学是必要的。只有真正理解数学一点, 这里讲的主要是算法。例如, 我们在介绍的人, 才能真正尝到数学的特殊乐趣。解决货郎担问题的一个近似多项式算法时, 选
4. 理实交融
用了Ch ristofides 在1976年提出的一个最新
的有效算法。这种算法用到求最优树算法、求理实交融是我校老校长郭沫若所倡导的最小权完备匹配算法和求Eu ler 圈算法。而求优良学风。图论来源于实践又服务于实践。从最小权完备匹配用到匈牙利算法; 求Eu ler 圈这个意义上讲, 图论又属于应用数学学科。我用到最小费用最大流算法。最小费用最大流用们在教材编写的过程中始终贯彻理实交融这
一原则。
《图论及其应用》是一门数学选修课程。首先应突出它是一门数学, 而且是其它任何数学分支所不能替代的, 因此它有一套特有的理论和研究方法。简练的数学语言, 严谨的理论推导和一定深度的讨论是必不可少的。虽然只是一门选修课程, 但选修的学生大多是高年级本科生并且具有一定的数学基础, 因此决不能把它当作科普课程来讲授。如果只有理论而没有应用, 这样的理论也只是空中楼阁, 学生也无兴趣, 会失去选修的意义。
笔者在《图论及其应用》教材中把理论和应用放在重要同等的位置。按照大部分教科书所采用的“定义一定理一应用”的叙述方式将每章分成两大部分。前一部分是理论部分, 后一部分为应用部分。这样安排好处有二:一是便于对学生有一个统一要求, 即理论部分由浅入深, 大部分是必修的; 二是便于学生选修应用方面的材料。至于应用材料也是在很大程度上做了选择, 即有理论又有方法。那些只用到图论语言而无理论的所谓应用一概不列其中。所列入的大多数应用问题都给出有效算法, 便于学生日后上机实践。对于专业性很强的应用, 我们在章末给出阅读指南。例如, 对图论在电网络应用方面感兴趣的同学可参阅《网络图
[6]论及其应用》; 对图论在理论物理应用方面
[7]
感兴趣的同学可参阅《图论与理论物理》; 对图论在化学应用方面感兴趣的同学可参阅《图
[8]
论在化学中的应用》等等。
几年来的教学实践证明, 同学们对这样的
地和拓展空间。这样对发挥任课教员和学生的教学积极性、主动性和提高教学效果都很有好处。该教材在下述几个方面作了些尝试。
①引入图的概念和结果时, 着眼于有向图。无向图中相应的概念和结果不加赘述。一些定理的推论也不给出证明, 留给学生补充消化。有些结论对有向图是成立的, 但对无向图却不成立。教材中只指出却不说明为什么, 留给学生们自己去思考。
②只着重论述最基本的概念和结果。还有一些重要概念和内容, 如度序列、特征多项式、
非平面图、极值图、重构等都是图Steiner 树、
论中重要的基本概念, 并且有一些漂亮的结论未包含在教材中, 留给任课教员视选修对象和课时作适当补充。该教材力图加强各专题之间的紧密联系, 为保持其独立性, 仍然给出主要经典定理的独立证明。内容安排由浅入深, 循序渐进。较难的章节打3号, 较深入的讨论和应用放在每章的最后。目的是供任课教员对教学作适当调整而不影响后面的教学。同时也为不同层次的学生留有选修的空间。
③笔者在教材中没有选用很有趣的所谓趣味应用材料。一方面, 考虑到已出版了许多
[9]
有关的小册子, 比如《有趣的图论问题》、《趣
[10]
味图论》等等。另一方面, 留给任课教员自己选用, 方可以提高学生的兴趣, 活跃课堂气氛。再说, 有兴趣的同学也可以自己去参阅这些小册子。
④在部分习题中引入新的概念和一些研究结果, 可供有余力的学生进一步提高, 也为
安排感到自然, 表示满意。
任课教员调整教学内容提供选用材料。
⑤章末有小结和参考文献, 为学生进一步
5. 留有余地
学习提供指南, 也为提高学生查阅文献能力作
作为高校本科生用的教材, 特别是选修课些尝试。教材, 对教员授课和学生练习应留有一定的余
四、教学方法的研究和探讨
图论中概念比较多, 论证方法独特而又千读教材中给出的证明时也不会感到困难。第二
变万化, 初学者不易掌握。课时短, 而且选修的个问题的难度是在图论的应用上。课堂上只着学生遍及全校几乎所有的专业和不同的年级, 重讲解使学生普遍感兴趣的应用, 而专业性较知识水平、理解能力和兴趣大不相同。这些都强的应用, 让学生自修。给教学带来一定的困难, 如不加以探讨和改
2. 分类指导
进, 势必影响这门课程的教学效果。笔者体会有以下几点:对于兴趣比较集中的专题和选修学生比较多的专业, 开展专题讲座和讨论会的方式,
来解答和讨论同学们提出的问题。对个别同学
公共点有两个方面的意思:一是尽管学生可以采用答疑、提供参考文献等方法来满足他们各自情况不同, 但要选修这门课应有一个基们的求知渴望。并为同学们创造条件提供一些本的公共要求, 这就是要求学生掌握图论中一应用图论的实践机会, 比如鼓励同学们参加数 1. 抓住公共点
定的基本概念和结论以及基本方法。二是摸清学建模竞赛, 听一些专题报告等。学生选修该课程的共同兴趣。为解决第一个问
3. 撰写小论文
题, 课堂教学主要精力放在基本概念的讲解上, 通过大量的实例使同学们首先弄清这些基结合专业特点和学习收获要求学生撰写本概念和图论中常用的基本方法, 并适当补充小论文作为这门课程期末考查内容之一。课程一些如六人集会, 莱狼羊过河, 分油等有趣味的问题, 以唤起初学者的兴趣。对一些难度较大的定理证明采用具体图例, 讲清论证方法的基本思路和一些可能会使学生感到困难的关键地方。这样, 对证明细节有兴趣的同学在阅
一开始就向同学们提出要求, 使学生们早有准备并有目的去进行学习。论文成绩占期末成绩的50%。在课堂教学过程中, 经常提供一些可供同学们研究的问题, 鼓励学生去积极思考。
参 考 文 献
[1] 王树禾, 《图论及其算法》, 中国科大出版社, 1990。
[2] B iggs , N . L . L loyd , E . K &W ilson , R . J . , 《Graph T heo ry 1736-1936》, C larendon P ress , O x 2
fo rd , 1976.
[3] 吴修珉, 图论发展的一些动态, 数学进展, 13(1984) , 241-253。
[4] Gravey , M . R . &John son D . S . , 《计算机和难解性—N P 完全性理论导引》, 中译本, 科学出版社,
1987。
[5] T hom assen , C , 图论的回顾, 中译文, 《数学译林》, 1987, N o . 4, 65-75。[6] 陈树柏等, 《网络图论及其应用》, 科学出版社, 1982。
[7] H arary , F . , 《Graph T heo ry and T heo retical Physics 》, A cadem ic P ress , 1967。[8] Balaban , A . T . 《图论在化学中的应用》, 中译本, 科学出版社, 1983。[9] 单土尊, 《趣味的图论问题》, 上海教育出版社, 1980。
口[10] 柯文, 《趣味图论》, 中国青年出版社, 1987。