其中 $ c(v) $ 表示在 $ G $ 中删除顶点 $ v $ 后，其邻域 $ N(v) $ 的顶点所构成的诱导子图中的**连通分量数量**。
这个值被称为顶点 $ v $ 的**叶状数**。

也就是说，这是一个**加性误差为 1 的近似算法**。这非常强大，因为对于 NP-Hard 问题，我们通常只能得到乘性近似比（比如 2倍最优解）。而这里，我们找到的树的最大度数最多只比最优解大 1。

好的，我已记住所有已讲过的题目。这次为你讲解一个尚未被提及的重要图论算法。 xxx 寻找图中的最小度生成树（Minimum Degree Spanning Tree）及其近似算法 题目描述 给定一个无向连通图 \( G = (V, E) \)，我们想要找到它的一个 生成树 。生成树的“度”是指其所有顶点中度数的最大值。我们的目标是寻找一棵生成树，使得这个最大的顶点度数尽可能小。这就是 最小度生成树 问题。 形式化地，对于一棵生成树 \( T \)，定义其度为： \[ \Delta(T) = \max_ {v \in V} \deg_ T(v) \] 其中 \( \deg_ T(v) \) 是顶点 \( v \) 在树 \( T \) 中的度数。 我们希望找到： \[ \Delta^* = \min_ {T \text{是} G \text{的生成树}} \Delta(T) \] 并构造一棵达到 \( \Delta^* \) 的生成树。 这个问题是 NP-Hard 的。因此，我们通常寻求高效的 近似算法 ，即找到一个生成树 \( T \)，使得 \( \Delta(T) \) 尽可能接近 \( \Delta^* \)。 解题过程循序渐进讲解 步骤1：理解问题的难度与下界 首先，我们需要知道最优解 \( \Delta^* \) 至少是多少。 明显的下界 ：对于图 \( G \) 中的任何一个顶点 \( v \)，它在任何生成树中的度数都不可能超过它在原图 \( G \) 中的度数 \( \deg_ G(v) \)。所以 \( \Delta^* \ge \min_ {v \in V} \deg_ G(v) \)。 更紧的下界 ：实际上，对于原图 \( G \) 中的任何一个顶点 \( v \)，在生成树中，连接它的边必须是从它与邻居相连的边中选出的。如果 \( v \) 在原图中有 \( k \) 个邻居，那么在生成树中，它最多只能有 \( k \) 条边与之相连。但这并没有给出一个全局的紧下界。 一个关键观察是：如果图 \( G \) 中有一个顶点 \( v \)，其邻域 \( N(v) \) 的导出子图是连通的，那么我们可以构造一棵生成树，让 \( v \) 的度数仅为 1（只需用一条边连接 \( v \) 到它的某个邻居，然后在这个邻居的连通块内构造树）。反之，如果 \( v \) 的邻域 \( N(v) \) 的导出子图不连通，那么为了保持整棵树的连通性，\( v \) 必须至少有 \( c \) 条边连接到它的邻居，其中 \( c \) 是 \( N(v) \) 导出子图中连通分量的数量。这是因为 \( v \) 是连接这些不同连通分量的唯一桥梁。 因此，我们得到一个非常重要的 下界 ： \[ \Delta^* \ge \max_ {v \in V} c(v) \] 其中 \( c(v) \) 表示在 \( G \) 中删除顶点 \( v \) 后，其邻域 \( N(v) \) 的顶点所构成的诱导子图中的 连通分量数量 。 这个值被称为顶点 \( v \) 的 叶状数 。 步骤2：近似算法的核心思想——Furer 和 Raghavachari 算法 一个经典且高效的近似算法由 Furer 和 Raghavachari 提出。其核心思想是 局部搜索 ：从任意一棵生成树开始，反复尝试进行“交换”操作来降低树中最大度顶点的度数，或者减少具有最大度数的顶点数量。 定义和记号 ： 设当前生成树为 \( T \)。 设 \( d = \Delta(T) \) 是当前树的最大度数。 目标是降低 \( d \)，或者在不增加 \( d \) 的情况下，减少度数为 \( d \) 的顶点数量。 关键操作：边交换 一次“边交换”操作是指：向树 \( T \) 中加入一条非树边 \( e = (u, w) \in E \setminus T \)，这必然会在树中形成一个唯一的环。然后从环中删除另一条边 \( f \neq e \)，得到一棵新的生成树 \( T' = T \cup \{e\} \setminus \{f\} \)。 一个好的交换应该能改善我们的目标。 如何选择交换？ 我们关注那些度数为 \( d \)（当前最大度）的顶点，称之为“坏”顶点。 考虑一个“坏”顶点 \( v \)。我们希望减少它的度数。 想法是：找到一条非树边 \( e = (u, w) \)，使得加入 \( e \) 后形成的环包含 \( v \) 的某条关联边 \( f \)（即 \( f \) 连接 \( v \) 和它的某个邻居）。然后我们删除 \( f \)。 这样操作的结果： 顶点 \( v \) 的度数减少 1（因为边 \( f \) 被删除了）。 顶点 \( u \) 和 \( w \) 的度数各增加 1（因为边 \( e \) 加入了）。 为了保证操作是“改善”的，我们需要确保 \( u \) 和 \( w \) 的度数在操作后 不超过 \( d-1 \)。否则，我们只是把最大度顶点从 \( v \) 换成了 \( u \) 或 \( w \)，没有实质改善。 更一般地，一个好的交换应满足：所有在新树 \( T‘ \) 中度数 增加 的顶点，其新度数都严格小于 \( d \)；而度数减少的顶点是原来的“坏”顶点 \( v \)。这样，新树的最大度数要么减小，要么保持不变但度数为 \( d \) 的顶点数减少。 步骤3：算法详细流程 初始化 ：使用任意算法（如 BFS、DFS 或 Prim 算法）找一棵生成树 \( T \)。 循环改进 ： 计算当前树 \( T \) 中每个顶点的度数，并找出最大度数 \( d = \Delta(T) \)。 尝试寻找一个“改进的边交换”： 遍历所有“坏”顶点 \( v \)（即 \( \deg_ T(v) = d \)）。 对于每个这样的 \( v \)，遍历它关联的每条树边 \( f = (v, x) \)。 对于每条这样的边 \( f \)，考虑所有可能的非树边 \( e = (u, w) \)，使得 \( f \) 在 \( T \cup \{e\} \) 形成的环上。 更实际的做法是：删除边 \( f \) 会将树 \( T \) 分成两个连通分量 \( A \) 和 \( B \)（\( v \) 在 \( A \)， \( x \) 在 \( B \)）。 我们需要找一条非树边 \( e = (u, w) \)，其中 \( u \in A \)， \( w \in B \)，且 \( u \neq v \)， \( w \neq x \)（这样可以确保 \( f \) 在环上）。 检查条件：\( \deg_ T(u) < d-1 \) 且 \( \deg_ T(w) < d-1 \)。 如果找到这样的边 \( e \)，则执行交换：\( T \leftarrow T \cup \{e\} \setminus \{f\} \)。 立即跳出循环，重新计算度数，开始下一轮改进尝试。 如果对所有的“坏”顶点 \( v \) 和其关联边 \( f \) 都找不到满足条件的非树边 \( e \)，则算法终止。 步骤4：算法性能分析（近似比） 该算法最精彩的部分在于其理论保证： 算法终止时，得到的生成树 \( T \) 的度 \( \Delta(T) \) 满足： \[ \Delta(T) \le \Delta^* + 1 \] 也就是说，这是一个 加性误差为 1 的近似算法 。这非常强大，因为对于 NP-Hard 问题，我们通常只能得到乘性近似比（比如 2倍最优解）。而这里，我们找到的树的最大度数最多只比最优解大 1。 为什么？ 回顾下界：\( \Delta^* \ge L = \max_ {v} c(v) \)，其中 \( c(v) \) 是 \( v \) 的叶状数（邻居连通分量数）。 假设算法终止时，得到树 \( T \) 且 \( \Delta(T) = d \)。 考虑任意一个在 \( T \) 中度数为 \( d \) 的顶点 \( v \)。 因为算法无法再进行改进，这意味着对于 \( v \) 的每一条关联树边 \( f = (v, x) \)，在由删除 \( f \) 分割出的两个分量 \( A \) 和 \( B \) 之间， 所有 跨越 \( (A, B) \) 的非树边 \( (u, w) \) 都至少有一个端点在原树 \( T \) 中的度数 大于等于 \( d-1 \)。 这表明，在分量 \( A \)（包含 \( v \)）中，所有与 \( v \) 在原图 \( G \) 中相连的邻居（除了通过 \( f \) 相连的 \( x \)），都在 \( T \) 中具有较高的度数（至少 \( d-1 \)）。通过仔细分析这种结构，可以论证在 \( G \) 中，删除 \( v \) 后，其邻域 \( N(v) \) 的连通分量数 \( c(v) \) 至少为 \( d-1 \)。 因此，\( d-1 \le c(v) \le \Delta^* \)。 所以 \( d \le \Delta^* + 1\)。 步骤5：总结与实例 总结 ： 最小度生成树问题的目标是找到最大顶点度数最小的生成树。 问题本质困难（NP-Hard），但存在高效的近似算法。 Furer 和 Raghavachari 的算法通过局部搜索（边交换）进行改进。 算法的终止条件是：找不到一种交换，能在不“破坏”当前最大度数约束的情况下，减少一个最大度顶点的度数。 该算法能保证找到的生成树的最大度数不超过最优解加 1，这是一个非常强的近似保证。 简单例子 ： 考虑一个“星形图”外加一条边：中心顶点 \( c \) 连接着 \( k \) 个叶子节点 \( l_ 1, ..., l_ k \)，同时叶子 \( l_ 1 \) 和 \( l_ 2 \) 之间也有一条边。 最优解 \( \Delta^* \) 是多少？注意到顶点 \( c \) 的邻居（所有叶子）构成的图，由于 \( l_ 1-l_ 2 \) 这条边的存在，是连通的（除了孤立点 \( l_ 3, ..., l_ k \) 各自为分量？这里需要仔细：\( N(c) = \{l_ 1, ..., l_ k\} \)， 其中 \( l_ 1 \) 和 \( l_ 2 \) 连通，其他 \( l_ 3, ..., l_ k \) 都是孤立点）。所以 \( c(c) = (k-2) + 1 = k-1 \)（一个包含 \( l_ 1, l_ 2 \) 的分量，加上 \( k-2 \) 个孤立叶子分量）。实际上，我们可以构造生成树：使用边 \( (c, l_ 1) \)，边 \( (l_ 1, l_ 2) \)，以及边 \( (c, l_ 3), ..., (c, l_ k) \)。这样 \( c \) 的度数是 \( k-1 \)，其他顶点度数最多 2。所以 \( \Delta^* \le k-1 \)。而下界 \( \Delta^* \ge c(c) = k-1 \)。因此 \( \Delta^* = k-1 \)。 算法可能会从一棵简单的 BFS 树开始（比如以 \( c \) 为根，连接所有叶子），此时 \( \Delta(T) = k \)。 算法会尝试改进：对于“坏”顶点 \( c \)，考虑它的一条边，比如 \( (c, l_ 1) \)。删除它，分量 \( A \) 包含 \( c, l_ 3, ..., l_ k \)，分量 \( B \) 包含 \( l_ 1, l_ 2 \)。存在非树边 \( (l_ 1, l_ 2) \) 连接 \( A \) 和 \( B \)（具体是连接 \( B \) 内部的 \( l_ 1 \) 和 \( l_ 2 \)？这里需要 \( u \in A, w \in B \)，而 \( l_ 1, l_ 2 \) 都在 \( B \)，不符合。我们需要一条边一端在 \( A \)，一端在 \( B \)。例如，考虑边 \( (c, l_ 2) \) 是树边，删除它，\( A \) 包含 \( c, l_ 1, l_ 3,...,l_ k \)， \( B \) 包含 \( l_ 2 \)。非树边 \( (l_ 1, l_ 2) \) 满足 \( u=l_ 1 \in A, w=l_ 2 \in B \)，且 \( \deg_ T(l_ 1)=1 < k-1\)， \( \deg_ T(l_ 2)=1 < k-1\)（假设 \( k > 2 \)）。执行交换：删除树边 \( (c, l_ 2) \)，加入非树边 \( (l_ 1, l_ 2) \)。这样， \( c \) 的度数减少 1， \( l_ 1 \) 和 \( l_ 2 \) 的度数增加 1但仍很小。经过一轮或几轮这样的交换，最终可以得到度数为 \( k-1 \) 的最优树。 这个算法虽然在最坏情况下的时间复杂度可能较高（与图的大小和初始解质量有关），但其简洁的思想和极强的理论保证，使其成为图论算法设计中局部搜索技术的典范之一。