《离散数学》电子教案 第7章 特殊图-教案

第7章特殊图一、教学内容及要求授课学时：8教学内容：7.1树树的基本概念及性质；生成树及算法；根树的定义与分类；根树的遍历；最优树与哈夫曼算法。7.2欧拉图欧拉图的引入与定义；欧拉图的判定。7.3哈密顿图哈密顿图的引入与定义；哈密顿图的判定；7.4偶图偶图的定义；偶图的判定；匹配。7.5平面图平面图的定义；平面图判定；欧拉公式；库拉托夫斯基定理。7.6特殊图的应用无向树的应用；根树的应用；欧拉图的应用；哈密顿图的应用；偶图的应用；平面图的应用。基本要求（1）掌握树、根树、生成树、最小生成树、二元树、k元完全树、子树、最优树等基本概念。（2）掌握树中有一个很重要的性质：m=n−1。这个性质与握手定理配合使用，更显其重要性，在有关无向树、有向树的很多证明中都可用到。（3）掌握树的算法：破圈法、避圈法、Kruskal算法、Prim算法、哈夫曼算法。（4）了解树的算法：生成树的广度优先搜索算法，二元树的先（中、后）根次序遍历算法，根树转化为二元树算法，森林转化为二元树算法。（5）了解树的同构及应用。能力培养：将树的基本知识用于解决实际问题，培养学生的算法能力。二、教学重点、难点及解决办法教学重点：无向树的基本概念；无向树的性质，特别是m=n-1和至少2个叶结点；生成树和最小生成树及其求解算法；根树的概念与分类；欧拉图及其判定，Fleury算法；哈密尔顿图及其判定；偶图及其判定、匹配；平面图及其判定，欧拉公式，库拉托夫斯基定理。教学难点：哈密尔顿图的判定；平面图的判定，库拉托夫斯基定理。解决办法：在教学过程中，通过实例深入讲解树的基本概念及相关性质，讲练结合，及时解决学生在学习过程中遇到的问题。1）树是不含回路的连通图，特别注意树的叶结点数目以及边数与结点数的关系。2）最小生成树是赋权连通图的权值之和最小的生成树，可使用keruskal算法和prim算法求解。3）有向树是略去所有边的方向所得无向图为无向树的有向图；根树是只有一个结点的入度为0，其余结点的入度均为1的有向树；注意根树的叶和分支点与无向树的叶和分支点的细微差别。4）有序树是对结点标定了顺序的根树5）k元树的每个分支点至多有k个儿子，因此其出度均小于等于k，一般取满足条件的最小值k；k元完全树的每个分支点都恰有k个儿子，因此其出度均恰好等于k。6）注意区分以v为根的子树和v的左子树、右子树。7）二元树遍历的三种方法，先根次序遍历法、中根次序遍历法、后根次序遍历法。8）有序树、森林与二元树之间的相互转换。三、教学设计介绍与欧拉图问题相关联的中国邮路问题，引出管梅谷教授。通过管梅谷教授的介绍，增强学生的民族自信心和自豪感。同时也告诫学生，中国的科技发展，尤其是在基础科学方面仍有不小的差距，需要更多后来人的努力。1）利用比赛结果图给出树的定义，注意分析多种方法对于求解树的相关问题的影响；将树的相关问题与实际应用和数据结构课程中的应用结合进行介绍。2）利用不同的问题引出不同的特殊图，强调特殊图的判定条件的使用。在学习完本章内容后，再从思维导图，重点解题方法和重点题型方面进行总结。1）再提思维导图让学生把握整章知识脉络，更好地把握重点和难点。2）利用树的性质m=n-1，将其与握手定理配合使用，在很多证明和计算中都很重要。3）用特殊图的定义分析和判断某个特殊图。4）在哈密尔顿图、平面图和偶图的匹配中都分别有定理仅是必要条件，注意必要条件主要用于判断一个图不是哈密尔顿图、平面图和匹配。5）在计算和证明与结点的度数有关的问题时，经常使用握手定理。6）构造性证明方法的使用，只有找到了就一定存在。7）反证法非常有用，特别是在证明唯一性和不存在的时候。通过课堂实例和课后实践作业，讲练结合，培养学生解决实际问题能力，并强化学生的算法思想。四、作业（第256-260页）1371011152021232729(a)(e)33353840(b)(d)4145(b)48五、参考资料见前面课程说明部分的参考书目对应章节。六、教学后记树是一种重要的特殊图，对树的定义及其几种等价定义等价性的证明