《离散数学（微课版第2版）》教案全套 第1-11章 命题逻辑-教案 - -特殊图、树及习题课

第32次课授课单元（章节）第9、10、11章图论综合复习与习题课授课学时2授课类型讲授课（）实践课（）其它（√）习题课授课周次教学目标知识目标贯通第9章图的基本概念及矩阵表示、第10章特殊图、第11章树，梳理定义、定理前提与算法适用条件，能够辨认常见错误命题。能力目标1.能由度与邻接矩阵分析图结构及连通性；选择适当条件判断欧拉图、哈密顿图、匹配和平面图，并检验网络流。2.能应用树的性质、Kruskal算法和最优二叉树构造方法求解问题，区分最短路径、最小生成树与最大流的不同目标。3.能用反例、可行构造或最优性依据纠正错题，完成树的遍历与结果核验，形成跨章节的解题方法。素质与课程思政目标结合物流运输与通信网络建设，培养节约资源、服务社会的责任意识；通过独立解答、同伴互评和如实订正，形成尊重事实、严谨论证的学习态度。达成评价采用板演、同伴纠错与6题出口检测，分别覆盖图的表示、条件辨析和树的算法；依据过程记录与分题得分安排补练，不预设目标已达成。教学重点、难点教学重点度与矩阵表示、连通性；特殊图判定与匹配、平面图和网络流；树的性质、最小生成树、最优二叉树及遍历。教学难点区分矩阵幂计数的路与基本路径；识别定理前提；比较三类优化目标；避免Kruskal选边成环和最优二叉树合并后未重新排序。突破方法每题统一采用“识别模型—列出条件—选择方法—实施求解—验证结论”的步骤，教师依据学生作业中的真实错误调整追问。教学方法1.诊断复习：先让学生判断命题并解释，再针对共性错误讲解。2.练讲结合：学生先做、代表板演、同伴指出缺失前提，教师补充关键证明。3.变式训练：对同一模型改变参数或约束，比较解法和结果为何改变。教学手段教材第9章习题（印刷页193—197）、第10章习题（228—231）、第11章习题（245—247）；三章课堂摘要、错题记录、矩阵计算单与树形图练习单。教学内容一三章知识框架与诊断第9章回答“图怎样描述与计算”：节点、边、度、同构、连通性及矩阵表示；第10章回答“特定约束怎样判定与求解”：遍历、匹配、平面图和网络；第11章回答“怎样无环连通与组织信息”：树、生成树、最优二叉树及遍历。诊断命题：“度数全偶必是欧拉图”“有n−1条边必是树”“最小生成树给出任意两点最短路”。三句均不能无条件成立：前两句缺少连通等前提，第三句混淆整体连通成本与两点路径目标。二第9章图的基本概念与矩阵表示题组1度数与矩阵计数教材第9章第4题：8个节点中有3个3度节点、2个2度节点、3个1度节点。由握手定理，度数和为3×3+2×2+3×1=16，故边数为8。提醒：无向图的自圈对度数贡献2。教材第9章第27题：按节点v₁、v₂、v₃、v₄的次序，邻接矩阵各行为(0,1,0,1)、(1,0,1,1)、(0,1,0,0)、(1,1,0,0)。行和得d(v₁)=2、d(v₂)=3；缺少边v₁v₃、v₃v₄，所以不是完全图。由邻接矩阵的普通乘法，A³第1行第2列为4。对应长度为3的路为v₁-v₂-v₁-v₂、v₁-v₂-v₃-v₂、v₁-v₂-v₄-v₂、v₁-v₄-v₁-v₂。矩阵幂计数允许重复节点和边，不能直接解释为基本路径条数。连通性复练：该无向图的4个节点在同一分支，故连通。可达性只看是否存在路径，矩阵布尔运算与普通计数运算须区分；有向图则还须逐对检查方向，不能把弱连通当成强连通。三第10章特殊图与网络题组2遍历条件与分配约束教材第10章第8题：若图有割点v，则删去v后至少有两个分支。假设存在哈密顿回路，删去v后剩余节点仍由一条路径连通，矛盾。用共享一点的两个三角形说明：有欧拉闭路不保证有哈密顿回路。教材第10章第17题：张明懂物理、电工；王同懂数学、计算机科学；李林懂数学、物理、电工；赵丽只懂电工。可安排赵丽—电工、张明—物理、李林—数学、王同—计算机科学，逐边核验资格且端点不重复。变式：若赵丽、张明都只懂电工，则这两人的邻集仅含一门课，违反Hall条件。诊断“人人有选择就能全部匹配”和“极大匹配必为最大匹配”，要求给出局部障碍或反例。题组3平面图与网络核验教材第10章第18题：r×r小正方形网格有n=(r+1)²个节点、m=2r(r+1)条边、f=r²+1个面，含无限面，满足n−m+f=2。取r=2得n=9、m=12、f=5；联系每面一个对偶节点，提醒四色定理是“至多四色”。复用第30次课网络：s→a容量3、s→b容量2、a→b容量1、a→t容量2、b→t容量3。按上述次序给流量(3,2,1,2,3)，逐点核对容量与守恒，流值5等于源点割容量5，故为最大流。追问：某弧容量8、已有流量5时，正向残量为3、对应反向残量为5；反向调整表示撤回已有分配。只给源点总容量是上界，必须有可行流达到它，才能据此判定最大值。四第11章树及其应用题组4树的性质与最小生成树教材第11章第10题：设n₂、n₃、…、nₖ分别为树的2、3、…、k度节点数，树至少有2个节点。设叶节点数为x，联立度数和与边数等于节点数减1，得x=2+n₃+2n₄+…+(k−2)nₖ。例如两个2度、一个3度、三个4度内点的树有9个叶节点。树的判定：对无向图，“连通且边数为n−1”或“无环且边数为n−1”均可推出是树。反例C₃加一个孤立点虽有4个节点、3条边，却不连通且有环，说明仅有边数条件不够。最小生成树练习（自编）：无向带权图节点a、b、c、d，边及权为ab(1)、bc(2)、ac(3)、cd(4)、bd(5)、ad(6)。Kruskal依次选ab、bc，跳过成环的ac，再选cd，得到3条边、总权7。检查覆盖全体节点、连通且无环。最优性说明：逐轮选择连接不同分支的最小权边，符合Kruskal安全选边规则。该树中a到d的路径权为7，而原图直接边ad的权为6，说明最小生成树不能代替最短路径算法。题组5最优二叉树与遍历最优二叉树练习（自编）：叶权为2、3、7、8。每轮合并当前最小的两项：2+3=5，5+7=12，8+12=20。叶节点加权路径长度为5+12+20=37。每次合并后须把新权放回待选集合。一种前缀编码：权8对应0，权7对应11，权2对应100，权3对应101；加权码长8×1+7×2+2×3+3×3=37。检查无一个码字是另一完整码字的前缀；左右分支对调可得到不同但同样最优的编码。遍历练习（自编）：根A的左、右孩子为B、C；B的左、右孩子为D、E；C仅有右孩子F。前序为ABDECF，中序为DBEACF，后序为DEBFCA。按“根的位置”核验，不以图上从左到右的扫描代替遍历。五跨章应用与课程思政以物流与通信网络为线索：第9章描述节点关系并检查可达性，第10章处理巡检、匹配与容量约束，第11章求低成本连通结构和高效编码。要求学生先说明目标与约束，再选择算法，把节约资源与保障服务落实到可核验的方案。六综合检测与反馈出口检测6题，每题2分：①无向图度数和为16时有几条边；②邻接矩阵A³的元素是否只计基本路径；③两个不相交三角形的所有节点度均为2，是否有覆盖全图的欧拉闭路；④连通无向图有6个节点、5条边，是否为树；⑤上述带权图的最小生成树总权是多少；⑥叶权2、3、7、8的最优二叉树加权路径长度是多少。参考答案：①8条，握手定理；②不是，允许重复；③没有，全图不连通；④是，连通且边数为节点数减1；⑤7，选ab、bc、cd；⑥37，合并权依次为5、12、20。每题结论与关键理由各1分，总分12分。课堂归纳：模型清楚才能选方法，条件满足才能用定理；构造结果须核验，声称最优须说明依据。依据第1—2题、第3题、第4—6题及课堂记录，分别定位三章的薄弱环节。教学设计及时间安排教学设计时间分配（分钟）（一）复习及提问学生按“图的描述—特殊图—树与优化”补全知识清单，教师依据三章作业各选一项共性错误。5（二）问题引入以物流网络提出“能否到达、怎样覆盖、如何低成本连通”三个问题，明确模型、约束与所求目标，辨析诊断命题。5（三）习题讲解第9章15分钟：度数3分钟、矩阵与连通性12分钟；第10章20分钟：遍历判定5分钟、匹配5分钟、平面图4分钟、网络流6分钟；第11章25分钟：树的性质4分钟、最小生成树8分钟、最优二叉树8分钟、遍历5分钟。各题先短时尝试再讲关键步骤。60（四）融入课程思政设计在物流运输与网络建设题中讨论节约资源与服务需求，引导学生解释模型的约束和最优性依据；同伴互评须如实记录错误。用三章知识共同支撑可靠工程决策。3（计入习题讲解）（五）互动与检测两人互查矩阵计数与树的构造4分钟；完成6题出口检测6分钟；教师按三章知识模块反馈并安排补练5分钟。15（六）课堂小结与作业归纳“识别模型—核查条件—选择方法—求解—验证”流程，比较最短路、最小生成树、最大流；布置三章订正和期末图论专题复习。5课后作业或思考题必做：提交第9、10、11章错题订正单，逐题写出原错误、正确依据和规范步骤。教材第9章第4、27题，第10章第8、17题，第11章第10、11题中已完成且正确者只补写验证，错误或未完成者重新解答。巩固：完成本课最优二叉树与遍历练习，记录每轮合并及遍历次序；订正第10章第24题，逐轮核查容量、守恒及等值割。提高：选做教材第9章第30题、第10章第26或27题、第11章第18或20题。整理最短路径、最小生成树和最大流的目标、约束与结果验证方法，不再安排第11章初次预习。教学总结与反思课后填写：出口检测平均分____；第1—6题得分率____；第9、10、11章各需补练的知识点____。观察重点：矩阵计数是否混淆路径类型；判定是否漏条件；Kruskal是否避环；最优二叉树是否每轮合并当前最小权；能否解释可行与最优的差别。改进预案：图的表示薄弱者补练第9章第27、30题；特殊图判定或网络薄弱者补练第10章第8、17、24题；树与算法薄