2

支配集 (DS) := 给定一个无向图 G = (V;E)，如果对于 V 中的每个顶点，S 中都有一个与 v 相邻的顶点，则一组顶点 SV 是支配集。整个顶点集V 是任何图中的平凡支配集。

找到一棵树的最小尺寸支配集。

4

2 回答 2

2

1-总是从叶子开始

2-将他们的父母添加到DS并剪切孩子

3-将所选父母的父母标记为已经占主导地位

4-完成过程后，检查那些标记的节点是否有一个不被
支配的孩子并将它们添加到DS

祝你好运

于 2013-04-17T16:32:31.493 回答
2

我将尝试以更正式的方式证明这一点。

大纲

为了证明你的贪心算法是正确的，你需要证明两件事：

  1. 首先，您的贪婪选择是有效的，并且始终可以用于形成最佳解决方案，并且
  2. 第二，你的问题具有最优子结构性质，即你可以从最优解到你自己问题的子问题形成最优解。

贪婪选择：在你的树 T = (V, E) 中，在树中找到一个顶点v，它的叶子数最多。将它添加到您的主导集。

最优子结构

T' = (V', E') 使得：

  • V' = V \ ({a : a ϵ V, a 与 v 相邻, a' 度 ≤ 2} ∪ {v})
  • E' = E - 涉及任何已移除顶点的任何边

换句话说

寻找叶数最多的顶点，删除其度数小于或等于 2 的任何相邻顶点，然后删除 v 本身，并将其添加到您的优势集。重复此操作，直到您没有剩余顶点。

证明

贪心选择证明

对于任何叶子l，它必须是它自己或其父节点在主导集中。在我们的例子中，我们选择的顶点v就是在这种情况下。

令A = { v 1 , v 2 , ... , v k } 是 T 的最小优势集。如果 A 已经有v作为成员，我们就完成了。如果没有，我们会看到两种情况：

  1. v有一些相邻的叶子l。那么， l必须是支配集的一部分，否则我们的集不会支配整个树。因此，我们可以简单地形成A' = { A - {l} + { v }} 并且仍然是一个优势集。自从 | 一个' | = | A |, A'仍然是最优的。

  2. v没有任何相邻的叶子l。然后，因为v的选择使得它的叶子数量最多，所以T中的任何顶点都没有叶子。那么T不是一棵树。矛盾。

因此，我们将始终能够通过我们的贪婪选择形成最优解。

最优子结构证明

假设A是T = ( V, E ) 的最小优势集，但A' = A \ { v } 不是上面定义的T'的最小优势集。

为 T' 建立一个最小优势集，称之为 B。如前所述，| 乙| < | 一个' |。可以证明B' = B ∪ { v } 是T的支配集。那么，由于| 一个' | = | 一个| - 1, | 乙' | = | 乙| + 1，我们得到 | 乙' | < | 一个|。这是矛盾的，因为我们假设A是最小独立集。因此它一定是A'也是T'的最小独立集。

证明B' = B ∪ { v } 是T的支配集：

  • v可能有相邻的顶点不在T'中。我们将证明在T'中未考虑的任何顶点都将由B'中的顶点支配（这意味着我们选择了最优的集合）：让y是与v相邻的某个顶点，而不是在T'中。根据T' 的定义，y 只能有 1 或 2 级。现在，y由v支配。如果y是一片叶子，那么我们就完成了。但是，如果y的度数为 2，则y连接到另一个节点，该节点必然在B的优势集中. 这是因为，当我们移除v以生成 T' 时， y的度数变为 1，这意味着y或其父项必然被添加到主导集。因此，B'是T的主导集。
于 2018-12-04T21:26:37.727 回答