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不是一棵树。矛盾。

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

最优子结构证明

假设AT = ( 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 级。现在,yv支配。如果y是一片叶子,那么我们就完成了。但是,如果y的度数为 2,则y连接到另一个节点,该节点必然在B的优势集中. 这是因为,当我们移除v以生成 T' 时, y的度数变为 1,这意味着y或其父项必然被添加到主导集。因此,B'T的主导集。
于 2018-12-04T21:26:37.727 回答