第六章 图论 §1 图的基本概念
教学步骤 教学内容 设计意图 表达方式 四、图的基本概念和结论(20分钟) 1. 空图和平凡图：没有边的图称为空图；只有一个点的图称为平凡图。 2. 简单图：任何一条边的两个端点都不重合，任何两条边都没有连接同一对点的图。图1-2显然不是简单图。而图1-6则是一个简单图。若|V|(|V|?1)图G?{V,E}是简单图，则|E|?，2其中|E|,|V|分别表示E和V中的元素个数。 3. 完全图：每对点之间均有边相连的简单图。有n个顶点的完全图记为Kn，显然Kn有|V|(|V|?1)条边。 24. 二分图：图G?{V,E}，如果存在V的一个划5．进一步学习图的有关概念。 分(S,T)使得G的每条边均有一个端点在S中，一个端点在T中，称G为二分图，也叫偶图。比如图1-13就是一个二分图： 图1-13 5. 补图：图G的补图G是与G有相同的顶点集合简单图，并且G中的两个点有边当且仅当它们在G中没有边。图1-14种的两个图就互为补图。 图1-14
10
之前的内容既是为了概括介绍图的新的认识角度，也是为了激发学习兴趣。从本部分开始转入图论的理论学习。 内容稍显枯燥，注意结合课件和直观作图。 第六章 图论 §1 图的基本概念
教学步骤 教学内容 6. 关联矩阵：简单图G?{V,E}与一个矩阵设计意图 表达方式 B?(bik)|V|?|E|对应，其中 此时应提?1, 点i与边k关联。例如，图1-4对应着醒学生注bik??0， 否则?意，虽然以下矩阵： 图有不同的类型，ABACADBCDC????但在这些1100??A1概念的基?B10010? ??础上，就C01011??能够用代?D0?0100??数的方法7. 邻接矩阵：简单图还对应着另一种矩阵来表示图。 ?1, 点i与点j邻接A??aij?|V|?|V|，其中aij??，例0， 否则?如，图1-4对应着以下矩阵： ABCD????A0111???B1010? ???C1101??D1010???明显，邻接矩阵是一个对称矩阵。 结论：给定一个简单图，一定可以写出其关联矩阵和邻接矩阵。 问题：如何从简单图的关联矩阵和邻接矩阵中计算顶点的奇偶性？ 课堂讨论。 提示：从矩阵的行元素来考虑 结论：如果关联矩阵和邻接矩阵的某行元素的和为奇数，则相应的顶点为奇顶点，否则为偶顶点。 定理1 G是二分图，当且仅当G的邻接矩阵 ?OA?可表示为? ?ATO??，其中O表示零矩阵。 ?? 课堂练习：写出图1-13的邻接矩阵。 一般的，与简单图的顶点i相关联的边数称为 顶点i的次，并用di表示，则有以下定理成立。 11
6．学习关于图的几个结论。
第六章 图论 §1 图的基本概念
教学步骤 教学内容 定理2 (1) di??bik??aij. 设计意图 表达方式 在前述概kj念的基础上，学习(2) ?di?2|E|. i这些结论定理2的证明作为课下练习。 的同时体定理3 任何一个图中，奇点的个数为偶数。 会如何用数学表达证明：设V1,V2分别为图中奇顶点和偶顶点的集式表现图合，由定理2，得到 的性质。 di??di??di?2|E|?ii?V1i?V2 因为?di,2|E|均为偶数，所以?di也是偶i?V2i?V1数，所以V1中元素的个数为偶数。 证毕 五、课堂小结和课下作业(1分钟) 7．通过小结，概述本课内容，并布置作业和预习任务。 1. 小结： 本节课通过七桥问题引入了对图的讨论，并且总结得到了欧拉定理，利用欧拉定理，解决了中国邮路问题。通过这两个问题，我们体会到了分析和研究图的一种新的视角，这是在本章所要学习的内容：图论。在此基础上，引入了一些图论的基本概念，主要有图，图的路，连通图，奇偶顶点，简单图，完全图，二分图，关联和邻接矩阵，并且总结得到了有关图的几个命题。这些概念和命题是进一步分析和研究图的基础。 2. 作业和预习要求 课下复习回顾本节内容，掌握有关概念，并预习第二节：图的连通与割集。 通过课堂总结，让学生对本节课内容形成整体认识。 六、课后反思和总结 课程结束后，反思整个教学过程，总结经验和教训。 12
第六章 图论 §1 图的基本概念
附件： 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年.
13