大数据

当前位置:首页 > 大数据

《算法导论》第三十四章(续6)

34.5.2顶点覆盖问题

无向图G=(V,E)的顶点覆盖(vertex cover)是一个子集V'cV,满足如果有(u,v)∈E,则u∈V'或v∈V(或两者同时成立)。也就是说,每个顶点“覆盖”与其相关联的边,并且G的顶点覆盖是覆盖E中所有边的顶点所组成的集合。顶点覆盖的规模是指它所包含的顶点数。例如,图34-15(b)中有一个规模为2的顶点覆盖{w,z}。

QQ截图20220812114811.png

顶点覆盖问题是指在一个给定的图中,找出具有最小规模的顶点覆盖。把这一最优化问题重新表述为一个判定问题,即确定一个图是否具有一个给定规模k的顶点覆盖。作为一种语言,我们定义

VERTEX-COVER={<G,k>:图G有一个规模为k的顶点覆盖}

下面的定理证明了这一问题是一个NP完全的。

定理34.12 顶点覆盖问题是NP完全的。

证明 首先来证明VERTEX-COVER∈NP。假定已知一个图G=(V,E)和整数k,我们选取的证书是顶点覆盖V'CV自身。验证算法可证实|V'|=k,然后对每条边(u,v)∈E,检查是否有u∈V'或v∈V'。我们可以很容易在多项式时间内验证这一问题。

我们通过证明CLIQUE≤VERTEX-COVER来证明顶点覆盖问题是NP难度的。这一归约过程是以“补图”的概念为基础的。给定一个无向图G=(V,E),定义G的补图G=(V,E),其中E一{(u,v):u,v∈V,u≠v,(u,v)∈E}。换句话说,G是正好包含不在G中的那些边的图。图34-15显示出了一个图与其补图,并说明了从CLIQUE到VERTEX-COVER的归约过程。

归约算法的输人是团问题的实例(G,k)。它计算出补图G,这很容易在多项式时间内完成。归约算法的输出是顶点覆盖问题的实例(G,|V|-k)。为了完成证明,下面来说明该变换的确是一个归约过程:图G具有一个规模为k的团,当且仅当图G有一个规模为|VI一k的顶点覆盖。

假设G包含一个团V'cV,其中|VI=k。我们断言:V一V'是G中的一个顶点覆盖。设(u,v)是E中的任意边,则有(u,v)E,这证明了u或v中至少有一个不属于V',这是由于V'中每--对顶点间都至少有一条E中的边与其相连。等价地,v或u中至少有一个属于V一V',这意味着边(u,v)是被V一V'所覆盖。由于(u,zv)是从E中任意选取的边,所以E的每条边都被V一V中的一个顶点所覆盖。因此,规模为|V|一k的集合V一V'形成了G的一个顶点覆盖。

反之,假设G具有一个顶点覆盖V'CV,其中|V'|=|V|一k。那么,对所有u,v∈V,如果(u,v)∈E,则u∈V'或u∈V'或两者同时成立。与此相对,对所有u,v∈V,如果uEV'且vEV',则(u,v)∈E。换句话说,V一V'是一个团,其规模为|V|一IV'l一k。

由于VERTEX-COVER是NP完全的,所以我们并不期望能找出一种多项式时间的算法来寻找最小规模的顶点覆盖。然而,35.1节介绍了一种多项式时间的“近似算法”,它可以产生顶点覆盖问题的“近似”解。该算法所产生的顶点覆盖的规模至多为最小规模顶点覆盖的2倍。

因此,我们不应该因为某个问题是NP完全的而放弃希望。对这样的问题,尽管寻找其最优解是NP完全问题,但依然可能设计出某种多项式时间的近似算法,来获得它的近似最优解。第35章介绍了几个NP完全问题的近似算法。


相关内容

文章评论

表情

共 0 条评论,查看全部
  • 这篇文章还没有收到评论,赶紧来抢沙发吧~