算法导论35.1 Exercises 答案

发表于 分类于 阅读次数： 本文字数： 2.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\)一共有\(\sigma_0(n)\)个因子，其中从小到大的第\(i\)个因子为\(d_i\)，那么必定有\(d_i\ge i\)，因为一个数的所有因子是正整数的子集。这意味着算法首先删除度数为\(d_{\sigma_0(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\)的定义是毫无意义的。因此这种关系并不意味着它对最大团问题存在固定的近似比。