即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

算法概论8.9解答

编程语言 jessir 10℃ 0评论

题目:这里写图片描述

证明:可以将最小顶点覆盖规约到HITTING SET。假设要求图G的最小顶点覆盖,可以建立一个HITTING SET实例,其中S1,S2,…,Sn是图G的各条边,比如{v1,v2},{v3,v4},…。通过二分式的询问,可以找到一个与Si都相交的最小集合H,这正好就是图G的最小顶点覆盖。

转载请注明:CodingBlog » 算法概论8.9解答

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情