离散数学-教案 -第7章7.1 无向树及生成树1

课堂教学设计22章节（专题）第7章树计划学时2课题（内容）7.1无向树及生成树（1）教育教学目的1.理解无向树与森林、生成树与余数的相关概念2.掌握基本回路与基本格式的相关定义3.掌握最小生成树与避圈法4.思政目标：无向树具有连通且无回路的特性，其每一个顶点和边都相互关联、不可或缺，如同集体中的每个成员，只有紧密协作才能维持整体的稳定与功能。在生成树的构建过程中，学生通过参与算法实践，如普里姆算法或克鲁斯卡尔算法，需要团队成员各司其职、相互配合，共同完成最小生成树的求解。这有助于学生理解个人在集体中的责任与价值，培养集体荣誉感，强化团结协作意识，树立集体主义价值观。教学重点及难点1.重点：避圈法、无向树及生成树的基本概念2.难点：避圈法、最小生成树教学方法及手段1.讲授法2.互动式教学3.多媒体辅助教学教学互动环节设计1.课程回顾导入新课（特殊的图）2.启发式提问引发课堂讨论（对最小生成树的理解）课后总结与反思第7章树7.1无向树及生成树课程导入展示古代园林的路径布局图，提出问题：“园林设计师如何设计路径，既能让游客游览所有景点，又不出现重复路线？”引导学生思考其中蕴含的数学原理，引入无向树及生成树的概念。无向树的定义不含回路的连通无向图称为无向树，简称树。每个连通分支均是树的非连通无向图称为森林。平凡图称为平凡树。树中度数为1的顶点称为树叶，度数大于等于2的顶点称为分支点。例如下图为一棵12阶树。说明：本章中所讨论的回路均指简单回路或初级回路。平凡树:平凡图森林:每个连通分支都是树的非连通的无向图树叶:树中度数为1的顶点分支点（内部结点）:树中度数2的顶点思政目标：无向树具有连通且无回路的特性，其每一个顶点和边都相互关联、不可或缺，如同集体中的每个成员，只有紧密协作才能维持整体的稳定与功能。练习：请指出下图中的分支点和树叶无向树的应用英国数学家凯莱(ArthurCayley)于19世纪中叶研究饱和碳氢化合CnH2n+2的同分异构体时提出树的概念.当n=1,2,3时,都只有一棵非同构的树;当n=4时,有2棵不同构的树.甲烷甲烷乙烷丙烷丁烷异丁烷无向树的性质定理：设G=<V,E>是n阶m条边的无向图,则下面各命题是等价的：(1)G是树(连通无回路);(2)G中任意两个顶点之间存在惟一的路径;(3)G中无回路且m=n-1;(4)G是连通的且m=n-1;(5)G是连通的且G中任何边均为桥;(6)G中没有回路,但在任何两个不同的顶点之间加一条新边后所得图中有惟一的一个含新边的圈.练习：判断下图中哪些属于无向树？定理：设T是n阶非平凡的无向树，则T中至少有两片树叶.证设T有x片树叶,由握手定理及前面的定理，2(n-1)>=x+2(n-x)解得x>=2.例题分析例1计算6阶非同构的无向树的个数。解顶点数n=6，边数m=n−1=5，总度数为2×5=10，每个顶点的度数都大于等于1且小于等于5，因此顶点度数分配如下：（1）1 1 1 1 1 5（2）1 1 1 1 2 4（3）1 1 1 1 3 3（4）1 1 1 2 2 3（5）1 1 2 2 2 2根据每种度数分配情况，将非同构的树都画出来：（1）（2）（3）（5）各有1棵非同构的树，而（4）有2棵非同构的树，共6棵非同构的树，分别对应图7.2所示各图。（1）（2）（3）（4）（5）（6）例2在一棵树中有7片树叶，3个3度顶点，其余都是4度顶点，则该树共有多少个4度