《离散数学》电子教案 第6章 图-教案

第六章图一、教学内容及要求授课学时：8教学内容：6.1图的基本概念图的定义；图的表示；图的操作。6.2握手定理邻接点与邻接边；图的分类：按边有无方向分类、按有无平行边分类、按边或结点是否含权分类；子图与补图；握手定理、推论及应用。6.3图的同构图同构的定义及判断。6.4通路与回路通路，回路，基本通路和简单回路等基本概念；无向赋权图的最短通路及求解算法：Dijkstra算法和Floyd算法。6.5图的连通性无向图连通性的定义及其判定，连通分支；有向图的强连通，单向连通和弱连通；强分图，弱分图和单向分图等概念及其判定。6.6图的应用网络的结构；渡河问题；均分问题。基本要求：1）重点掌握图论的基本定理，即握手定理及其推论的内容，并且能灵活地应用。2）记住简单图的概念及主要特征，分清与线图的区别。3）掌握几种特殊图：无向完全图，子图，补图等。4）掌握有向、无向图之间同构的概念，会判断结点数较小的图之间的同构。会求4阶无向完全图K4和3阶有向图K3的非同构子图。5）弄清通路与回路的各种概念，掌握可达性及图的各种连通性，并能熟练的做出判断。6）对于上述全部的内容，都能用矩阵熟练地加以判断。7）在图论中，也可采用第一、第二数学归纳法证明，或反证方法。能力培养：将图论的基本知识用于解决实际问题，培养学生的抽象思维能力。二、教学重点、难点及解决办法教学重点：图的基本概念及分类；握手定理的理解与运用；邻接矩阵的理解与运用；通路与回路的理解与运用；图连通性的判定；连通分支的计算。教学难点：图同构的判断与证明；单向连通图的判断；连通分支的计算。解决办法：在教学过程中，通过实例深入讲解图论的基本概念、图连通性和子图的判断方法，讲练结合，及时解决学生在问题解决时遇到的问题。1）判断图的同构还没有一个很好的解决办法，主要凭经验，根据结点度数和关联的其它结点进行判断和尝试。2）握手定理是图论的基本定理，很多理论都是以它为基础的，必须熟练掌握，并能灵活运用。3）注意区分简单通路与基本通路，简单回路与基本回路；4）可以利用邻接矩阵来计算任意两结点间固定长度的通路数目和距离；利用可达性矩阵来判断图的连通性。5）计算图的连通分支，特别是有向图的单向分图，是比较难的问题。三、教学设计图论中所谓的图是指某类具体离散事物集合和该集合中的每对事物间以某种方式相联系的数学模型，许多实际问题都可以抽象为图这种数学模型。在教学中讲述图论之父-欧拉的故事，欧拉在双目失明的情况下仍然坚持科学研究，凭着惊人记忆力笔耕不辍，写下不朽篇章，为人类留下了宝贵的精神财富。在潜移默化中培养学生的人文思想和人文精神，铸就优秀的道德品质，塑造正确的价值观和人生观。首先举出多个不同的例子，指出这些例子的共同点，并从中得到图的基本定义。在讲述的过程中，始终贯穿图的矩阵表示法。在学习完本章内容后，再从思维导图，重点解题方法和重点题型方面进行总结。1）再提思维导图让学生把握整章知识脉络，更好地把握重点和难点。2）图的集合表示法、图形表示法和矩阵表示法在同构的意义下是唯一的。3）图的邻接矩阵既描述了图中结点间的邻接关系，还可以利用通过计算结点间的通路数目、判断图的连通性。4）判断两个图同构，只能依据同构的定义，构造两个结点集之间的双射函数，没有简单的方法。5）在计算和证明结点的度数有关的问题时，经常使用握手定理。6）反证法非常有用，特别是在证明唯一性和不存在的时候。7）重点题型主要是握手定理相关的计算与证明；图是否同构的判断；结点间通路数目的计算；结点间可达的判断与距离的计算；可达性矩阵的计算；无向图连通性的判断及其连通分支个数计算；有向图连通性的判断。通过课堂实例和课后实践作业，讲练结合，培养学生解决实际问题和抽象思维能力。四、作业（第205－208页）

5

710

11171823

25

2728五、参考资料见前面课程说明部分的参考书目对应章节。六、教学后记教学按计划完成。讲授时，无向图可详