支配集 (DS) := 给定一个无向图 G = (V;E),如果对于 V 中的每个顶点,S 中都有一个与 v 相邻的顶点,则一组顶点 SV 是支配集。整个顶点集V 是任何图中的平凡支配集。
找到一棵树的最小尺寸支配集。
1-总是从叶子开始
2-将他们的父母添加到DS并剪切孩子
3-将所选父母的父母标记为已经占主导地位
4-完成过程后,检查那些标记的节点是否有一个不被
支配的孩子并将它们添加到DS
祝你好运
我将尝试以更正式的方式证明这一点。
大纲
为了证明你的贪心算法是正确的,你需要证明两件事:
贪婪选择:在你的树 T = (V, E) 中,在树中找到一个顶点v,它的叶子数最多。将它添加到您的主导集。
最优子结构
T' = (V', E') 使得:
换句话说
寻找叶数最多的顶点,删除其度数小于或等于 2 的任何相邻顶点,然后删除 v 本身,并将其添加到您的优势集。重复此操作,直到您没有剩余顶点。
证明
贪心选择证明
对于任何叶子l,它必须是它自己或其父节点在主导集中。在我们的例子中,我们选择的顶点v就是在这种情况下。
令A = { v 1 , v 2 , ... , v k } 是 T 的最小优势集。如果 A 已经有v作为成员,我们就完成了。如果没有,我们会看到两种情况:
v有一些相邻的叶子l。那么, l必须是支配集的一部分,否则我们的集不会支配整个树。因此,我们可以简单地形成A' = { A - {l} + { v }} 并且仍然是一个优势集。自从 | 一个' | = | A |, A'仍然是最优的。
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的支配集: