离散数学 课件 6.8 树与生成树

第六章图论6.8树与生成树TreeandSpanningTree目录CONTENTS016.8.1树的基本概念树的定义、性质、特征与定理，为后续算法理解奠定理论基础。026.8.2生成树深入解析生成树的定义、存在性判定以及核心构造方法。036.8.3最小生成树理解最小生成树的定义，并掌握经典的Kruskal算法原理与实现。引言：树的概念与应用01/历史起源：从化学到数学19世纪中叶，英国数学家亚瑟·凯莱(ArthurCayley)在深入研究碳氢化合物的同分异构体时，敏锐地发现了“树”的数学结构。在形如CₙH₂ₙ₊₂的饱和烃分子中，碳原子与氢原子的连接方式呈现出一种无环、连通的网状特征。凯莱将这种结构抽象为数学中的“树”，并在1857年发表了相关论文，标志着图论中树论研究的正式开端。02/典型应用领域分子结构分析有机化学分子建模组织架构管理企业/机构层级关系计算机数据结构文件系统/数据库索引决策分析模型商业/AI算法决策树6.8.1树的基本概念定义6.36：无向树(Tree)树(Tree)一个连通且无回路的无向图，称为无向树，简称为树，在图论中常用符号T表示。树叶(Leaf)在一棵树中，度数等于1的结点。树叶是树的“端点”，不与其他中间节点相连。分枝点(InternalVertex)度数严格大于1的结点，也常被称为“内点”。它们起到连接和支撑整棵树结构的作用。森林(Forest)一个无回路的无向图。它不要求连通性，但它的每一个极大连通子图（连通分图）都是一棵树。简单来说，森林就是由多棵独立的树构成的图。平凡树(TrivialTree)一种特殊情况，指图中仅含有一个孤立结点（即无边、仅一个顶点）的树。这是最小的树结构，也常被看作是树的基础情况。树、森林与非树的对比树(Tree)图结构的一种，特征是：连通且无回路。任意两点间有且仅有一条路径。森林(Forest)由多棵互不相交的树组成。特征是：无回路，但整体不连通。非树(Non-Tree)不满足树定义的图。常见特征是：既不连通，又存在回路。也可能只违反其中一个条件。定理6.27：树的等价定义01定义一：无回路的连通图图T中不存在任何回路，且图T是连通的。02定义二：无回路且边数满足e=v-1图T中无回路，且图的边数恰好比顶点数少一。03定义三：连通且边数满足e=v-1图T是连通图，且图的边数恰好比顶点数少一。04定义四：加边产生唯一回路图T中无回路，但在任意两个不相邻的顶点间加一条边，就得到唯一的一个回路。05定义五：删边则不再连通图T是连通的，但删除任意一条边后，图T便不再连通。06定义六：两点间有且仅有一条通路对于图T中的任意一对顶点，它们之间有且仅有一条通路连接。树的核心特征总结01/路径唯一性树中任意两个结点之间都存在且仅存在一条简单通路，体现了树结构的确定性与连通性。02/边的敏感性树的连通性完全依赖于每条边。若删除其中任意一条边，图将立即被分割为两个互不连通的子图，整体变为森林。03/边数极值•无向图中，树是边数最多的无回路图

•无向图中，树是边数最少的连通图04/精妙平衡树完美地处于“连通”与“无回路”的临界点上。在保持连通的同时去掉了所有冗余，多一条边就会产生回路，少一条边则导致不连通。定理6.28：非平凡树的树叶数量定理表述：任一n阶非平凡树（n≥2），至少有两片树叶。（等价结论：树中至少存在两个度数为1的顶点）Step1:树的边点关系设树T有n个结点，m条边。根据树的基本定义与性质：连通且无回路，可得树的边数公式：m=n-1Step2:握手定理的推论根据图论中的“握手定理”，图中所有顶点的度数之和等于边数的两倍。结合树的边数性质可得：∑deg(v)=2m=2(n-1)Step3:反证法推导矛盾假设树只有1片树叶，则剩下n-1个顶点的度数至少为2。此时总度数之和：∑deg(v)≥1+2(n-1)=2n-1与∑deg(v)=2n-2矛盾！例题6.27：求树的树叶数💡问题描述：已知一棵无向树T中有4度、3度、2度的分枝点各一个，其余顶点均为树叶。问：树T中共有几片树叶？01/设定变量设树中树叶的数量为x个。02/计算总度数所有顶点的度数之和为：

4(分枝点)+3(分枝点)+2(分枝点)+x(树叶)=9+x03/计算总边数总顶点数n=3+x，根据树的性质m=n-1：

边数m=(3+x)-1=2+x04/应用握手定理(总度数=2×边数)建立方程：9+x=2×(2+x)05/求解方程展开并化简：9+x=4+2x

解得：x=5✅结论：树T中共有5片树叶6.8.2生成树定义6.37：生成树(SpanningTree)📋核心定义：若图G的生成子图T仍是一棵树，则称树T为图G的生成树。生成子图要求包含原图所有顶点。🌿树枝(Branch)生成树T中包含的边。🎻弦(Chord)图G中不在生成树T中的边。🌳余树(Cotree)：图G中所有弦的集合构成的子图（不一定是树）。应用场景：网络最小连通在通信网络、交通路网或计算机网络中，往往需要以最低成本连接所有节点。生成树是实现这一目标的最优结构：✅包含网络中全部的节点，保证连通性

✅无回路冗余，边的数量最少(n-1条边，n为节点数)“连接一切，且不多费一根线”生成树的应用示例核心问题构建一个包含多个节点的通信网络，如何在保证所有节点都能连通的前提下，铺设尽可能少的线路(边)，以实现成本与资源的最优配置？最优解：生成树在包含所有节点的连通图中，找到一个包含全部顶点且边数最少的连通子图——生成树(SpanningTree)。它在保证网络连通性的同时，消除了所有的环路冗余。图示：6个城市的通信网络对比

左侧为全连接图（存在大量冗余环路），右侧为其对应的生成树（仅保留必要连接）。定理6.29：生成树的存在条件定理内容：连通图至少有一棵生成树．一个图G存在生成树的充分必要条件是G是连通的。Case1:G本身是树如果图G满足树的定义（无回路且连通），则它自身就是一棵生成树，无需任何修改。Case2:G包含回路不断删除图中回路上的任意一条边，保持图的连通性不变。重复此操作直到图中没有回路，最终的子图即为生成树。💡重要推论一个连通图可以有多个不同的生成树。不同的删除边顺序或策略，会得到不同的生成树结构。例题6.28：识别生成树图G与子图G1,G2,G3,G4结构示意G1分析该子图内部不连通，既不满足“树”的连通性要求，也无法成为原图G的生成树。G2分析满足三个核心条件：连通、无回路、包含所有结点。是生成树。G3分析虽然连通且包含所有结点，但内部存在回路，不满足树的定义，因此不是生成树。G4分析图G中的一个顶点在G4中不存在，G4不是原图的生成子图，故也不是生成树。📝问题描述给定无向连通图G，试根据生成树的定义，判断下列四个子图G₁、G₂、G₃、G₄中，哪一个是G的生成树？定义6.38：连通图的秩基本定义若图G是一个有n个结点、m条边的连通图：根据树的性质，G的任意一棵生成树都恰好有n-1条边，且不包含任何回路。边数计算连通图G比其生成树多出了若干条边。要从连通图G中确定并构造出一棵生成树，我们必须删去的边的数量为：m-(n-1)图的秩(Rank)将上述计算式化简，数值：m-n+1被称为连通图G的秩。它的本质含义是图中“多余”的、可以被删除而不影响图的连通性的边的数量。生成树的构造算法方法一：破圈法(BreakingCycle)💡核心思想：从原图出发，主动破坏所有存在的回路。最终得到一个无回路的连通子图。📝具体步骤：循环在图中找到任意一个回路，并删除该回路中的任意一条边。重复此操作，直到图中不再含有任何回路。

对于有n个顶点、m条边的连通图，共需删除m-n+1条边。方法二：避圈法(AvoidingCycle)💡核心思想：从空图开始，通过逐步添加边来构建，每一步都严格避免产生新的回路，最终连接所有顶点。📝具体步骤：从空图开始，每次选取一条与已选边集合不构成回路的边加入。重复此操作，直到图中选取并连接了n-1条边。

常见的Kruskal算法与Prim算法均属于避圈法的具体实现。构造算法示例：破圈法01初始图从一个具有多个顶点和边，且存在多个回路的无向连通图出发。02第一次破圈在图中任意找到一个回路，删除其中一条边（例如边(1,4)），破坏该回路。03重复操作检查剩余的图，找到新的回路并删除其中一条边（例如边(3,5)），直至图中不存在任何回路。04最终结果原图变为连通且无回路的图，即为原图的一棵生成树。图示：破圈法逐步消除回路构造生成树构造算法示例：避圈法▍算法执行过程01初始状态：空图起点

从一个不包含任何边的空图开始，准备逐步构建。02首边选择：任选其一

从图中所有边中任意选择一条加入集合，例如边(1,2)。03避圈选边：循环迭代

每一步都选一条与已有边不构成回路的新边，如边(2,3)。✅终止条件：直至选够n-1条边，即得生成树图示：避圈法逐步添加边构建生成树的过程广度优先搜索(BFS)算法▍算法特点一种系统的、按层遍历的方法来构造生成树，像水波纹一样由内向外逐层扩散。01初始化任意选一个起始结点s，标记为0。02迭代搜索将标记k结点的未访问邻居记为k+1，并记录边03终止持续扩展，直到所有结点都被访问。核心应用：IP网络组播生成树在网络通信中，利用BFS算法构建的生成树，可以保证数据包高效、无冗余地从源节点到达网络中的多个目的节点，避免数据在网络中循环发送，降低网络拥塞风险。6.8.3最小生成树定义6.39：最小生成树(MinimumSpanningTree,MST)带权图(WeightedGraph)树权(TreeWeight)生成树T的所有边权值之和，记为C(T)。它是衡量整棵树总开销的指标。最小生成树(MST)在连通图G的所有可能生成树中，使得树权C(T)最小的那一棵生成树。💡典型应用场景：最低成本连接在连接多个城市的通信网或交通网建设中，如何铺设光纤、电缆或修建道路，使得所有节点（城市）都能连通，且总的建设成本或总距离达到最低？这是一个典型的最小生成树问题。为图G的每一条边e赋予一个数值化的权重，记为C(e)，常表示成本、距离或时间等。定理6.32：Kruskal算法别名：Kruskal避圈法(Kruskal'sAlgorithm)核心思想：一种贪心算法在图中所有与已选择边不构成回路的边中，始终选择权值最小的边，逐步构建最小生成树。01排序将图中所有的边按照权值从小到大进行升序排列，为后续选择做准备。02选择按照排序后的顺序，依次尝试选择边。若该边加入已选边集合后不构成回路，则选中；否则跳过。03终止持续选择直到已选边的数量达到n-1条（n为图中顶点数），此时算法结束，已选边构成最小生成树。例题6.29：求最小生成树❓问题：给定一个包含6个结点的无向连通带权图（图6.76(a)），请使用Kruskal算法求出其最小生成树(MST)并计算总权值。🛠算法执行步骤(按权值升序选择)1.选择边(权值1)：加入集合，无回路。2.选择边(权值2)：加入集合，无回路。3.选择边(权值3)：加入集合，无回路。4.跳过边(权值4)：若加入将构成回路。5.选择边(权值5)：加入集合，无回路。6.跳过边(权值6)：若加入将构成回路。7.选择边(权值7)：加入集合，已选够5条边，结束。✅最终结果：成功构造最小生成树（如图6.76(b)），包含5条边，连接所有6个结点。🌳总权值计算：C(T)=1+2+3+5+7=18例题6.30：求最小生成树题目描述请针对图6.77(a)中的连通带权图，应用图论算法找出其对应的最小生成树(MST)。算法与结果采用Kruskal算法（避圈法），按边权从小到大排序并依次选取，最终构造出的最小生成树结构如图6.77(b)所示。总权值(TotalWeight)计算C(T)=1+2+3+5+6+8+9=34本章总结树的基本概念🔍定义连通且无回路的无向图。⚡关键性质•边数关系：边数e=顶点数v-1

•路径唯一：任意两点间有且仅有一