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

课堂教学设计23章节（专题）第7章树计划学时2课题（内容）7.1无向树及生成树（2）教育教学目的1.理解无向树与森林、生成树与余数的相关概念2.掌握基本回路与基本格式的相关定义3.掌握最小生成树与避圈法4.思政目标：无向树具有连通且无回路的特性，其每一个顶点和边都相互关联、不可或缺，如同集体中的每个成员，只有紧密协作才能维持整体的稳定与功能。在生成树的构建过程中，学生通过参与算法实践，如普里姆算法或克鲁斯卡尔算法，需要团队成员各司其职、相互配合，共同完成最小生成树的求解。这有助于学生理解个人在集体中的责任与价值，培养集体荣誉感，强化团结协作意识，树立集体主义价值观。教学重点及难点1.重点：避圈法、无向树及生成树的基本概念2.难点：避圈法、最小生成树教学方法及手段1.讲授法2.互动式教学3.多媒体辅助教学教学互动环节设计1.课程回顾导入新课（特殊的图）2.启发式提问引发课堂讨论（对最小生成树的理解）课后总结与反思第7章树7.1无向树及生成树课程导入提出一个实际问题：“社会主义新农村”政策提出后，村村通、路路通即将实现，需要修建道路连通各个乡村，各道路长短花费不同，请问如何使花费最小？”引发学生思考，导入本节课主题。生成树定义：设G是无向连通图，T是G的生成子图并且是树，则称T是G的生成树。G在T中的边称为T的树枝，不在T中的边称为T的弦。T的所有弦的集合的导出子图称为T的余树。生成树的存在性定理：任何无向连通图都有生成树.证：用破圈法.若图中无圈,则图本身就是自己的生成树.否则删去圈上的任一条边,这不破坏连通性,重复进行直到无圈为止,剩下的图是一棵生成树.推论：设n阶无向连通图有m条边,则m>=n-1.基本回路与基本回路系统定义：设T是连通图G的一棵生成树,对每一条弦e,存在惟一的由弦e和T的树枝构成的初级回路Ce,称Ce为对应于弦e的基本回路.称所有基本回路的集合为对应生成树T的基本回路系统.性质：连通图中的任一条回路都可以表成对应它所含弦的基本回路的合并.基本割集与基本割集系统定义：设T是连通图G的一棵生成树,对T的每一条树枝a,存在惟一的由树枝a,其余的边都是弦的割集Sa,称Sa为对应树枝a的基本割集，称所有基本割集的集合为对应生成树T的基本割集系统.性质：连通图中的任一割集都可以表成对应它所含树枝的基本割集的对称差.无向图与最小生成树对无向图或有向图的每一条边e附加一个实数w(e),称作边e的权.图连同附加在边上的权称作带权图,记作G=<V,E,W>.设T是G的生成树,T所有边的权的和称作T的权,记作W(T).最小生成树:带权图权最小的生成树避圈法(Kruskal)——求最小生成树的算法(1)按权从小到大排列边(1)按权从小到大排列边(环除外),设W(e1)≤W(e2)≤…≤W(em).(2)令T,i1,k0.(3)若ei与T中的边不构成回路，则令TT{ei},kk+1.(4)若k<n-1,则令ii+1,转(3).例求图的一棵最小生成树贪心法(Prim算法)——求最小生成树的算法问题：给定连通带权图G=(V,E,W)，w(e)ÎW是边e的权.求G的一棵最小生成树。村村通问题可以简化为一个最小生成树的问题。思政目标：无向树具有连通且无回路的特性，其每一个顶点和边都相互关联、不可或缺，如同集体中的每个成员，只有紧密协作才能维持整体的稳定与功能。在生成树的构建过程中，学生通过参与算法实践，如普里姆算法或克鲁斯卡尔算法，需要团队成员各司其职、相互配合，共同完成最小生成树的求解。这有助于学生理解个人在集体中的责任与价值，培养集体荣誉感，强化团结协作意识，树立集体主义价值观。算法思想：输入：图G=(V,E,W),V={1,2,…,n}输出：最小生成树T设计思想：初始S={1}，T=∅选择连接S与V-S集合的权最短边e