无向图的最小点覆盖问题的基于树形动态规划的精确算法
字数 2690 2025-12-10 17:33:50

无向图的最小点覆盖问题的基于树形动态规划的精确算法

题目描述

在一个无向图 \(G = (V, E)\) 中，一个点覆盖是一个顶点集合 \(S \subseteq V\)，使得图中的每一条边都至少有一个端点在 \(S\) 中。最小点覆盖问题是要找到一个包含顶点数量最少的点覆盖。该问题是 NP-Hard 的。然而，当图是树时，该问题可以在多项式时间内通过树形动态规划解决。题目要求：给定一棵树，计算其最小点覆盖的大小（或构造出这个覆盖本身）。

解题过程

第一步：问题分析与模型转化

  1. 树的性质：树是连通的、无环的无向图。其任意两个节点之间有且只有一条简单路径。树可以任意选择一个根节点，转化为有根的树结构，从而父子关系明确，便于自底向上进行动态规划。
  2. 状态设计：对于有根树的每一个节点 \(u\)，我们定义两个状态：
    • \(dp[u][0]\)：表示以 \(u\) 为根的子树中，不选节点 \(u\) 的情况下，能够覆盖该子树中所有边的最小点覆盖的大小。
    • \(dp[u][1]\)：表示以 \(u\) 为根的子树中，选节点 \(u\) 的情况下，能够覆盖该子树中所有边的最小点覆盖的大小。
  3. 目标：最终答案是 \(\min(dp[root][0], dp[root][1])\)。如果要求构造方案，则需要记录状态转移的选择。

第二步：状态转移方程的推导

考虑节点 \(u\) 及其子节点集合 \(v_1, v_2, ..., v_k\)。

  • 情况1：不选节点 \(u\) (\(dp[u][0]\)）
    如果 \(u\) 不选，为了覆盖连接 \(u\) 和它的子节点 \(v_i\) 的边 \((u, v_i)\)，必须选择每一个子节点 \(v_i\)。因为这条边只能依靠其两个端点之一来覆盖，既然 \(u\) 未被选中，那么 \(v_i\) 就必须被选中。
    因此，\(dp[u][0] = \sum_{v \in children(u)} dp[v][1]\)。

  • 情况2：选择节点 \(u\) (\(dp[u][1]\)）
    如果 \(u\) 被选中，那么边 \((u, v_i)\) 已经被 \(u\) 覆盖。因此，对于子节点 \(v_i\)，我们既可以选择它，也可以不选择它。我们需要为每个子节点 \(v_i\) 做出最优决策，使得 \(v_i\) 的子树在满足覆盖条件的前提下，总点数最少。
    因此，\(dp[u][1] = 1 + \sum_{v \in children(u)} \min(dp[v][0], dp[v][1])\)。 这里的 \(1\) 代表选择了节点 \(u\) 本身。

第三步：边界条件（叶子节点）

考虑叶子节点 \(l\)。叶子节点没有子节点。

  • \(dp[l][0] = 0\)。如果不选叶子节点，其子树（只有自己）没有边需要覆盖，点覆盖大小为0。
  • \(dp[l][1] = 1\)。如果选择叶子节点，点覆盖大小为1。

第四步：算法步骤与示例

假设我们有一棵树：

        1
       / \
      2   3
     / \
    4   5

我们以节点1为根。

  1. 初始化叶子节点：

    • 节点4：\(dp[4][0]=0, dp[4][1]=1\)
    • 节点5：\(dp[5][0]=0, dp[5][1]=1\)
    • 节点3：\(dp[3][0]=0, dp[3][1]=1\)

  2. 自底向上计算：

    • 节点2（子节点为4,5）：
      • \(dp[2][0] = dp[4][1] + dp[5][1] = 1 + 1 = 2\)
      • \(dp[2][1] = 1 + \min(dp[4][0], dp[4][1]) + \min(dp[5][0], dp[5][1])\)
        \(= 1 + \min(0, 1) + \min(0, 1) = 1 + 0 + 0 = 1\)
    • 节点1（子节点为2,3）：
      • \(dp[1][0] = dp[2][1] + dp[3][1] = 1 + 1 = 2\)
      • \(dp[1][1] = 1 + \min(dp[2][0], dp[2][1]) + \min(dp[3][0], dp[3][1])\)
        \(= 1 + \min(2, 1) + \min(0, 1) = 1 + 1 + 0 = 2\)

  3. 得出答案：

    • 最小点覆盖大小为 \(\min(dp[1][0], dp[1][1]) = \min(2, 2) = 2\)。

第五步：构造最小点覆盖方案

为了输出是哪些节点，我们需要在动态规划的过程中记录每个状态的选择。

  1. 最终决策：从根节点开始。比较 \(dp[root][0]\) 和 \(dp[root][1]\)。假设我们最终决定的选择是 \(choice(root)\)。
  2. 递归构造：
    • 如果决定选节点 \(u\)，则将 \(u\) 加入结果集，并对其每个子节点 \(v\)，可以自由选择（选或不选），我们选择使得 \(dp[v][0]\) 和 \(dp[v][1]\) 中更小的那个对应的方案。
    • 如果决定不选节点 \(u\)，则 \(u\) 不加入结果集，但必须选择它的每一个子节点 \(v\)（即对每个子节点，必须走“选”的路径）。

以示例回溯：

  • 在节点1，两种选择结果相同（大小都是2），我们任选一种。假设我们选择不选节点1（即 \(dp[1][0]\) 这条路径）。
  • 因为不选节点1，根据规则，我们必须选节点2和节点3。
  • 对于节点2（必须选）：
    • 选择节点2后，对其子节点4和5可以自由选择。比较 \(dp[4][0]=0\) 和 \(dp[4][1]=1\)，选择不选节点4。比较 \(dp[5][0]=0\) 和 \(dp[5][1]=1\)，选择不选节点5。
  • 对于节点3（必须选）：
    • 选择节点3，其无子节点，结束。
  • 最终覆盖：节点2和节点3。大小=2，与计算结果一致。

总结

这个算法核心是利用了树的递归结构，通过定义“选/不选当前节点”两种状态，推导出清晰的最优子结构，并用后序遍历（DFS） 的方式自底向上完成动态规划。时间复杂度为 \(O(n)\)，其中 \(n\) 是树的节点数，因为每个节点只会被访问一次。这个算法是解决树结构上最小点覆盖问题的经典且最优的方法。

无向图的最小点覆盖问题的基于树形动态规划的精确算法 题目描述 在一个 无向图 \(G = (V, E)\) 中，一个 点覆盖 是一个顶点集合 \(S \subseteq V\)，使得图中的每一条边都至少有一个端点在 \(S\) 中。 最小点覆盖 问题是要找到一个包含顶点数量最少的点覆盖。该问题是 NP-Hard 的。然而，当图是 树 时，该问题可以在多项式时间内通过 树形动态规划 解决。题目要求：给定一棵树，计算其最小点覆盖的大小（或构造出这个覆盖本身）。 解题过程 第一步：问题分析与模型转化 树的性质 ：树是连通的、无环的无向图。其任意两个节点之间有且只有一条简单路径。树可以任意选择一个根节点，转化为有根的树结构，从而父子关系明确，便于自底向上进行动态规划。 状态设计 ：对于有根树的每一个节点 \(u\)，我们定义两个状态： \(dp[ u][ 0]\)：表示以 \(u\) 为根的子树中， 不选 节点 \(u\) 的情况下，能够覆盖该子树中所有边的最小点覆盖的大小。 \(dp[ u][ 1]\)：表示以 \(u\) 为根的子树中， 选 节点 \(u\) 的情况下，能够覆盖该子树中所有边的最小点覆盖的大小。 目标 ：最终答案是 \(\min(dp[ root][ 0], dp[ root][ 1 ])\)。如果要求构造方案，则需要记录状态转移的选择。 第二步：状态转移方程的推导 考虑节点 \(u\) 及其子节点集合 \(v_ 1, v_ 2, ..., v_ k\)。 情况1：不选节点 \(u\) (\(dp[ u][ 0]\)） 如果 \(u\) 不选，为了覆盖连接 \(u\) 和它的子节点 \(v_ i\) 的边 \((u, v_ i)\)， 必须选择每一个子节点 \(v_ i\) 。因为这条边只能依靠其两个端点之一来覆盖，既然 \(u\) 未被选中，那么 \(v_ i\) 就必须被选中。 因此，\(dp[ u][ 0] = \sum_ {v \in children(u)} dp[ v][ 1 ]\)。 情况2：选择节点 \(u\) (\(dp[ u][ 1]\)） 如果 \(u\) 被选中，那么边 \((u, v_ i)\) 已经被 \(u\) 覆盖。因此，对于子节点 \(v_ i\)，我们既可以选择它，也可以不选择它。我们需要为每个子节点 \(v_ i\) 做出最优决策，使得 \(v_ i\) 的子树在满足覆盖条件的前提下，总点数最少。 因此，\(dp[ u][ 1] = 1 + \sum_ {v \in children(u)} \min(dp[ v][ 0], dp[ v][ 1 ])\)。 这里的 \(1\) 代表选择了节点 \(u\) 本身。 第三步：边界条件（叶子节点） 考虑叶子节点 \(l\)。叶子节点没有子节点。 \(dp[ l][ 0 ] = 0\)。如果不选叶子节点，其子树（只有自己）没有边需要覆盖，点覆盖大小为0。 \(dp[ l][ 1 ] = 1\)。如果选择叶子节点，点覆盖大小为1。 第四步：算法步骤与示例 假设我们有一棵树： 我们以节点1为根。 初始化叶子节点 ： 节点4：\(dp[ 4][ 0]=0, dp[ 4][ 1 ]=1\) 节点5：\(dp[ 5][ 0]=0, dp[ 5][ 1 ]=1\) 节点3：\(dp[ 3][ 0]=0, dp[ 3][ 1 ]=1\) 自底向上计算 ： 节点2 （子节点为4,5）： \(dp[ 2][ 0] = dp[ 4][ 1] + dp[ 5][ 1 ] = 1 + 1 = 2\) \(dp[ 2][ 1] = 1 + \min(dp[ 4][ 0], dp[ 4][ 1]) + \min(dp[ 5][ 0], dp[ 5][ 1 ])\) \(= 1 + \min(0, 1) + \min(0, 1) = 1 + 0 + 0 = 1\) 节点1 （子节点为2,3）： \(dp[ 1][ 0] = dp[ 2][ 1] + dp[ 3][ 1 ] = 1 + 1 = 2\) \(dp[ 1][ 1] = 1 + \min(dp[ 2][ 0], dp[ 2][ 1]) + \min(dp[ 3][ 0], dp[ 3][ 1 ])\) \(= 1 + \min(2, 1) + \min(0, 1) = 1 + 1 + 0 = 2\) 得出答案 ： 最小点覆盖大小为 \(\min(dp[ 1][ 0], dp[ 1][ 1 ]) = \min(2, 2) = 2\)。 第五步：构造最小点覆盖方案 为了输出是哪些节点，我们需要在动态规划的过程中记录每个状态的选择。 最终决策 ：从根节点开始。比较 \(dp[ root][ 0]\) 和 \(dp[ root][ 1 ]\)。假设我们最终决定的选择是 \(choice(root)\)。 递归构造 ： 如果决定 选 节点 \(u\)，则将 \(u\) 加入结果集，并对其每个子节点 \(v\)， 可以自由选择 （选或不选），我们选择使得 \(dp[ v][ 0]\) 和 \(dp[ v][ 1 ]\) 中更小的那个对应的方案。 如果决定 不选 节点 \(u\)，则 \(u\) 不加入结果集，但必须 选择它的每一个子节点 \(v\)（即对每个子节点，必须走“选”的路径）。 以示例回溯 ： 在节点1，两种选择结果相同（大小都是2），我们任选一种。假设我们选择 不选节点1 （即 \(dp[ 1][ 0 ]\) 这条路径）。 因为不选节点1，根据规则，我们必须 选节点2和节点3 。 对于节点2（必须选）： 选择节点2后，对其子节点4和5可以自由选择。比较 \(dp[ 4][ 0]=0\) 和 \(dp[ 4][ 1]=1\)，选择不选节点4。比较 \(dp[ 5][ 0]=0\) 和 \(dp[ 5][ 1 ]=1\)，选择不选节点5。 对于节点3（必须选）： 选择节点3，其无子节点，结束。 最终覆盖 ：节点2和节点3。大小=2，与计算结果一致。 总结 这个算法核心是利用了树的递归结构，通过定义“选/不选当前节点”两种状态，推导出清晰的 最优子结构 ，并用 后序遍历（DFS） 的方式自底向上完成动态规划。时间复杂度为 \(O(n)\)，其中 \(n\) 是树的节点数，因为每个节点只会被访问一次。这个算法是解决树结构上最小点覆盖问题的经典且最优的方法。