《离散数学（微课版第2版）》 第10、第11章 特殊图、树及习题课-教案

________________（学校）教案第10章特殊图课程名称：离散数学课程编号：任课教师：任课专业：任课学年学期：院系（部）：教务处制（2026年）注意事项和要求教案是任课教师的教学实施方案。任课教师应遵循专业培养方案制订的培养目标、毕业要求，严格按课程教学大纲编写，体现OBE理念，落实课程思政要求，并根据经济社会发展及学校人才培养要求及时增加和补充前沿内容，一、教案主要内容（一）课程概况：课程名称、课程编码、课程类型、考核方式、推荐教材及参考书目、教学目标、课程思政目标、教学重难点等。以上课程信息内容必须同培养方案及教学大纲保持一致。（二）课程教案：包括授课单元（章节）、授课学时、授课类型、授课周次、教学目标、教学重点难点、教学方法、教学手段、教学内容、教学设计、课后作业、教学反思、备注等。二、编写注意事项（一）教学目标：可从知识目标、能力目标、素质目标等多维度进行设定，从有利于学生发展的角度去思考，既要符合课程和教材的要求，更要符合学生先修基础和认知规律。目标要切实可行，可操作、可检测。（二）教学重点、难点：指本次课的重点和难点部分，学生必须掌握的知识点和技能。实践教学还包括实践操作训练的主要指导要点、关键环节、关键技术指导方法等。（三）教学方法：主要包括讲授法、讨论法、练习法、归纳法、演示法、启发法、实验法等。（四）教学手段：指课堂教学中师生教学相互传递信息的工具、媒体或设备，可以包括备课本、教材、模型、图表、黑板、电脑、多媒体课件、线上教学平台等，实践教学包括所用到的实践仪器设备。（五）教学内容：依据人才培养方案、教学大纲对课程教学内容的要求，扩充填写本次课的主要传授知识内容，可以用图表或知识网络图表达，并在适当内容处有机融入课程思政元素。（六）教学设计：是课堂教学的总体设计安排，可供参考（但不限于）教学设计选项有：考勤点名、作业反馈、复习旧课、导入新课、新课内容、课后小结、知识拓展、布置作业等，具体可视实际教学内容安排以上某些选项组成该堂课的教学设计，实践课的教学设计还可补充实践步骤或实践流程。不同专业，其课堂教学设计也可有不同特色。（七）课后作业或思考题：应根据本次课的教学目标要求进行布置，可以形式多样，应体现一定的高阶性、创新性和挑战度，在复习本次课的同时，注意引导学生积极开展预习。（八）教学总结与反思：填写课程教学支撑教学大纲相应课程目标、毕业要求指标点的情况、经验教训、效果估计、学生学习状态分析和存在问题等，也可以填写创新点或特色等内容（九）备注：用于批注教学过程中用到的教学方法或启发学生思维的实际案例，或实践教学中的注意事项等。二、课程教案第31次课授课单元（章节)第11章树授课学时2授课类型讲授课(√)实践课()其它()授课周次第16周教学目标知识目标：1.掌握树（自由树形、无根树形）的定义，理解叶结点（悬挂结点）、内结点（分枝结点）、叶边（悬挂边）等基本术语。2.掌握关于树的五个等价命题及其证明思路，掌握引理F及其证明。3.掌握森林的定义，掌握“森林F有n个结点、m条边和k个分支时m=n−k”的定理。4.掌握生成树、基本循环的秩、弦和枝的概念，理解生成树不唯一。5.掌握加权长度、最小生成树的概念，掌握Kruskal算法（避圈法）。6.掌握有向树、根、叶、分支结点、级和高度的定义，掌握“D是以v0为根的有向树当且仅当从v0至D的任意结点恰有一条路径”的定理。7.掌握有向森林、m元有向树、完全m元有向树、正则m元有向树和二叉树的定义。8.掌握叶加权二叉树、叶加权路径长度的概念，掌握最优二叉树的定义与求解方法。9.掌握有向有序树、位置有向有序树、前缀编码的概念，掌握有向有序森林与位置二元有向有序树之间的自然对应关系。10.掌握二元树的存储结构与前序、中序、后序三种周游的递归定义及前序、后序周游算法的思想。11.了解搜索树的构造与剪枝思想（取火柴游戏、4×4棋盘放棋子问题），了解深度优先搜索（DFS）算法和Dijkstra算法。12.了解树与最小生成树在图像分割、句法分析、博弈智能等领域的应用。能力目标：1.能够判定一个无向图是否为树，并能运用树的等价命题进行推理与证明。2.能够求给定连通图的生成树，计算基本循环的秩并指出其中的弦与枝。3.能够运用Kruskal算法求加权连通图的最小生成树。4.能够判定有向图是否为有向树，并指出它的根、叶、分支结点和高度。5.能够根据给定的一组权构造最优二叉树，并计算叶加权路径长度。6.能够写出位置二元有向有序树各结点的编码及其前缀编码，能够完成有向有序森林与位置二元有向有序树之间的相互转化。7.能够对给定的二元树写出前序、中序、后序周游所得到的结点序列。素质目标：1.体会树是计算机科学中应用最广泛的一类特殊图，理解从实际图问题中提炼树结构、把图的算法转化为树的算法的建模思想。2.通过最优二叉树的构造过程，体会贪心策略与分步归约的算法设计思想，培养算法思维和优化意识。3.通过搜索树的剪枝过程，体会“减少无效搜索”对提高问题求解效率的重要意义。课程思政目标：1.【科学方法】通过基尔霍夫1847年提出生成树思想雏形、克鲁斯卡尔1956年提出最小生成树算法的历史，引导学生体会“抽象建模——从现实问题到数学结构”的思路，认识基础研究具有的长远价值，学习科学家敢于挑战基础理论问题、勇于创新的科学精神。2.【工程素养】通过Kruskal算法和最优二叉树构造方法的学习，引导学生体会算法设计追求简洁与高效的目标，树立理论与实践相结合、把数学方法用于解决实际问题的意识。3.【青年使命】通过最小生成树在图像分割、有向树在句法分析、搜索树在博弈智能（MCTS、AlphaGo）中的应用，引导学生认识基础理论在人工智能等前沿领域的关键作用，增强创新自信和时代担当，立志为科技强国建设贡献力量。教学重点、难点1.教学重点：（1）树的定义及关于树的五个等价命题；森林中结点数、边数与分支数的关系m=n−k。（2）生成树、基本循环的秩、弦与枝的概念；用Kruskal算法求最小生成树。（3）有向树的定义及“以v0为根的有向树当且仅当从v0至任意结点恰有一条路径”的定理。（4）叶加权路径长度与最优二叉树的构造方法。（5）有向有序森林与位置二元有向有序树之间的自然对应关系；前缀编码。（6）二元树的前序、中序、后序三种周游。2.教学难点：（1）关于树的五个等价命题的证明，特别是(2)⇒(3)的证明和引理F的应用。（2）基本循环的秩的理解——为什么在求得生成树之前需删除的边数是m−(n−1)。（3）最优二叉树的构造方法——如何把求m片叶的最优二叉树归结为求m−1片叶的最优二叉树。（4）位置二元有向有序树的编码规则及前缀编码的理解。（5）前序周游与后序周游算法的栈操作过程。教学方法1.讲授法：系统讲解树与生成树、有向树及其应用的概念体系和算法，确保知识体系的完整性和逻辑性。2.案例教学法：以冬季道路扫雪问题说明最小生成树的应用背景；以取火柴游戏说明搜索树与极小极大原理；以4×4棋盘放棋子问题说明搜索树的剪枝思想。3.演示法：现场演示Kruskal算法的执行过程、最优二叉树的构造过程和二元树三种周游的过程。4.对比教学法：对比无向树与有向树、生成树与最小生成树、完全m元有向树与正则m元有向树、前序与中序与后序周游等概念。5.启发式教学法：通过“为什么n个结点的树恰有n−1条边”“如何用最少的雪保证道路畅通”“怎样设计判断次数最少的识别算法”等问题引导学生主动思考。教学手段1.多媒体课件：展示PPT内容，包括树的图示、五个等价命题的证明思路、生成树与弦的示意、Kruskal算法演示、最优二叉树的分步归约过程、位置二元有向有序树及其编码、二元树三种周游示例、搜索树与剪枝过程等，增强教学的直观性。2.板书：板书Kruskal算法的执行步骤，以表格形式记录最优二叉树每次归约后的权序列，板书二元树三种周游的递归定义，突出核心概念与算法流程。3.线上教学平台辅助：提前将课程相关参考资料和预习任务上传到教学平台上，供学生预习和课后复习。教学内容一、导入新课说明树是在计算机科学中应用最广泛的一类特殊图，本章学习树及其性质、生成树与最小生成树、有向树及其应用三部分内容。回顾前面学过的连通性、回路等概念，指出树就是“没有回路的连通无向图”；并说明生成树、最优二叉树、搜索树等结构都与计算机算法和数据结构密切相关，本章内容在后续专业课程中有广泛的应用。二、新课内容11.1树与生成树11.1.1树及其性质1.树的定义与基本术语（1）自由树形（无根树形）：没有回路的连通无向图。由定义可以看出，树是一个简单图，没有自环，没有平行边。（2）叶结点（悬挂结点）：树中度为1的结点；内结点（分枝结点）：度数大于1的结点；叶边（悬挂边）：与叶结点（悬挂结点）所关联的边。2.关于树的等价命题（定理）如果G是一个无向图，则下列命题等价：（1）G是一个自由树形；（2）G是连通的，但若删去任何一条边，则所得图形就不再连通；（3）对于G的两个不同结点v和v′恰有一条从v到v′的基本通路。又当G有限时，记G的结点数为n>0，则下列命题也与前诸命题等价：（4）G不含回路而且有n−1条边；（5）G连通而且有n−1条边。3.等价命题的证明思路（1）(1)⇒(2)：倘若删去边{v,v′}后G仍然连通，则按连通性定义有通路从v到v′；取其中最短者即得基本通路，这条通路的长度≥2，于是该通路连同边{v,v′}将是G中的一条回路，与自由树形的定义矛盾。（2）(2)⇒(3)：G连通故从v到v′有通路，取最短者即得一条基本通路；再证最多有一条这样的基本通路——倘若有两条从v到v′的基本通路(vv1…vi…v′)和(vv1′…vi′…v′)，则自左而右可找到最小的k≥1使vk≠vk′，这样从G中删去边{vk−1,vk}后仍将是连通图形（因为从vk−1到vk还有通路(vk−1vk′…v′…vk)），这与(2)所设矛盾。（3）(3)⇒(1)：既然恰有一条基本通路从v到v′，故G自然连通；再证G无回路——倘若G有回路C，则从v到v1将有两条基本的通路(vv1…v′…v)和(vv1)（或(v…v′…v1)），与(3)矛盾。（4）引理F：设G为任意有限图形，G无回路但至少有一边，则至少有一个结点恰好相邻于别的一个结点。证明：既然G至少有一条边，故可取一结点v1以及v1的一个相邻结点v2；从v1出发依次考察v2、v3、…，对于k≥2，或者vk只与vk−1相邻（从而即为所求者），或者vk又相邻于别的结点vk+1≠vk−1。如此类推得一串结点v1,v2,…,vk−1,vk,vk+1,…。既设G无回路，这一串结点不能重复；但G有限，故以上过程必停止于有限步，即最终可得一结点只与前一结点相邻。（5）(1)⇒(4)：对图的结点数用归纳法。n=1时显然成立；设n−1时成立，往证n时亦成立。利用引理F命vn为恰有一相邻结点vn−1者，删去vn和边{vn−1,vn}得一新图形G′。G′有n−1个结点，而且无回路还连通——这是因为vn只有一个相邻结点，故vn不能出现在G的任何一个结点到另一个结点的基本通路的中间处，至多只能出现在两端的端点处。根据(3)与(1)的等价性知G′仍是自由树形，按归纳假设G′有(n−1)−1=n−2条边，所以G有(n−2)+1=n−1条边。（6）(4)⇒(5)：还是对结点数n>0使用归纳法。仿前一段证明，利用引理F删去vn和{vn−1,vn}得G′，G′有n−1个结点、n−2条边且无回路，按归纳假设G′连通；由于把{vn−1,vn}和vn添加到G′之后，G中任何两结点之间仍必有通路（必要时取道(vn−1,vn)），故G连通。（7）(5)⇒(1)：即设G有n>0个结点、n−1条边且连通，要证G无回路。设G含有一个回路，则删去回路上任何一条边后所得的图形仍连通；用这种方法不断地删去一些边，最后得出一个图形G′仍连通，G′具有n−1−k条边且无回路，即G′为一自由树形；由已证的(1)蕴含(4)的事实，G′有n−1条边，可见k=0，也就是说G中原来就无回路。4.森林（1）定义：每个分支都是树的无向图称为森林。树是非循环连通无向图，如果去掉对连通性的要求，就得到森林的概念。（2）定理：如果森林F有n个结点、m条边和k个分支，则m=n−k。11.1.2生成树1.生成树的定义与求法（1）推论1：任何有限连通图G必有一结点数相同的自由子树形，或称G的生成树，记作T_G。事实上，根据(2)，尽可能地删去一条条边，即得一自由树形。（2）如果给定的图G是一个(n,m)连通图，根据(5)知，生成树是个(n,n−1)图；因而在求得T_G之前应该删除的边数是m−(n−1)。这个数也称为给定图G的基本循环的秩——它是为了打断它的所有基本循环时，必须从G中删除的边数。（3）每一条被删除的边都称作G的弦，T_G中的边称为枝。生成树不唯一。（4）例：求(6,9)无向图G1的生成树。生成树T_G有6−1=5条边；G的基本循环的秩等于弦的数目，为9−(6−1)=4。2.最小生成树与Kruskal算法（1）定义：设<G,W>是个加权图，G′⊆G，G′中所有边的加权长度之和称为G′的加权长度。设G是连通无向图，<G,W>是加权图，G的所有生成树中加权长度最小者称为<G,W>的最小生成树。（2）Kruskal算法（1956）——避圈法：设G是有m条边的n阶连通无向图，首先把G的m条边排成加权长度递增的序列e1,e2,…,em，然后依次考察每条边：若当前边加入后不构成回路则保留，否则舍弃。算法结束时所得的边的集合T即为所求的最小生成树的边的集合。它的本质是树生成过程，因此得名避圈法。（3）应用实例——道路扫雪问题：在冬天里经常下雪，保持道路畅通的唯一方式就是经常扫雪。高速公路部门希望只扫尽可能少的道路上的雪，而确保总是存在连接任何两乡镇的干净道路。这一问题即归结为求道路系统所对应的加权图的最小生成树。11.2有向树及其应用1.有向树（1）定义：一个结点的入度为0、其余结点的入度均为1的弱连通有向图，称为有向树。（2）基本术语：入度为0的结点称为根，出度为0的结点称为叶，出度大于0的结点称为分支结点，从根至任意结点的距离称为该结点的级，所有结点的级的最大值称为有向树的高度。（3）定理：设v0是有向图D的结点，则D是以v0为根的有向树，当且仅当从v0至D的任意结点恰有一条路径。（4）证明思路：必要性——因D弱连通，取v′∈V，从v0至v′存在半路径v0e1v1…epvp（vp=v′）；由d⁻(v0)=0知e1是正向边，由d⁻(v1)=1知e2是正向边，可归纳证明ep是正向边，故存在从v0至v′的路径；若从v0至v′有两条路径P1和P2，则P1和P2的公共点（v0除外）的入度为2，与D是有向树矛盾。充分性——显然D是弱连通的；若d⁻(v0)>0则存在以v0为终点的边e，设v1是e的起点、P是从v1至v0的路径，则在D中存在两条从v0至v0的路径，矛盾，故d⁻(v0)=0；若d⁻(v)>1，则存在两条边e1和e2以v为终点，设起点分别是v1和v2，从v0至v1和v2的路径分别是P1和P2，则P1v1e1v和P2v2e2v是两条不同的从v0至v的路径，矛盾。2.m叉树（m元有向树）（1）有向森林：每个弱分支都是有向树的有向图，称为有向森林。（2）m元有向树：设m∈N，D为有向树；如果D的所有结点的出度的最大值为m，则D称为m元有向树。（3）完全m元有向树：如果对于m元有向树的每个结点v，都有d⁺(v)=m或d⁺(v)=0，则称D为完全m元有向树。（4）正则m元有向树：若所有的叶结点的级相同，则称正则m元有向树。（5）二叉树：完全二元有向树也称二叉树，在计算机科学中最有用。3.叶加权二叉树与最优二叉树（1）叶加权二叉树：设V是二叉树D的叶子的集合，R⁺是全体正实数的集合，W:V→R⁺，则称<D,W>为叶加权二叉树。对于D的任意叶v，W(v)称为v的权。（2）叶加权路径长度：称Σ(v∈V)W(v)·L(v)为<D,W>的叶加权路径长度，其中W(v)是叶子v的权，L(v)为v的级。（3）应用意义：用叶子表示字母或符号，用分支结点表示判断，用权表示字母或符号出现的几率，则叶加权路径长度就表示算法的平均执行时间——把求某问题的最佳算法就归结为求最优二叉树的问题。（4）例：某问题有两个识别算法，出现概率分别是0.5、0.3、0.05、0.15。算法(a)的叶加权路径长度为2×(0.5+0.3+0.05+0.15)=2，算法(b)的叶加权路径长度为1×0.5+2×0.3+3×(0.05+0.15)=1.7，故算法(b)更优。（5）最优二叉树：设<D,W>是叶加权二叉树，如果对于一切叶加权二叉树<D′,W′>，只要对于任意正实数r，D和D′中权等于r的叶的数目相同，就有<D,W>的叶加权路径长度不大于<D′,W′>的叶加权路径长度，则称<D,W>为最优的。（6）求最优二叉树的方法：假定要找出有m片叶、权分别为w1,w2,…,wm（按递增顺序排列，即w1≤w2≤…≤wm）的最优二叉树。设<D,W>是满足要求的最优二叉树，D中以w1,w2,…,wm为权的叶分别为v1,v2,…,vm。显然在所有叶中v1和v2的级最大，且不妨设v1和v2与同一个分支结点邻接。令D′=D−{v1,v2}，W′:{v′,v3,v4,…,vm}→R⁺，并且W′(v′)=w1+w2，W′(vi)=wi，则<D,W>是最优的，当且仅当<D′,W′>是最优的。这样就把求m片叶的最优二叉树归结为求m−1片叶的最优二叉树；继续这个过程，直到归结为求两片叶的最优二叉树，问题就解决了。（7）例：求叶的权分别为2、3、9、18、23、29的最优二叉树。构造过程中每次归约后的权序列依次为：2,3,9,18,23,29→5,9,18,23,29→14,18,23,29→23,29,32→32,52→84。4.有序树（1）有向有序树：为每一级上的结点规定了次序的有向树，称为有向有序树。如果有向森林F的每个弱分支都是有序树，并且为F的每个弱分支也规定了次序，则称F为有向有序森林。画有序树时约定总是把根画在上部，同一级上结点的次序是从左至右的；在画有序森林时，弱分支的次序也是从左至右的。（2）应用：可以用有向有序树表达算术表达式，其中叶表示参加运算的数或变量，分支结点表示运算符。（3）家族树的称呼：为方便起见，借用家族树的名称来称呼有向有序树的结点，如父亲、长子、哥哥、弟弟、伯父、堂兄等。（4）位置有向有序树：为每个分支结点的儿子规定了位置的有向有序树，称为位置有向有序树。（5）位置二元有向有序树的表示方法：可用字母表{0,1}上的字符串唯一地表示每个结点。用空串ε表示根；设用β表示某分支结点，则用β0表示它的左儿子，用β1表示它的右儿子。例如ε,0,1,00,10,11的编码。位置二元有向有序树全体叶的编码表示的集合称为它的前缀编码。（6）有向有序森林与位置二元有向有序树的转化：二者之间可以建立一一对应关系。在有向有序森林中，称位于左边的有向有序树的根为位于右边的有向有序树的根的哥哥。设F为有向有序森林、T为对应的有向有序树，则：在F中若v1是v2的长子，则在T中v1是v2的左儿子；在F中若v1是v2的大弟，则在T中v1是v2的右儿子。这种对应关系称为有向有序森林和位置二元有向有序树之间的自然对应关系。5.二叉树的遍历（1）二元树的存储：如果一个实际问题可以抽象成一个图，则可以将这个图转化成树（求这个图的生成树），而对任何一棵树都可以转化成与其对应的二元树。利用连接分配技术可以方便地表示二元树，其中所包含的结点结构为LLINK、DATA、RLINK——LLINK或RLINK分别包含一个指向所论结点的左子树或右子树的指针，DATA包含与这个结点有关的信息。（2）二元树的三种周游：前序周游：处理根结点→按前序周游左子树→按前序周游右子树；中序周游：按中序周游左子树→处理根结点→按中序周游右子树；后序周游：按后序周游左子树→按后序周游右子树→处理根结点。（3）前序周游算法（PREORDER）：给定一棵二元树，它的根结点地址是变量T，结点结构与上面描述的相同，本算法按前序周游这棵二元树。利用一个辅助栈S，S的顶点元素的下标是TOP，P是一个临时变量，表示我们处在这棵树中的位置。算法的四个步骤为：①置初态；②访问结点P，右分枝地址进栈，并转左；③链结束否；④右分枝地址退栈。（4）后序周游算法（POSTORDER）：在后面序周游算法中，每一个结点将进栈两次——一次是当周游它的左子树时，另一次是当周游它的右子树时；这两种周游完成时就处理这个被考虑的结点。因此必须能区别两种类型的栈元素，第一种类型的元素采用负指针值（这里假设实际使用的指针数据总是非零并且是正的）。6.搜索树（1）搜索树——取火柴游戏：设有n根火柴，甲乙两人依次从中取走1或2根，但不能不取，谁取走最后一根谁就是胜利者。不妨设n=6，用树表示轮流取火柴时的各种状态。显然一当出现只剩1根或2根的状态，轮到取的一方便取胜，不必再搜索下去。约定甲取胜时其得分为1、乙取胜时甲的得分为−1；则轮到甲作出判决时，他一定选取最大值，而轮到乙作出判决时，他会选取使甲失败的最小值。据此可以逐层确定甲应当取的火柴数。（2）深度优先搜索（DFS）算法（图的遍历算法）：①当E(G)的所有边未经完全搜索时，任取一结点vi，给vi以标志且入栈；②对与vi点关联的边依次进行搜索，当存在另一端点未给标志的边时，把另一端点作为vi，给以标志并且入栈，转②；③当与vi关联的边全部搜索完毕时（即不存在以vi为端点而未经搜索的边时），则让vi从栈顶退出，即让取走vi后的栈顶元素作为vi，转②；④若栈已空但还存在未给标志的结点时，取其中任一结点作vi，转②；若所有结点都已给标志，则算法终止。（3）搜索树的剪枝——4×4棋盘放棋子问题：设有一个4×4的棋盘，当一个棋子放到其中一个格子里去以后，则这格子所在的行、列以及对角线上所有的格子都不允许放别的棋子。现在有四个棋子，问在棋盘上有哪几种容许的布局。用树表示所有可能的状态并对树进行搜索：一旦某结点被判定为不被容许，这个结点下的树枝可以全部剪去，从而大大减少搜索量。（4）Dijkstra算法：Dijkstra算法是典型的最短路算法，用于计算一个结点到其他所有结点的最短路径；主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。它能得出最短路径的最优解，但由于它遍历计算的结点很多，所以效率较低。应用与拓展（1）最小生成树在图像分割中的应用：在图像分割中，最小生成树（MST）将图像建模为加权图——像素为节点，相邻像素之间的边权表示颜色或纹理差异。Felzenszwalb和Huttenlocher提出的MST分割算法通过构建最小生成树，并比较区域内部差异与区域间差异来决定是否切断边，从而得到内部一致、边界清晰的区域。由于无需固定阈值，该方法具有良好的自适应性，并常用于超像素生成或视觉算法的预处理，在医学影像和点云处理等任务中可降低计算复杂度并提升后续分析效率。（2）有向树在句法分析中的应用：在自然语言处理的语法分析中，依存句法树是一种有向树结构，用于表示句子中词语之间的语法关系。句子中的词作为节点，通过有向边连接形成无环、连通的树，每个词只有一个父节点。现代依存句法分析通常利用神经网络对词间关系进行评分，再通过最大生成树等图算法生成满足树约束的最优结构，为关系抽取和情感分析等任务提供重要的结构信息。（3）搜索树在博弈智能中的应用：在决策智能与博弈对抗中，搜索树（如m叉博弈树）用于表示序列决策过程——节点表示状态，分支表示可选动作。由于搜索空间巨大，蒙特卡洛树搜索（MCTS）通过选择、扩展、模拟和回传等步骤集中探索高价值分支，从而在有限计算资源下获得近似最优决策。现代方法如AlphaGo将神经网络与搜索树结合，利用策略和价值评估引导搜索，大幅提升了复杂决策问题的效率。历史人物与事件（1）生成树思想的起源——基尔霍夫（GustavRobertKirchhoff）：德国物理学家、电路理论奠基人、光谱学创始人之一，21岁提出电路基本定律，1847年提出生成树思想雏形。基尔霍夫一生致力于教学与科研，《数学物理学讲义》成为德国高校经典教材；他提出的电路定律至今仍是电气工程基础，其生成树思想已成为计算机科学、运筹学与网络理论的重要工具。（2）克鲁斯卡尔算法的青年创新精神——约瑟夫·克鲁斯卡尔（JosephBernardKruskal）：美国数学家、统计学家，任职于贝尔实验室数学研究中心，1956年提出最小生成树算法，在多维尺度分析、序理论等领域亦有重要贡献。克鲁斯卡尔提出的最小生成树算法成为图论与算法设计的经典成果，其贪心策略为网络优化、工程规划与计算机系统设计提供了重要方法。三、课堂小结回顾本次课的核心内容：树的定义、基本术语与五个等价命题；引理F及其应用；森林及m=n−k；生成树、基本循环的秩、弦与枝；加权长度与最小生成树、Kruskal算法（避圈法）；有向树、根、叶、分支结点、级与高度；m元有向树、完全m元有向树、正则m元有向树与二叉树；叶加权路径长度与最优二叉树；有向有序树、位置有向有序树与前缀编码、有向有序森林与位置二元有向有序树的自然对应关系；二元树的存储结构与前序、中序、后序三种周游；搜索树（取火柴游戏、4×4棋盘问题）、DFS算法与Dijkstra算法；树在图像分割、句法分析、博弈智能中的应用；基尔霍夫与克鲁斯卡尔的历史贡献。强调：树是计算机科学中应用最广泛的一类特殊图，生成树、最优二叉树和搜索树等结构是算法设计与分析、数据结构、人工智能等后续课程的重要基础。教学设计及时间安排教学设计时间分配（分钟）（一）复习及提问1.考勤点名（2分钟）：通过线上教学平台签到或现场点名，确认学生出勤情况，记录考勤结果。提问“图论部分的连通性是用什么来判断的？什么是回路和基本回路？”，引导学生回顾图的基本概念，为本次课的学习做铺垫。2（二）课程引入2.课程导入（5分钟）：由“图论部分的最后一章学什么”入手，说明树是计算机科学中应用最广泛的一类特殊图——文件系统的目录结构、算术表达式的组织、程序的递归调用、博弈的决策过程都可以用树来描述；指出树就是n个结点的连通无回路图，并介绍本章的三部分内容：树及其性质、生成树与最小生成树、有向树及其应用。5（三）课程内容新课内容讲授（80分钟）：1.11.1.1树及其性质（20分钟）：（1）树的定义与基本术语（5分钟）：讲解自由树形（无根树形）的定义，说明树是简单图；讲解叶结点（悬挂结点）、内结点（分枝结点）和叶边（悬挂边）。（2）关于树的五个等价命题及证明思路（10分钟）：板书五个等价命题；重点讲清(1)⇒(2)、(2)⇒(3)、(3)⇒(1)三个证明和引理F的证明，再简要交代(1)⇒(4)、(4)⇒(5)、(5)⇒(1)的归纳证明思路，说明“多次用到引理F”这一特点。（3）森林及其边数定理（5分钟）：讲解森林的定义，推导并证明m=n−k，说明树是k=1的特例。2.11.1.2生成树（18分钟）：（1）生成树、基本循环的秩、弦与枝（6分钟）：讲解推论1及生成树的求法；讲解(n,m)连通图的生成树是(n,n−1)图，说明需删除的边数m−(n−1)即基本循环的秩，指出被删除的边为弦、保留的边为枝，并强调生成树不唯一；以(6,9)无向图G1为例计算。（2）最小生成树与Kruskal算法（8分钟）：讲解加权长度和最小生成树的定义；板书演示Kruskal算法（避圈法）的执行过程——把边按加权长度递增排序，依次选边并判断是否构成回路，保留或舍弃，直至得到n−1条边。（3）应用实例——道路扫雪问题（4分钟）：讲解如何把“只扫尽可能少的道路而保证任何两乡镇连通”这一问题转化为求最小生成树的问题，让学生体会数学建模的过程。3.11.2有向树及其应用（42分钟）：（1）有向树（8分钟）：讲解有向树的定义以及根、叶、分支结点、级、高度的概念；讲解“以v0为根的有向树当且仅当从v0至任意结点恰有一条路径”的定理及其必要性与充分性的证明思路。（2）m叉树与最优二叉树（12分钟）：讲解有向森林、m元有向树、完全m元有向树、正则m元有向树和二叉树的定义；讲解叶加权二叉树与叶加权路径长度，以两个识别算法（概率0.5、0.3、0.05、0.15）为例比较优劣，说明叶加权路径长度表示算法的平均执行时间；讲解最优二叉树的定义与构造方法，板书演示权2、3、9、18、23、29的完整归约过程。（3）有序树（8分钟）：讲解有向有序树与有向有序森林的定义及画法约定，说明用有向有序树可以表达算术表达式；讲解位置有向有序树，讲清用字母表{0,1}上的字符串为结点编码的规则及前缀编码；讲解有向有序森林与位置二元有向有序树之间“长子对应左儿子、大弟对应右儿子”的自然对应关系，并配合图示说明。（4）二叉树的遍历（6分钟）：讲解二元树用LLINK、DATA、RLINK的存储结构；讲解前序、中序、后序三种周游的递归定义，并以一棵具体的二元树演示三种周游所得到的结点序列；简介前序周游算法的栈操作过程。（5）搜索树（8分钟）：以取火柴游戏（n=6）讲解搜索树的构造和极小极大原理，说明如何由各状态的得分确定先取者应取几根；讲解深度优先搜索（DFS）算法的四个步骤；以4×4棋盘放棋子问题讲解搜索树的剪枝思想；简介Dijkstra算法及树在图像分割、句法分析、博弈智能中的应用。其中包含融入课程思政3分钟、课堂互动5分钟。80（四）融入课程思政设计融入课程思政设计（3分钟）：【科学方法】在讲解生成树和最小生成树时，介绍基尔霍夫1847年提出生成树思想雏形、克鲁斯卡尔1956年提出最小生成树算法的历史，引导学生体会“从现实问题到数学结构”的抽象建模过程，认识基础研究具有的长远价值，学习科学家敢于挑战基础理论问题、勇于创新的科学精神；【工程素养】通过Kruskal算法和最优二叉树构造方法的学习，引导学生体会算法设计追求简洁与高效的目标，树立理论与实践相结合、把数学方法用于解决实际问题的意识；【青年使命】结合最小生成树在医学影像处理、有向树在自然语言处理、搜索树在AlphaGo等博弈智能中的应用，引导学生认识基础理论在人工智能等前沿领域的关键作用，增强创新自信和时代担当，立志为科技强国建设贡献力量。3（包含在新课内容讲授的80分钟内）（五）互动环节设计互动环节设计（5分钟）：采用提问与讨论相结合的方式。提出问题——“为什么n个结点的树恰有n−1条边？请用握手定理说明。”“在道路扫雪问题中，为什么求得最小生成树就能保证扫雪的道路最少而又保证连通？”“最优二叉树在生活中的典型应用是什么？请举例说明。”“位置二元有向有序树中，结点的编码为什么不会出现一个是另一个前缀的情况？”组织学生简短讨论，邀请2-3名学生分享，教师点评，加深学生对树的结构和算法思想的理解。5（包含在新课内容讲授的80分钟内）课堂小结（3分钟）：梳理本次课核心知识点，明确重点和需掌握的内容，帮助学生构建知识框架。3课后作业或思考题一、简答题1.什么叫做树（自由树形）？什么叫做叶结点、内结点和叶边？2.试述关于树的五个等价命题，并说明(2)⇒(3)的证明思路。3.什么叫做森林？如果森林F有n个结点、m条边和k个分支，m与n、k之间有什么关系？4.什么叫做生成树？什么叫做基本循环的秩、弦和枝？它们之间有什么关系？5.什么叫做有向树？什么叫做根、叶、分支结点、级和高度？6.什么叫做m元有向树、完全m元有向树和正则m元有向树？7.什么叫做叶加权二叉树和叶加权路径长度？它在算法分析中有什么意义？8.什么叫做有向有序树和位置有向有序树？什么叫做前缀编码？9.有向有序森林与位置二元有向有序树之间的自然对应关系是怎样的？10.二元树的前序、中序、后序周游分别是按什么次序访问结点的？二、判断题（判断对错并说明理由）1.n个结点的树恰好有n−1条边。2.生成树是唯一的。3.在加权连通图中，最小生成树是所有生成树中加权长度最小者。4.有向树中除根以外的每个结点的入度都为1。5.完全m元有向树的每个结点的出度都等于m。6.在有向有序森林与位置二元有向有序树的对应中，森林中结点的长子对应该结点的左儿子。三、作图与计算题1.求下列连通图的生成树，写出它的基本循环的秩，并指出哪些边是弦、哪些边是枝。2.用Kruskal算法求下列加权连通图的最小生成树，并写出它的加权长度。3.判断下列有向图是否为有向树；若是，指出它的根、叶、分支结点和高度；若不是，说明理由。4.求叶的权分别为2、3、9、18、23、29的最优二叉树，并计算它的叶加权路径长度；再求叶的权分别为1、2、4、8、16、32的最优二叉树。5.写出下列有向有序森林所对应的位置二元有向有序树，并写出该二元树全体叶的编码所构成的前缀编码。6.已知一棵二元树，写出对它进行前序、中序和后序周游所得到的结点序列。四、拓展思考1.已知一棵二元树的前序周游序列和中序周游序列，能否唯一确定这棵二元树？如果能，请说明确定的方法。2.在取火柴游戏中（每次取1根或2根，取到最后一根者胜），n取哪些值时先取者必胜？试利用搜索树的思路说明理由。说明：第十一章“树”为图论部分的最后一章，本次课为该章的唯一一次课。教学总结与反思1.课程目标支撑情况：本次课系统讲授了树与生成树、有向树及其应用等内容，使学生掌握了树这一重要结构的数学基础，有效支撑了课程目标1（系统掌握数理逻辑、集合论、代数系统和图论的基本概念、基本理论和基本方法）；通过最小生成树、最优二叉树、搜索树等算法与应用的讲解，把理论方法与其在计算机科学中的实际应用紧密结合，支撑了课程目标2（运用图论的相关方法描述软件工程方法系统需求、系统架构和系统的实现方法）；课程思政环节融入科学方法、工程素养和青年使命教育，为课程目标3（树立社会主义核心价值观）奠定基础。2.教学效果估计：树的定义及五个等价命题中，(1)(2)(3)三个命题直观易懂，(4)(5)涉及归纳证明，部分学生可能跟不上；引理F的证明思路清晰，学生接受度应较好；生成树和基本循环的秩概念明确，计算难度不大；Kruskal算法步骤清晰，学生掌握情况应较好；有向树的定义和定理与无向树的结论形成对比，理解难度不大；最优二叉树的构造方法是本次课的难点，需要学生动手练习才能掌握；位置二元有向有序树的编码和森林与二元树的转化较为抽象，需借助图示反复说明；二元树三种周游与数据结构课程内容相衔接，预计学生兴趣较高；搜索树、DFS和Dijkstra算法内容较多，只能作简要介绍。3.存在问题与改进方向：（1）问题：本章内容极为丰富（树的等价命题、生成树与最小生成树、有向树、最优二叉树、有序树与编码、二叉树遍历、搜索树及多种算法），而本章只有2学时，难以深入展开。（2）改进方向：把教学重点放在树的概念体系、Kruskal算法和最优二叉树的构造方法上；五个等价命题只详讲(1)⇒(2)、(2)⇒(3)、(3)⇒(1)和引理F，其余证明作简要交代并布置课后阅读；DFS、Dijkstra算法作简要介绍，引导学生结合课件自学。（3）问题：最优二叉树的构造需要多次归约，步骤较多，学生容易在中间过程出错。（4）改进方向：课堂上完整演示权2、3、9、18、23、29的构造过程，要求学生在作业中按同样的表格形式逐步记录每次归约后的权序列，并验算最终的叶加权路径长度。（5）问题：位置二元有向有序树的编码规则和森林与二元树的自然对应关系较为抽象，仅凭讲授不易理解。（6）改进方向：以具体的三棵树组成的森林为例，边画图边写出各结点的编码，让学生对照图形理解“长子对应左儿子、大弟对应右儿子”的规则，并布置同类型练习加以巩固。备注1.本次课是第十一章“树”的全部内容，也是图论部分的最后一次课，内容多、涉及面广。授课时应把握主线——以“树是无回路的连通无向图”为出发点，按“无向树→生成树→有向树→有序树→搜索树”的顺序层层展开，注意各知识点之间的逻辑联系。2.讲授树的五个等价命题时不必逐一详细证明，建议重点讲清(1)⇒(2)、(2)⇒(3)、(3)⇒(1)和引理F，其余三个证明的归纳思路作简要交代，详细证明留给学生课后阅读。3.讲授Kruskal算法时，建议先按加权长度把边排序，再逐步演示“选边—判圈—保留或舍弃”的过程，并用道路扫雪问题说明算法的实际背景和应用价值。4.讲授最优二叉树时，建议用表格形式记录每次归约后的权序列（2,3,9,18,23,29→5,9,18,23,29→14,18,23,29→23,29,32→32,52→84），便于学生看清归约过程，避免中间步骤出错。5.讲授二元树的三种周游时，可提示学生与数据结构课程中的内容相互印证，重点讲清三种周游的递归定义和访问次序的差别。6.搜索树、DFS算法、Dijkstra算法和三个应用案例的内容较多，建议作简要介绍，引导学生课后结合课件和教材自学，并鼓励有兴趣的学生动手实现Kruskal算法和最优二叉树的构造过程。7.本章涉及的历史人物（基尔霍夫、克鲁斯卡尔）和应用案例（图像分割、句法分析、博弈智能、AlphaGo）适合作为课程思政素材，可结合专业背景适当展开，增强学生的专业认同感和使命感。8.授课周次按图论部分在课程中的实际进度填写，本教案暂填第16周，可根据实际教学进度调整。第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)、