基于线性规划的图最小有向生成树（最小树形图）问题的Edmonds算法与对偶解释求解示例
字数 5909 2025-12-22 05:57:53

基于线性规划的图最小有向生成树（最小树形图）问题的Edmonds算法与对偶解释求解示例

问题描述

我们考虑一个有向图 \(G = (V, E)\)，其中 \(V\) 是顶点集合，共有 \(n\) 个顶点，\(E\) 是有向边的集合，共有 \(m\) 条边。每条边 \(e = (u, v) \in E\) 都有一个非负的权重 \(w(e)\)。我们指定一个特殊的顶点 \(r \in V\) 作为根。

最小树形图问题 的目标是：找到一个有向边的集合 \(T \subseteq E\)，使得：

  1. \(T\) 构成一棵以 \(r\) 为根的有向生成树（或称“树形图”）。这意味着从根 \(r\) 出发，可以通过 \(T\) 中的有向边到达图中任何一个顶点 \(v \in V\)，且 \(T\) 中不包含任何有向环。
  2. 所有满足条件的树形图中，\(T\) 中边的权重之和最小。

这是一个经典的组合优化问题，有着广泛的应用，例如网络设计、电路布线等。我们将展示如何通过 Edmonds算法 求解，并从线性规划对偶的角度解释其正确性。

解题过程

第一步：理解问题结构与初步想法

  1. 什么是以 \(r\) 为根的有向生成树？

    • 除了根 \(r\) 以外的每个顶点 \(v \neq r\)，在树形图中必须恰好有 一条 进入边（入度为1）。
    • 根 \(r\) 的入度为0。
    • 整个子图必须是无环的（即构成一棵有向树）。
    • 这保证了从 \(r\) 到任一顶点都存在唯一的有向路径。

  2. 一个朴素的整数规划模型：
    对每条边 \(e \in E\)，定义一个二进制变量 \(x_e\)，表示该边是否被选入树形图 \(T\) 中。

\[ \begin{aligned} \text{最小化} \quad & \sum_{e \in E} w(e) x_e \\ \text{满足} \quad & \sum_{e \in \delta^{-}(v)} x_e = 1, \quad \forall v \in V \setminus \{r\} \quad (\text{每个非根节点恰有一条入边}) \\ & \sum_{e \in \delta^{-}(S)} x_e \ge 1, \quad \forall S \subseteq V \setminus \{r\}, S \neq \emptyset \quad (\text{防止无环性被破坏，即每个非根集合至少有一条来自外部的入边})\\ & x_e \in \{0, 1\}, \quad \forall e \in E \end{aligned} \]

其中，$ \delta^{-}(v) $ 表示指向顶点 $ v $ 的边的集合，$ \delta^{-}(S) $ 表示指向集合 $ S $（从 $ V \setminus S $ 到 $ S $）的边的集合。

第二个约束（称为**有向割约束**）保证了从根 $ r $ 可以到达所有顶点。这个整数规划模型虽然精确，但约束数量是指数级的（需要对所有子集 $ S $），直接求解困难。Edmonds算法巧妙地避开了显式处理这些约束。

第二步：Edmonds 算法详解

Edmonds算法是一个递归的贪心算法，核心思想是 “收缩环” 。

算法步骤：

  1. 初始化：对于每个非根顶点 \(v \neq r\)，选择指向它的权重最小的边，记其权重为 \(min\_in[v]\)，这条边称为 \(v\) 的 最小入边。

    • 如果某个非根顶点没有入边，则问题无解。
    • 将这些最小入边（共 \(n-1\) 条）的集合记为 \(E_{min}\)。

  2. 检查环：

    • 考察由 \(E_{min}\) 构成的子图。由于每个非根点恰有一条入边，这个子图由若干个有向环（可能包含自环，即指向自己的环状结构，这里指大小>=2的环）和一些以 \(r\) 为起点的树组成。
    • 如果这个子图中 没有 有向环（除了可能的根 \(r\) 自环，但 \(r\) 没有最小入边，所以不会形成环），那么 \(E_{min}\) 就是我们要找的最小树形图。算法结束。

  3. 处理环：

    • 如果发现一个有向环 \(C\)（由顶点集合 \(V_C\) 和边集合 \(E_C\) 构成，且 \(r \notin V_C\)），我们进行 “收缩” 操作：
      a. 重新计算权重：
      * 对于环 \(C\) 外的任意一条边 \(e = (u, v)\)：
      * 如果 \(v\) 在环 \(C\) 中，我们将这条边的权重修改为 \(w'(e) = w(e) - min\_in[v]\)。其直观意义是：要使用这条边进入环，相当于我们“放弃”了环上进入 \(v\) 的那条最小入边，因此成本是“额外支付”的差价。
      * 如果 \(v\) 不在环 \(C\) 中，权重 \(w'(e)\) 不变。
      b. 收缩环：将环 \(C\) 中的所有顶点“捏”成一个新的 超级顶点 \(c^*\)。所有原来指向环 \(C\) 中任一顶点的边，现在都指向 \(c^*\)；所有从环 \(C\) 中任一顶点指出的边，现在都从 \(c^*\) 指出。注意处理重边（保留权重最小的那条）。
      c. 记录下环 \(C\) 和收缩关系，用于后续 “展开” 还原。

  4. 递归求解：

    • 在收缩后的新图 \(G'\) 上，递归调用 Edmonds 算法，寻找以 \(r\) 为根的最小树形图 \(T'\)（如果 \(r\) 被收缩进环，则根变为新的超级顶点）。

  5. 展开环，恢复解：

    • 递归调用返回新图 \(G'\) 上的解 \(T'\)。
    • 展开环 \(C\)：
      • 如果 \(T'\) 中包含一条指向超级顶点 \(c^*\) 的边 \(e'\)，这条边在原图中对应一条指向环 \(C\) 中某个特定顶点 \(v_c\) 的边 \(e\)。在最终的解中，我们 保留边 \(e\)，并且 去掉 环 \(C\) 中原本指向 \(v_c\) 的那条最小入边。
      • 对于环 \(C\) 上的其他顶点，我们保留它们在第一步中选择的最小入边。
      • 这样，我们就打破了环，并得到原图 \(G\) 上的一个合法树形图 \(T\)。
    • 最终，\(T\) 就是原问题的最小树形图。

算法复杂度：每次递归至少减少一个顶点，每次迭代需要 \(O(m)\) 时间检查入边和环，因此总时间复杂度为 \(O(nm)\)，对于稠密图是多项式时间。

第三步：从线性规划对偶角度解释

Edmonds算法的精妙之处可以从其 线性规划对偶 的角度得到深刻理解。

  1. 构造对偶问题：
    考虑最小树形图问题的一个线性规划松弛，放松整数约束 \(x_e \in \{0,1\}\) 为 \(x_e \ge 0\)，但保留所有有向割约束。这个LP的对偶问题可以构造如下：

    • 对偶变量：对于每个非根顶点 \(v\)，有一个变量 \(y_v\)（可以直观理解为给顶点 \(v\) 的“预算”或“势能”）。
    • 对偶约束：对于每条边 \(e = (u, v)\)，有 \(y_v \le w(e) + y_u\)。（当 \(v = r\) 时，视 \(y_r = 0\) 固定）
    • 对偶目标：最大化 \(\sum_{v \neq r} y_v\)。

  2. 对偶可行解的构造与算法对应：
    Edmonds算法中，第一步为每个非根顶点 \(v\) 选择最小入边，其权重 \(min\_in[v]\) 可以自然地构造一个对偶可行解。

    • 初始化所有 \(y_v = 0\)。
    • 当我们为一个顶点 \(v\) 找到最小入边权重 \(min\_in[v]\) 时，我们设置 \(y_v = min\_in[v]\)。
    • 此时，对于所有指向 \(v\) 的边 \(e=(u,v)\)，检查对偶约束：\(y_v = min\_in[v] \le w(e) \le w(e) + y_u\)，因为 \(y_u \ge 0\)。所以约束成立。

  3. 收缩操作的对偶意义：
    当发现环 \(C\) 时，环上的对偶变量 \(\{y_v\}\) 可能不满足“互补松弛条件”的严格等式（最优解中，对于选中的边 \(e=(u,v)\)，应有 \(y_v = w(e) + y_u\)）。
    收缩操作和权重调整 \(w'(e) = w(e) - min\_in[v]\) 本质上是在 重新定义图上的对偶变量。

    • 在收缩后的新图中，超级顶点 \(c^*\) 的对偶变量 被设为0。
    • 原图中，环 \(C\) 上所有顶点的对偶变量的“盈余”部分（即它们当前 \(y_v\) 与可能的最优值之间的差距）被吸收进边的权重调整中。权重调整公式 \(w'(e) = w(e) - y_v\) 保证了在新图中，与 \(c^*\) 相关的边的对偶约束能够基于新的 \(y_{c^*}=0\) 来重新评估。
    • 递归求解新图上的问题，相当于在寻找一个能“吸收”掉环上对偶变量不协调部分的新对偶分配。

  4. 互补松弛与最优性：
    当算法终止（无环）时，我们得到一组最小入边构成一棵树，以及对应的对偶变量 \(y_v\)（最终值可能是递归过程中调整后的累加值）。
    可以证明，这组原始解（选中的边）和对偶解 \(\{y_v\}\) 满足 互补松弛条件：

    • 原始互补松弛：如果边 \(e=(u,v)\) 被选中，那么在对偶约束中一定有 \(y_v = w(e) + y_u\)（因为它是 \(v\) 的最小入边，调整后的权重为0）。
    • 对偶互补松弛：变量 \(x_e > 0\)（即被选中的边）对应的对偶约束是紧的。
      满足互补松弛条件，且原始解可行（是一棵树形图），对偶解可行，根据线性规划对偶理论，它们分别是原始问题和对偶问题的最优解。因此，Edmonds算法找到的树形图是最小权重的。

第四步：一个简单的计算示例

考虑下图，根 \(r = 1\)，边权重如图。

顶点: 1(r), 2, 3, 4
有向边与权重：
(1->2): 4
(1->3): 3
(2->3): 2
(3->2): 1
(3->4): 5
(4->3): 6
(4->1): 7 (从非根指向根的边，对树形图无用)
(2->4): 8

  1. 初始化：选择每个非根顶点的最小入边。

    • \(min\_in[2] = 1\) (来自边 3->2)
    • \(min\_in[3] = 2\) (来自边 2->3)
    • \(min\_in[4] = 5\) (来自边 3->4)
    • \(E_{min} = \{3->2, 2->3, 3->4\}\)

  2. 检查环：\(E_{min}\) 包含环 \(C: 2 -> 3 -> 2\)。顶点集 \(V_C = \{2,3\}\)，边集 \(E_C = \{2->3, 3->2\}\)。

  3. 收缩环 \(C\)：

    • 重新计算指向环的边的权重：
      • 边 (1->2): \(w' = 4 - min\_in[2] = 4 - 1 = 3\)
      • 边 (1->3): \(w' = 3 - min\_in[3] = 3 - 2 = 1\)
      • 边 (4->3): 指向环，但顶点4不在新图中（未处理到），先不计算，等下个递归。
    • 收缩 {2,3} 为新超级顶点 \(c^*\)。
    • 新图 \(G'\) 的顶点：\(\{1(r), c^*, 4\}\)
    • 新图的边：
      • (1->c^*): 权重取 min(上述调整后的 (1->2):3, (1->3):1) = 1
      • (c^*->4): 环内顶点指向外的边，权重不变，即 (3->4):5。
      • (4->c^*): (4->3) 调整后权重？需要先知道环中 min_in[3]=2。 \(w' = 6 - 2 = 4\)。
      • (1->4): 原图没有直接边。
      • (4->1): 7 (不变，但无用)。

  4. 递归求解 \(G'\)：

    • 在 \(G'\) 中，对非根顶点选最小入边：
      • \(min\_in[c^*] = 1\) (来自边 1->c^*)
      • \(min\_in[4] = 5\) (来自边 c^->4) // 注意，边(4->c^)权重4，但它是从4指向c^，不是c^的入边。
    • \(E'_{min} = \{1->c^*, c^*->4\}\)。
    • 检查无环。递归结束。\(T' = \{1->c^*, c^*->4\}\)。

  5. 展开环 \(C\)：

    • \(T'\) 中边 (1->c^*) 对应原图中调整后权重最小的那条入环边，即 (1->3)，权重调整值为1（原权重3 - min_in[3]=2）。
    • 因此，在原环 \(C\) 中，我们 选择原边 (1->3)，并 去掉 环中指向顶点3的最小入边，即 (2->3)。（因为 (1->3) 进入了环上的顶点3）。
    • 环 \(C\) 上剩下的边，我们保留其最小入边，即 (3->2)（指向顶点2的）。
    • \(T'\) 中另一条边 (c^*->4) 对应原边 (3->4)。
    • 最终解 \(T = \{1->3, 3->2, 3->4\}\)。
    • 总权重 = 3 + 1 + 5 = 9。

验证：这是一棵以1为根的有向生成树，且权重最小（可以尝试其他组合验证，如 {1->2, 2->3, 3->4} 权重4+2+5=11 > 9）。

总结

Edmonds算法通过递归地“选择最小入边 - 检测环 - 收缩环并调整权重”的过程，高效地解决了最小树形图问题。其背后的线性规划对偶理论为其正确性提供了严谨的证明框架：算法隐式地维护了一组对偶可行的势函数 \(y_v\)，并通过收缩操作协调环上的对偶冲突，最终使原始解（得到的树形图）和对偶解满足互补松弛条件，从而保证了最优性。这个算法将复杂的组合结构处理和线性规划的最优性验证完美地结合了起来。

基于线性规划的图最小有向生成树（最小树形图）问题的Edmonds算法与对偶解释求解示例 问题描述 我们考虑一个有向图 \( G = (V, E) \)，其中 \( V \) 是顶点集合，共有 \( n \) 个顶点，\( E \) 是有向边的集合，共有 \( m \) 条边。每条边 \( e = (u, v) \in E \) 都有一个非负的权重 \( w(e) \)。我们指定一个特殊的顶点 \( r \in V \) 作为根。 最小树形图问题 的目标是：找到一个有向边的集合 \( T \subseteq E \)，使得： \( T \) 构成一棵以 \( r \) 为根的有向生成树（或称“树形图”）。这意味着从根 \( r \) 出发，可以通过 \( T \) 中的有向边到达图中任何一个顶点 \( v \in V \)，且 \( T \) 中不包含任何有向环。 所有满足条件的树形图中，\( T \) 中边的权重之和最小。 这是一个经典的组合优化问题，有着广泛的应用，例如网络设计、电路布线等。我们将展示如何通过 Edmonds算法 求解，并从线性规划对偶的角度解释其正确性。 解题过程 第一步：理解问题结构与初步想法 什么是以 \( r \) 为根的有向生成树？ 除了根 \( r \) 以外的每个顶点 \( v \neq r \)，在树形图中必须恰好有 一条 进入边（入度为1）。 根 \( r \) 的入度为0。 整个子图必须是无环的（即构成一棵有向树）。 这保证了从 \( r \) 到任一顶点都存在唯一的有向路径。 一个朴素的整数规划模型： 对每条边 \( e \in E \)，定义一个二进制变量 \( x_ e \)，表示该边是否被选入树形图 \( T \) 中。 \[ \begin{aligned} \text{最小化} \quad & \sum_ {e \in E} w(e) x_ e \\ \text{满足} \quad & \sum_ {e \in \delta^{-}(v)} x_ e = 1, \quad \forall v \in V \setminus \{r\} \quad (\text{每个非根节点恰有一条入边}) \\ & \sum_ {e \in \delta^{-}(S)} x_ e \ge 1, \quad \forall S \subseteq V \setminus \{r\}, S \neq \emptyset \quad (\text{防止无环性被破坏，即每个非根集合至少有一条来自外部的入边})\\ & x_ e \in \{0, 1\}, \quad \forall e \in E \end{aligned} \] 其中，\( \delta^{-}(v) \) 表示指向顶点 \( v \) 的边的集合，\( \delta^{-}(S) \) 表示指向集合 \( S \)（从 \( V \setminus S \) 到 \( S \)）的边的集合。 第二个约束（称为 有向割约束 ）保证了从根 \( r \) 可以到达所有顶点。这个整数规划模型虽然精确，但约束数量是指数级的（需要对所有子集 \( S \)），直接求解困难。Edmonds算法巧妙地避开了显式处理这些约束。 第二步：Edmonds 算法详解 Edmonds算法是一个递归的贪心算法，核心思想是 “收缩环” 。 算法步骤： 初始化 ：对于每个非根顶点 \( v \neq r \)，选择指向它的权重最小的边，记其权重为 \( min\_in[ v] \)，这条边称为 \( v \) 的 最小入边 。 如果某个非根顶点没有入边，则问题无解。 将这些最小入边（共 \( n-1 \) 条）的集合记为 \( E_ {min} \)。 检查环 ： 考察由 \( E_ {min} \) 构成的子图。由于每个非根点恰有一条入边，这个子图由若干个有向环（可能包含自环，即指向自己的环状结构，这里指大小>=2的环）和一些以 \( r \) 为起点的树组成。 如果这个子图中 没有 有向环（除了可能的根 \( r \) 自环，但 \( r \) 没有最小入边，所以不会形成环），那么 \( E_ {min} \) 就是我们要找的最小树形图。算法结束。 处理环 ： 如果发现一个有向环 \( C \)（由顶点集合 \( V_ C \) 和边集合 \( E_ C \) 构成，且 \( r \notin V_ C \)），我们进行 “收缩” 操作： a. 重新计算权重 ： * 对于环 \( C \) 外的任意一条边 \( e = (u, v) \)： * 如果 \( v \) 在环 \( C \) 中，我们将这条边的权重修改为 \( w'(e) = w(e) - min\_in[ v ] \)。其直观意义是：要使用这条边进入环，相当于我们“放弃”了环上进入 \( v \) 的那条最小入边，因此成本是“额外支付”的差价。 * 如果 \( v \) 不在环 \( C \) 中，权重 \( w'(e) \) 不变。 b. 收缩环 ：将环 \( C \) 中的所有顶点“捏”成一个新的 超级顶点 \( c^* \)。所有原来指向环 \( C \) 中任一顶点的边，现在都指向 \( c^* \)；所有从环 \( C \) 中任一顶点指出的边，现在都从 \( c^* \) 指出。注意处理重边（保留权重最小的那条）。 c. 记录下环 \( C \) 和收缩关系，用于后续 “展开” 还原。 递归求解 ： 在收缩后的新图 \( G' \) 上，递归调用 Edmonds 算法，寻找以 \( r \) 为根的最小树形图 \( T' \)（如果 \( r \) 被收缩进环，则根变为新的超级顶点）。 展开环，恢复解 ： 递归调用返回新图 \( G' \) 上的解 \( T' \)。 展开环 \( C \) ： 如果 \( T' \) 中包含一条指向超级顶点 \( c^* \) 的边 \( e' \)，这条边在原图中对应一条指向环 \( C \) 中某个特定顶点 \( v_ c \) 的边 \( e \)。在最终的解中，我们 保留边 \( e \) ，并且 去掉 环 \( C \) 中原本指向 \( v_ c \) 的那条最小入边。 对于环 \( C \) 上的其他顶点，我们保留它们在第一步中选择的最小入边。 这样，我们就打破了环，并得到原图 \( G \) 上的一个合法树形图 \( T \)。 最终，\( T \) 就是原问题的最小树形图。 算法复杂度 ：每次递归至少减少一个顶点，每次迭代需要 \( O(m) \) 时间检查入边和环，因此总时间复杂度为 \( O(nm) \)，对于稠密图是多项式时间。 第三步：从线性规划对偶角度解释 Edmonds算法的精妙之处可以从其 线性规划对偶 的角度得到深刻理解。 构造对偶问题 ： 考虑最小树形图问题的一个 线性规划松弛 ，放松整数约束 \( x_ e \in \{0,1\} \) 为 \( x_ e \ge 0 \)，但保留所有有向割约束。这个LP的对偶问题可以构造如下： 对偶变量：对于每个非根顶点 \( v \)，有一个变量 \( y_ v \)（可以直观理解为给顶点 \( v \) 的“预算”或“势能”）。 对偶约束：对于每条边 \( e = (u, v) \)，有 \( y_ v \le w(e) + y_ u \)。（当 \( v = r \) 时，视 \( y_ r = 0 \) 固定） 对偶目标：最大化 \( \sum_ {v \neq r} y_ v \)。 对偶可行解的构造与算法对应 ： Edmonds算法中，第一步为每个非根顶点 \( v \) 选择最小入边，其权重 \( min\_in[ v ] \) 可以自然地构造一个对偶可行解。 初始化所有 \( y_ v = 0 \)。 当我们为一个顶点 \( v \) 找到最小入边权重 \( min\_in[ v] \) 时，我们设置 \( y_ v = min\_in[ v ] \)。 此时，对于所有指向 \( v \) 的边 \( e=(u,v) \)，检查对偶约束：\( y_ v = min\_in[ v] \le w(e) \le w(e) + y_ u \)，因为 \( y_ u \ge 0 \)。所以约束成立。 收缩操作的对偶意义 ： 当发现环 \( C \) 时，环上的对偶变量 \( \{y_ v\} \) 可能不满足“互补松弛条件”的严格等式（最优解中，对于选中的边 \( e=(u,v) \)，应有 \( y_ v = w(e) + y_ u \)）。 收缩操作和权重调整 \( w'(e) = w(e) - min\_in[ v] \) 本质上是在 重新定义图上的对偶变量 。 在收缩后的新图中， 超级顶点 \( c^* \) 的对偶变量 被设为0。 原图中，环 \( C \) 上所有顶点的对偶变量的“盈余”部分（即它们当前 \( y_ v \) 与可能的最优值之间的差距）被吸收进边的权重调整中。权重调整公式 \( w'(e) = w(e) - y_ v \) 保证了在新图中，与 \( c^* \) 相关的边的对偶约束能够基于新的 \( y_ {c^* }=0 \) 来重新评估。 递归求解新图上的问题，相当于在寻找一个能“吸收”掉环上对偶变量不协调部分的新对偶分配。 互补松弛与最优性 ： 当算法终止（无环）时，我们得到一组最小入边构成一棵树，以及对应的对偶变量 \( y_ v \)（最终值可能是递归过程中调整后的累加值）。 可以证明，这组原始解（选中的边）和对偶解 \( \{y_ v\} \) 满足 互补松弛条件 ： 原始互补松弛 ：如果边 \( e=(u,v) \) 被选中，那么在对偶约束中一定有 \( y_ v = w(e) + y_ u \)（因为它是 \( v \) 的最小入边，调整后的权重为0）。 对偶互补松弛 ：变量 \( x_ e > 0 \)（即被选中的边）对应的对偶约束是紧的。 满足互补松弛条件，且原始解可行（是一棵树形图），对偶解可行，根据线性规划对偶理论，它们分别是原始问题和对偶问题的最优解。因此，Edmonds算法找到的树形图是最小权重的。 第四步：一个简单的计算示例 考虑下图，根 \( r = 1 \)，边权重如图。 初始化 ：选择每个非根顶点的最小入边。 \( min\_in[ 2 ] = 1 \) (来自边 3->2) \( min\_in[ 3 ] = 2 \) (来自边 2->3) \( min\_in[ 4 ] = 5 \) (来自边 3->4) \( E_ {min} = \{3->2, 2->3, 3->4\} \) 检查环 ：\( E_ {min} \) 包含环 \( C: 2 -> 3 -> 2 \)。顶点集 \( V_ C = \{2,3\} \)，边集 \( E_ C = \{2->3, 3->2\} \)。 收缩环 \( C \) ： 重新计算指向环的边的权重： 边 (1->2): \( w' = 4 - min\_in[ 2 ] = 4 - 1 = 3 \) 边 (1->3): \( w' = 3 - min\_in[ 3 ] = 3 - 2 = 1 \) 边 (4->3): 指向环，但顶点4不在新图中（未处理到），先不计算，等下个递归。 收缩 {2,3} 为新超级顶点 \( c^* \)。 新图 \( G' \) 的顶点：\( \{1(r), c^* , 4\} \) 新图的边： (1->c^* ): 权重取 min(上述调整后的 (1->2):3, (1->3):1) = 1 (c^* ->4): 环内顶点指向外的边，权重不变，即 (3->4):5。 (4->c^* ): (4->3) 调整后权重？需要先知道环中 min\_in[ 3 ]=2。 \( w' = 6 - 2 = 4 \)。 (1->4): 原图没有直接边。 (4->1): 7 (不变，但无用)。 递归求解 \( G' \) ： 在 \( G' \) 中，对非根顶点选最小入边： \( min\_in[ c^ ] = 1 \) (来自边 1->c^ ) \( min\_in[ 4] = 5 \) (来自边 c^ ->4) // 注意，边(4->c^ )权重4，但它是从4指向c^ ，不是c^ 的入边。 \( E'_ {min} = \{1->c^ , c^ ->4\} \)。 检查无环。递归结束。\( T' = \{1->c^ , c^ ->4\} \)。 展开环 \( C \) ： \( T' \) 中边 (1->c^* ) 对应原图中调整后权重最小的那条入环边，即 (1->3)，权重调整值为1（原权重3 - min\_in[ 3 ]=2）。 因此，在原环 \( C \) 中，我们 选择原边 (1->3) ，并 去掉 环中指向顶点3的最小入边，即 (2->3)。（因为 (1->3) 进入了环上的顶点3）。 环 \( C \) 上剩下的边，我们保留其最小入边，即 (3->2)（指向顶点2的）。 \( T' \) 中另一条边 (c^* ->4) 对应原边 (3->4)。 最终解 \( T = \{1->3, 3->2, 3->4\} \)。 总权重 = 3 + 1 + 5 = 9。 验证 ：这是一棵以1为根的有向生成树，且权重最小（可以尝试其他组合验证，如 {1->2, 2->3, 3->4} 权重4+2+5=11 > 9）。 总结 Edmonds算法通过递归地“选择最小入边 - 检测环 - 收缩环并调整权重”的过程，高效地解决了最小树形图问题。其背后的线性规划对偶理论为其正确性提供了严谨的证明框架：算法隐式地维护了一组对偶可行的势函数 \( y_ v \)，并通过收缩操作协调环上的对偶冲突，最终使原始解（得到的树形图）和对偶解满足互补松弛条件，从而保证了最优性。这个算法将复杂的组合结构处理和线性规划的最优性验证完美地结合了起来。