算法导论35.1 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 2k 阅读时长 ≈ 2 分钟

35.1-1

令图$G=(V,E),V={a,b},E={(a,b)}$。可见，算法APPROX-VERTEX-COVER对图$G$产生的点覆盖大小总是为$2$（因为它将会把边$(a,b)$直接选出来，并将节点$a$和$b$添加到集合中），然而最小点覆盖仅仅是其中一个节点即可。因此在这个图上由APPROX-VERTEX-COVER产生的点覆盖总是次优的。

35.1-2

如果选出的边集$A$不是一个极大匹配，那么意味着存在一个匹配$A’$，使得$A\subsetneq A’$。考虑某一条边$(u,v)\in A’-A$。由于$A,A’$都是一组匹配，因此每个节点在所有边中只出现最多一次。这意味着删去$G=(V,E)$中的$A$中这$2|A|$个节点所有关联的边后，至少还剩下一条边$(u,v)$，算法APPROX-VERTEX-COVER的while循环不应该终止。因此，由算法APPROX-VERTEX-COVER第4行选出的编辑$A$是$G$的一个极大匹配。

$\star$ 35.1-3

假设当前有$n=|L|$个左部节点，其中$n$是一个盈数（即$n$的因子之和大于$2n$），我们将按如下方式构造这个二分图$G=(V,E)$：

1
2
3
4
5
6
7
8
9
10
11
CONSTRUCT-GRAPH(n):
  generate new vertex set L = {l_0, l_1, ..., l_{n - 1}}
  R = ∅
  E = ∅
  for each divisor d of n
    k = n / d
    generate new vertex set R' = {r_0, r_1, ..., r_{k - 1}}
    R = R ∪ R'
    for j = 0 to n - 1
      E = E ∪ {(l_{j}, r_{⌊j / i⌋})}
  return (L ∪ R, E)

也就是说，枚举$n$的每个因子$d$，令$k=n/d$，在右部生成$k$节点，这$k$个节点每个节点将连出$d$条边，连到这不相交的$n$个节点中。

接下来证明，如果这个启发式算法在点的度数相同的情况下，优先选择$R$中的节点，那么这个算法将会不停选择$R$中的节点，并且在$|R|>2|L|$的情况下，就会超过近似比$2$。

接下来首先证明这个算法会不停选择$R$中的节点。假设$n$一共有$\sigma0(n)$个因子，其中从小到大的第$i$个因子为$d_i$，那么必定有$d_i\ge i$，因为一个数的所有因子是正整数的子集。这意味着算法首先删除度数为$d{\sigma0(n)}$的所有右部节点，删除完成后，$L$中所有节点的度数都减少$1$；接下来删除度数为$d{\sigma_0(n)-1}$的所有右部节点，删除完成后，$R$中所有节点的度数都减少$1$……一直删除下去。由于总有$d_i\ge i$，因此删除的总是右部节点。

由于$n$是盈数，因此$\displaystyle{|R|=\sum_{d\mid n} d> 2n=2|L|}$。

最终证明了这个算法只要打破平等的策略不恰当，那么这个算法的近似比将会超过$2$。

35.1-4

假设当前的这棵树$T=(V,E)$的节点数超过$2$，否则$T$不会存在边。假设$L_T$是$T$的叶子节点，那么对于一个必定存在一个最小点覆盖$V’$使得$V’\cap L_T=\varnothing$，因为使用叶子节点$l$覆盖和$l$唯一关联的边$(l,u)$，不如使用$l$的唯一邻居$u$关联这条边，此外$u$还有可能覆盖其它边，因此选择$l$不会比选择$u$更优。由此这给出了一个贪心算法TREE-VERTEX-COVER-GREEDY，它的基本思想是，取出森林中某个度数为$1$的节点$l$，并得到和$l$唯一关联的边$(l,u)$，将$u$加入点覆盖中，并删去和$u$关联的所有边。由于每个节点和每条边最多只会遍历一次，因此其时间复杂度为$O(V+E)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
TREE-VERTEX-COVER-GREEDY(G)
  V = G.V
  E = G.E
  L = ∅
  let V' be a new list
  for each vetrex v in V
    // 点v目前的度数为1
    if G.deg(v) == 1
      L = L ∪ {v}
  while |L| != ∅
    select leaf l from L randomly
    let (l, u) be the incident edge of l
    L = L - {l}
    V = V - {u, l}
    INSERT(V', u)
    while an edge (u, v) in E such that incident to u
      E = E - {(u, v)}
      if G.deg(v) == 1
        L = L ∪ {v}
      else if G.deg(v) == 0
        L = L - {v}
        V = V - {v}
  return V'

上面的算法也很容易用贪心选择性质证明：假设$T$的一个最小点覆盖$V’$满足$V’\cap L_T\neq \varnothing$，那么令$l\in V’\cap L_T,(l,u)\in E$，可见$l$覆盖了边$(u,l)$。首先不可能有$u\in V’$，否则可以构造一个更优的最小点覆盖$V’-{ l}$。因此，令$V’’=(V’-{l})\cup{ u}$，那么集合$V’’$仍然覆盖了边$(u,l)$，并且有$|V’’|=|V’|$。因此这种贪心策略成立。

35.1-5

如果使用APPROX-VERTEX-COVER的修改版本求解最大团，那么这个算法对最大团问题不存在固定是近似比$\rho$。

假设现在有一个$n$个节点的图$G$，它存在一个大小为$k$的最小点覆盖，那么算法APPROX-VERTEX-COVER构造出的点覆盖至少为$2k$。

对于图$G$的补图$\overline{G}$，定理34.12证明了$\overline{G}$存在一个大小为$n-k$的最大团，那么这个算法的改版能够找到$\overline{G}$中大小至少为$n-2k$的团。因此这个求解最大团算法的近似值为$\rho=\dfrac{n-k}{n-\min{n,2k}}$。当$k\ge n/2$时，可见这个近似比值$\rho$的定义是毫无意义的。因此这种关系并不意味着它对最大团问题存在固定的近似比。