获得北京市高校第五届青年教师教学基本功比赛最佳教案奖
北京高校第五届
青年教师教学基本功比赛
                       
参赛教案
类    别  A组理工类
任课教师  岳瑞锋
北京高校第五届
青年教师教学基本功比赛
参赛教案
课程名称  运筹学
授课章节  第六章 图论 §1 图的基本概念
授课对象  非数学专业本科二年级
授课时间  50分钟
任课教师  岳瑞锋
1．【教学目标】
1)知识层面：通过七桥问题掌握欧拉定理，并利用中国邮路问题理解欧拉定理在解决实际问题中的作用。掌握关于图的一些基本概念和结论。
2)能力层面：通过解决七桥问题和中国邮路问题，培养学生将实际问题加以抽象，建立一般模型的能力。学习利用数学知识，分析和解决模型，并最终回到实际问题。
3)认知层面：体会图论中对图的讨论和传统几何学的不同之处，认识到对图的这种分析角度打开了一个新的视野。
2．【教学内容】
1)七桥问题与欧拉定理。
2)中国邮路问题的解法。
3)图的基本概念和结论。
3．【教学重点与难点】
1)教学重点：欧拉定理，中国邮路问题，图的有关概念。
处理方法：重点讲解；启发主动思考；提供学生参与机会。
2)教学难点：中国邮路问题算法过程；关于图的三个定理。
处理方法：根据学生反映，把握讲解速度；结合多媒体课件；利用提问方式，随堂检验学生掌握程度。
4．【教材分析】
图与网络分析是运筹学的重要内容之一。它以图为研究对象。图论中的图指的是一些点以及连接这些点的线的总体。通常用点代表事物，用连接两点的线代表事物间的关系。图论是研究事物对象在上述表示法中具有的特征与性质的学科。图论的研究发源于18世纪普鲁士的柯尼斯堡。从19世纪中叶开始，图论问题大量出现。比如哈密顿问题、四问题以及与之相关联的图的可平面性问题等。1936年D.柯尼希发表了图论的第一本专著《有限与无限图理论》，这时图论才成为一门学科。近代以来，由于生产管理、军事、交通运输和计算机网络等方面出现了大量实际问题，特别是许多离散化问题的出现，以及由于大型高速电子计算机而使许多大规模问题求解成为可能，图论的理论及其应用研究得到飞速发展。尤其是图论与线性规划、动态规划等优化理论和方法的互相渗透，促使和丰富了图论的内容和应用。
本次课是图论的第一节内容。由于图论直接从现实问题入手，经过抽象构建一般理论。对学生而言，除了比较基础的线性代数知识外，对其他分支的数学内容要求不高。但由于图论中对图的分析视角完全不同于传统几何学，从认知水平上，属于全新的认识角度。为了构建这门学科体系，学习图论之初要涉及大量的概念和定义，这将使得本来生动活泼的图论显得枯燥乏味。为了能够引起学生的学习兴趣，可从图论上的一些经典的问题入手，在此基础上，逐步引入重要的概念和结论，为后续的有关图的一些算法做准备。例如用七桥问题和中国邮路问题引入课程内容，逐步引导学生从实际问题中抽象出一般的图，并体会如何通过对图的讨论来解决现实问题。
本部分内容一方面具有较为直观的意义，另一方面，如果上升为数学上的一般结论，又不得不借助于大量的符号语言和逻辑推理。在教学过程中，应恰当处理借助图形直观含义和严密的数学推理之间的关系。既要引导学生从直观上发现问题的实质，也要注意对某些关键的结论进行缜密的逻辑推理。例如欧拉定理和中国邮路问题的算法过程的直观意义相当明显，但要进行数学证明则需要借助许多相关的概念和结论，证明过程反而掩盖了其数学本质，这时候就不易进行数学证明。
5．【设计思路】
1)设计要点一：
通过介绍七桥问题引入本课内容，一方面有助于引起学习兴趣，另一方面通过介绍七桥问题，使学生初步体会认识图的新视角。
设计依据：
创设问题情境，引起注意和好奇心理，是激发学习动机，进行有效学习的重要因素。
2)设计要点二：
利用中国邮路问题阐述欧拉定理的应用，进一步体会图论和传统几何学对图的分析视角的重要区别。在完成中国邮路问题的算法过程之后，引导学生自主分析这种区别并进行归纳，从而完成从直观感觉到认知水平的升华。
设计依据：
学习的过程不仅仅简单掌握方法，更重要的是原有知识的重新体认，是认知结构的重塑和提升。
3)设计要点三：
七桥问题和中国邮路问题的解决过程都遵循了“实际问题—建立模型—分析模型—解决问题”的思维方式。通过这种方式的教学，在潜移默化中培养学生利用已有知识解决现实问题的能力。
设计依据：
授课过程不仅要传授知识，而且要注重能力的培养。
4)设计要点四：
上述两个问题有助于让学生认识到“图论既有意思也很有用处”，从而激发其求知欲望，这时恰当把握时机，将求知欲望转为学习动力，完成从“现实问题”到“数学理论”的升华，转入下一部分图的基本概念和结论。
设计依据：
每节课都有其内在的旋律，掌控其起承转合才能把握学生心理。适当情景下的转折是提升课
堂内容水平的关键。
6．【教学模式和手段】
1)教学模式：问题导入——启发思考——共同分析——构建知识。
2)教学手段：动态多媒体课件和板书结合。
7．【板书设计，教学大纲，参考文献】
见附件。
8．【教学过程】
教学步骤
教学内容
设计意图
表达方式
1．提出问题，导入本课内容。
一、引例：七桥问题(10分钟)
在哥尼斯堡镇(Konigsberg)的旁边有一条河流，河中有两个小岛，通过7座桥梁相连。有人提出这样一个问题：能不能不重不漏的走过每一座桥梁，并且再回到起点？有人写信请教当时在彼得堡科学院任院士的数学家欧拉，请他帮助解决这个问题。
图1-1
利用多媒体课件，
介绍问题背景，用问题激发学生兴趣。
2．分析问题特征，总结得到欧拉定理，并利用欧拉定理解决七桥问题。
1．建立模型
首先，欧拉试图将这个问题做一些抽象，将河的两岸和两个小岛分别看成点，将七座桥看成点之间的连线，于是，七桥问题就抽象为下列问题：
“在图1-2中，能不能从某点出发，不重不漏的走过每一条边，再回到起点？”
A
B
C
D
图1-2
将问题加以抽象，建立一般模型，在此过程中注意提醒学生思考问题的解决方法。
课件演示
2．解决问题的准备——几个概念
(1). 图(Graph)：一个图G包含两种元素:顶点集合V(Vertex)和边集合E(Edge)，即G={V,E}。
(2). 路(path)：在图中，若干条边相连，形成路。
(3). 连通图(connected graph)：任意两点之间都有路相连的图。
A
B
图1-3
(4). 奇顶点和偶顶点(odd vertex and教师基本功 even vertex)：
如果从某个顶点出发的边数是奇数，称这个顶点为奇顶点；否则称为偶顶点。
注意：奇偶顶点的分类，对于解决七桥问题至关重要。
利用课件中的图，学习这几个概念。
启发学生思考奇偶顶点的区别。
欧拉的结论：
(1)起点和终点不是同一点：只能有两个奇顶点。如图1-4。
(2)起点和终点是同一点：不能有奇顶点。如图1-5。
A
C
D
B
图1-4
A
C
D
B
图1-5
欧拉定理：连通图可以不重不漏走过每一条边的充分必要条件是图的奇顶点的个数为0或2，并且，当且仅当奇顶点的个数为0时，可以回到起点。
结合学生讨论，总结欧拉定理。
利用动画演示行进路线。
3．解决七桥问题：
在图1-2中，由于4个顶点均为奇顶点，所以，不存在不重不漏的走过每一条边并回到起点的走法。实际上，根据欧拉定理，即使不要求回到起点，也不存在不重不漏的走法。
从实际问题出发，还要回到实际问题中来。
4．知识扩展：
1921年，Fleury给出了欧拉回路的一般算法，详细资料可参见www.algorithmist/
延伸课堂内容，供学有余力的同学拓展知识面。
3．利用欧拉定理解决中国邮路问题。
二、欧拉定理的应用—中国邮路问题(15分钟)
问题描述：邮递员送信，怎样安排路线使他以最短距离走遍每个街道，最后再回到起点？
背景介绍：由山东师范大学的管梅谷于1962年提出并解决，所以被称为中国邮路问题。
根据杜威的学习观，必须经过检验才能获得新知识。
1．建立模型：
像解决七桥问题那样，将送信问题抽象为图。在图1-6中，顶点K表示邮局所在位置，边上的数字表示每一条街道的长度，邮递员需要从K出发，走遍每一条边之后，再回到K。从而问题转化为：
给定一个具有非负权的图G，求G的一个Euler赋权母图G*，使得尽可能小。
A
B
C
D
E
F
G
H
I
J
K
0.8
0.4
0.4
1.2
图1-6
与七桥问题类似，同样采用“问题—抽象—解决”的过程，目的是为了培养学生解决问题的能力。
课件演示
课堂讨论：如果图中不存在奇顶点，根据欧拉定理，必存在不重不漏并且回到起点的走法，这种走法就是问题的最优方案。但如果图中存在奇顶点呢？
问题1：在1-6图中，是否存在不重不漏的走法？为什么？
结论：根据欧拉定理，不存在。这意味着，要想走遍每条街道，某些街道必须重复。
问题2：直观上看，应该重复哪些街道，才可以使得总路程最短？
结论：应该重复那些比较短的街道。
问题3：那么该如何实现这种想法？（不形成结论，转入下一部份）
结合课件演示，提出问题，引起讨论，启发学生思考。
注意引导学生的讨论方向。
2．分析问题：
已经知道：第一，必定要重复走过某些街道。第二，最好重复走那些比较短的街道。在图中，可以用添加边的方式表示重复走的那些街道。如图1-7，表示计划重走H-K街道。
A
B
C
D
E
F
G
H
I
J
K
0.8
0.4
0.4
1.2
0.6
图1-7
摆脱实际问题背景，直接从图上分析。
课件演示
3．加边原则：
原则1：加边是为了去掉途中的奇顶点。因为根据欧拉定理，只有在图中不存在奇顶点时，才存在不重不漏并且回到起点的走法。
问题：如果按图1-8的形式加边，能不能保证总路程最短？
A
B
C
D
E
F
G
H
I
J
K
0.8
0.4
0.4
1.2
0.6
图1-8
结论：不能，因为可以在圈中加另外的边。
原则2：每个圈上所加的边长之和不能超过圈的一半。
问题：怎样加边才可以使得总路程减少？
结论：如果某个方案在某个圈上所加的边长超过圈长的一半，则应该改进。
原则3：如果超过,则去掉原来所加的边,在圈中剩余路线上加边。
总结：加边的这三个原则就可以使得即减少了奇顶点的数目，又可以使得总路程最短。
结合课件，依次提出问题，师生共同参与讨论，归纳三原则。
4．解决问题：
1)寻初始可行方案（Feasible Scheme）。在图1-6中，任意确定一种加边方式。如图1-9。
A
B
C
D
E
F
G
H
I
J
K
0.8
0.4
0.4
1.2
0.6
图1-9
2)方案的迭代（iteration）。由于在圈ABJKHIA中，所加边的总长超过圈长的一半，根据加边原则，去掉所加边AI，AB，HK。用边HI，BJ，JK迭代。得到图1-10。
A
B
C
D
E
F
G
H
I
J
K
0.8
0.4
0.4
1.2
0.6
图1-10
3)得到最优方案（Optimal Scheme）。在图1-10中，不再含有奇顶点，并且每一个圈上所加的边长总合不超过圈长的一半。于是如图1-11所示的行进方式就是邮递员走过每一条街道，回到邮局的最佳路线之一。
A
B
C
D
E
F
G
H
I
J
K
0.8
0.4
0.4
1.2
0.6
图1-11
总结：以上通过对图的讨论解决了七桥问题和中国邮路问题。和传统几何学一样，现在也是在讨论和分析一些几何图形，但是分析的方法和视角和传统几何学却不一样。这是七桥问题的意义所在。
根据加边原则，解决中国邮路问题。
体会初始解和解的迭代思想。
动画演示最优方案
小结并过渡，完成课堂内容的转折。
5．知识扩展：
中国邮路问题是NP难度问题。上述算法过程中，在每一次方案迭代时都要检查每个圈，当图较为复杂时，算法的效率很低。1973年，著名的组合数学家J. Edmonds和Johnson结合Fleury算法给出了解决一般邮路问题的更好的算法。对这个算法的详细资料可参考《算法分析导论》（作者Robert Sedgewick）。
延伸课堂内容，供学有余力的同学拓展知识面。
4．总结上述两个问题的解决过程，引导学生以新的视角来认识图。
三、七桥问题的意义(4分钟)
1．一种新的几何学——拓扑学(Topology)。
欧拉认识到，虽然七桥问题也是对图形的讨论，但是现在的视角和传统的几何学不同。初等几何研究的是在刚性变换下的图形的不变性质，如长度、角度、面积。射影几何研究的是在射影变化下图形的不变性质，如点、直线和交比。现在关注的是图形的顶点和边之间的关联和邻接关系是否存在。这种新的视角促进了一种新的几何学——拓扑学的诞生。拓扑学研究的是在拓扑变换下图形的不变性质。由于一个圆可以经过连续的变换，得到一个三角形，所以在拓扑学看来，圆和三角形就是拓扑等价的。
图1-12
结合课件概括介绍拓扑学，但本部分不是本课的核心，只是提供一个思考的视角，意义2才是本部分的目的。
2．图论的产生。
因为拓宽了数学的视野，所以对图的讨论在数学理论上有着重要的意义，同时随着对图的深入研究，人们逐渐认识到，许多现实生活中的问题都可以经过抽象而最终归结一个图。比如运输问题，网络流量问题，最优的生产安排问题等等。而研究如何通过对图的讨论解决现实中的一些优化问题，就是现在要学习的运筹学的分支——图论的研究内容。
这部分即是课堂的又一个转折点，也是课堂内容的升华。
5．进一步学习图的有关概念。
四、图的基本概念和结论(20分钟)
1.空图和平凡图：没有边的图称为空图；只有一个点的图称为平凡图。
2.简单图：任何一条边的两个端点都不重合，任何两条边都没有连接同一对点的图。图1-2显然不是简单图。而图1-6则是一个简单图。若图是简单图，则，其中分别表示E和V中的元素个数。
3.完全图：每对点之间均有边相连的简单图。有n个顶点的完全图记为，显然有条边。
4.二分图：图，如果存在V的一个划分(S,T)使得G的每条边均有一个端点在S中，一个端点在T中，称G为二分图，也叫偶图。比如图1-13就是一个二分图：
图1-13
5.补图：图G的补图是与G有相同的顶点集合简单图，并且中的两个点有边当且仅当它们在G中没有边。图1-14种的两个图就互为补图。
图1-14
6.关联矩阵：简单图与一个矩阵对应，其中。例如，图1-4对应着以下矩阵：
7.邻接矩阵：简单图还对应着另一种矩阵，其中，例如，图1-4对应着以下矩阵：
明显，邻接矩阵是一个对称矩阵。
结论：给定一个简单图，一定可以写出其关联矩阵和邻接矩阵。
问题：如何从简单图的关联矩阵和邻接矩阵中计算顶点的奇偶性？
课堂讨论。
提示：从矩阵的行元素来考虑
结论：如果关联矩阵和邻接矩阵的某行元素的和为奇数，则相应的顶点为奇顶点，否则为偶顶点。
之前的内容既是为了概括介绍图的新的认识角度，也是为了激发学习兴趣。从本部分开始转入图论的理论学习。
内容稍显枯燥，注意结合课件和直观作图。
此时应提醒学生注意，虽然图有不同的类型，但在这些概念的基础上，就能够用代数的方法来表示图。
6．学习关于图的几个结论。
定理1  G是二分图，当且仅当G的邻接矩阵可表示为，其中表示零矩阵。
课堂练习：写出图1-13的邻接矩阵。
一般的，与简单图的顶点i相关联的边数称为顶点i的次，并用表示，则有以下定理成立。
定理2  (1) .
(2) .
定理2的证明作为课下练习。
定理3   任何一个图中，奇点的个数为偶数。
证明：设分别为图中奇顶点和偶顶点的集合，由定理2，得到
因为均为偶数，所以也是偶数，所以中元素的个数为偶数。
证毕
在前述概念的基础上，学习这些结论的同时体会如何用数学表达式表现图的性质。
7．通过小结，概述本课内容，并布置作业和预习任务。
五、课堂小结和课下作业(1分钟)
1.小结：
本节课通过七桥问题引入了对图的讨论，并且总结得到了欧拉定理，利用欧拉定理，解决了中国邮路问题。通过这两个问题，我们体会到了分析和研究图的一种新的视角，这是在本章所要学习的内容：图论。在此基础上，引入了一些图论的基本概念，主要有图，图的路，连通图，奇偶顶点，简单图，完全图，二分图，关联和邻接矩阵，并且总结得到了有关图的几个命题。这些概念和命题是进一步分析和研究图的基础。
2.作业和预习要求
课下复习回顾本节内容，掌握有关概念，并预习第二节：图的连通与割集。
通过课堂总结，让学生对本节课内容形成整体认识。
六、课后反思和总结
课程结束后，反思整个教学过程，总结经验和教训。
附件：
1．板书设计：
2．教学大纲（节选）：
第六章 图论
1)图的基本概念：欧拉定理；中国邮路问题；图的基本概念和结论。
2)图的连通与割集：图的连通；图的割集。
3)树与支撑树：树及其基本性质；支撑树及其基本性质。
4)最小树：最小树及其基本性质；求最小树的Kruskal算法；Dijkstra算法。
5)最短有向路：最短有向路方程；求最短有向路的Dijkstra算法。
6)最大流：最大流最小割定理；最大流算法。
7)最小费用流：最小费用流算法。
基本要求：深刻理解图与网络概念，掌握矩阵、集和树等相关概念；理解最小树的Kruskal算法和Dijkstra算法思想和基本步骤；了解最短有向路方程，掌握求最短有向路的Dijkstra算法思想和基本步骤；理解最大流最小割定理。
3．参考文献：
1)刁在筠等编.《运筹学》(第二版).高等教育出版社.2002年.
2)董肇君等编著.《系统工程与运筹学》.国防工业出版社.2003年.
3)钱颂迪主编.《运筹学》（修订版）.清华大学出版社.2002年
4)[美]R·柯朗，H·罗宾，著.《什么是数学——对思想和方法的基本研究》.复旦大学出版社.2004年.
5)张振民等主编.《站在大学讲台上》.北京理工大学出版社.2004年.