算法导论34 Problems 答案

发表于 分类于 阅读次数： 本文字数： 14k 阅读时长 ≈ 13 分钟

34-1

a

图\(G=(V,E)\)的一个独立集\(V'\)意味着以节点集合\(V'\)的子图不包含任何一条边。

这个判定性问题是：对于图\(G=(V,E)\)，是否存在一个大小至少为\(k\)的点集\(V'\subseteq V\)，使得\(\forall (u,v)\in E,\neg(u\in V'\land v\in V')\)均成立。

将这个问题定义成一种语言INDEPENDENT-SET：

\[\begin{aligned} \text{INDEPENDENT-SET}=\{\langle G, k\rangle:&G = (V, E)\text{ is an undirected graph, }\\ &k \ge 0\text{ is an integer, and}\\ &G\text{ contains a independent set at least }k\text{ vertex}\} \end{aligned}\]

首先证明INDEPENDENT-SET属于\(\text{NP}\)。对于一个集合\(V'\)，检验程序只需要对\(E\)中的所有边\((u,v)\)进行判断是否\(u,v\)都在\(V'\)中，以及判断是否满足\(|V'|\ge k\)即可。检验程序可以在多项式时间内运行，因此INDEPENDENT-SET属于\(\text{NP}\)。

接下来证明INDEPENDENT-SET是NP困难的，考虑使用团问题进行规约，即证明\(\text{CLIQUE}\le_P\text{INDEPENDENT-SET}\)。对于CLIQUE问题中的任意一个实例\(\langle G,k\rangle\)，规约算法\(F\)构造出如下一个INDEPENDENT-SET问题的实例\(\langle G',k'\rangle\)，使得\(G=(V,E)\)包含一个大小为\(k\)的团，当且仅当\(G'=(V',E)\)包含一个大小为\(k'\)的独立集。

规约过程是：令\(V'=V,E'=\overline{E}\)，即\(G'\)是\(G\)的补图，且\(k'=k\)。可见，\(G\)的补图可以在多项式时间内被求出来，因此规约算法\(F\)是多项式时间的。

现在证明\(G=(V,E)\)包含一个大小为\(k\)的团，当且仅当\(G'=(V,\overline{E})\)包含一个大小为\(k\)的独立集。

充分性：如果\(G\)中存在一个大小为\(k\)的团\(V_1\)，那么在\(G\)的补图\(G'\)中，节点集合\(V_1\)中的任意两点都没有\(\overline{E}\)中的边，因此\(V_1\)也是\(G'\)中的一个独立集。

必要性：如果\(G'\)中存在一个大小为\(k\)的独立集\(V_1\)，那么在\(G'\)的补图\(G\)中，节点集合\(V_1\)中的任意两点都有\(E\)中的边相连，因此\(V_1\)也是\(G\)中的一个团。

因此\(\text{CLIQUE}\le_P\text{INDEPENDENT-SET}\)。由于CLIQUE是NP完全的，那么INDEPENDENT-SET是NP困难的，也是NP完全的，原结论成立。

b

首先可以使用二分法，用于确定最大独立集的大小\(k\)，这仅需要\(O(\lg V)\)次使用INDEPENDENT-SET。接下来，由于移除一个顶点并不会以及其关联的所有边增大，因此考虑尝试移除每一个顶点，并使用INDEPENDENT-SET判断图中是否仍然有一个至少为\(k\)的独立集，如果仍然有，说明这个顶点不是必要的，可以删除。否则必须保留下来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
MAX-INDEPENDENT-SET(G)
  l = 1
  r = |G.V|
  while l < r
    mid = ⌊(l + r + 1) / 2⌋
    if INDEPENDENT-SET(G, mid) == 1
      l = mid
    else
      r = mid - 1
  k = l
  VI = ∅
  V = G.V
  E = G.V
  while V != ∅
    select v from V randomly
    V = V - {v}
    E' = E - {(w, v) : (w, v) ∈ E and w ∈ V}
    if INDEPENDENT-SET((V ∪ VI, E'), mid) == 1
      E = E'
    else
      VI = VI ∪ {v}
  return VI

c

如果图\(G=(V,E)\)的每个节点度数为\(2\)，那么这意味着\(G\)是由多个不相交的环\(C\)构成。遍历每个环\(C\)，那么这个环中不相邻的所有节点就是一个独立集（这保证了这些节点之间将不会有边进行连接，因此这是一个独立集，且是一个极大的独立集）。最终，所有环中的极大独立集拼起来，就是图\(G=(V,E)\)的最大独立集。具体过程由MAX-INDEPENDENT-SET-DEGREE-2给出，其时间复杂度为\(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
MAX-INDEPENDENT-SET-DEGREE-2(G)
  let vis[1 : |G.V|] be a new array by False
  S = ∅
  for each vertex u in G.V
    if vis[u] == false
      T = ∅
      cnt = 0
      while True
        if cnt % 2 == 1
          T = T ∪ {u}
        vis[u] = True
        cnt = cnt + 1
        // 表示u的两个相邻节点
        v = G.Adj[u, 0]
        w = G.Adj[u, 1]
        if vis[v] == False
          u = v
        else if vis[w] == False
          u = w
        else
          break
      S = S ∪ T
  return S

d

首先考虑图\(G=(V,E)\)最大独立集问题和最小点覆盖问题的可规约性：对于一个点覆盖\(V'\)，在图\(G=(V,E)\)中，将\(V'\)和\(V'\)关联的所有边删去后，剩下的图不会含有任何一条边，因此\(V-V'\)是\(G\)的一个独立集。因此对于\(G\)的一个最小点覆盖\(V_0\)，那么得知\(V-V_0\)就是图\(G\)的一个最大独立集。

接下来考虑二分图\(G\)下最小点覆盖问题和最大匹配的问题的等价性。

首先说明图\(G=(V,E),V=L\cup R\)的最小点覆盖中的点数不可能小于最大匹配的边数，因为最大匹配是由多条不相交的边构成的，这些边都至少需要一个顶点进行覆盖。接下里证明图\(G\)最小点覆盖中的点数恰好为最大匹配的边数。

考虑如下一个构造方法，最终通过二分图最大匹配算法得到二分图的最小点覆盖：

  1. 求出\(G\)的最大匹配。
  2. 再次从\(L\)中所有节点非匹配节点出发，寻找一条增广路径（且一定寻找失败）。
  3. 取\(L\)中尚未被标记的节点\(L_0\)，\(R\)中被标记过的节点\(R_0\)，这些顶点构成了\(G\)的一个最小点覆盖\(V_0=L_0\cup R_0\)。

接下来证明这个方法构造出来的\(V_0\)是一个最小点覆盖。运行完整个增广路径算法后，对于\(L\)中的非匹配节点，它们一定都被标记，因为它们是出发点；而对于\(R\)中非匹配节点，它们一定都没有被标记，否则就找到了一条增广路径。对于一条匹配边，两边的节点要么被标记，要么没有被标记，因为左部节点只能通过匹配边从右部节点进行访问。

可以发现，\(L_0\)和\(R_0\)恰好是从最大匹配中，来自每条边的两个节点之一。\(L_0\)中节点所对应的匹配边，是指增广路径算法中没有访问的边；\(R_0\)中节点所对应的匹配边，是指增广路径算法中有访问的边。接下来验证这个点覆盖确实覆盖了所有边：

  1. 左部节点\(l\in L\)是非匹配点，右部节点\(r\in R\)也是非匹配点。这种边是不可能存在的，因为这是一条增广路径。
  2. \(l\)是匹配点，\(r\)也是匹配点。这种边被覆盖了，因为每条匹配边的其中一个节点都在\(V_0\)中。
  3. \(l\)是匹配点，\(r\)是非匹配点。这说明\(l\)没有被访问到，否则找到了通向\(r\)的增广路径，因此这条边是被\(L_0\)中的节点覆盖。
  4. \(l\)是非匹配点，\(r\)是匹配点。因为起点是\(l\)，所以\(r\)一定被访问，因此这条边是被\(R_0\)中的节点覆盖。

自此证明了最大匹配问题和最小点覆盖问题的等价性。可以给出如下过程MAX-INDEPENDENT-SET-BIPARTITE，其时间复杂度取决于增广路径算法的时间复杂度，因此这个算法是多项式时间的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
MAX-INDEPENDENT-SET-BIPARTITE(G)
  M = HOPCROFT-KARP(G)
  // 记录被标记的节点
  construct GM from M and G
  Q = Ø
  L0 = Ø
  R0 = Ø
  for each unmatched vertex l ∈ L
    l.π = NIL
    ENQUEUE(Q, l)
    L0 = L0 ∪ {l}
  while Q != Ø
    u = DEQUEUE(Q)
    for each v in GM.Adj[u]
      if v in L and v not in L0
        L0 = L0 ∪ {v}
        ENQUEUE(Q, v)
      else if v in R and v not in R0
        R0 = R0 ∪ {v}
        ENQUEUE(Q, v)
  V0 = (L - L0) ∪ R0
  return V - V0

34-2

a

这是一个多项式时间的算法即可完成。

当钱的总数为奇数时，必定无法分成。

假设有\(a\)枚\(x\)美元的硬币，\(n-a\)枚\(y\)美元的硬币，那么这些钱的总共的价值为\(ax+(n-a)y\)，那么每一个人将分得\(s=\dfrac{ax+(n-a)y}{2}\)块钱。

接下来使用扩展欧几里得算法对关于\((u,v)\)的方程\(xu+yu=s\)进行求解，并尝试找到一个满足\(0\le u\le a,0\le v\le n-a\)的整数解，这将在多项式的时间内完成。更具体的过程由DIVIDING-MONEY-A给出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
DIVIDING-MONEY-A(a, n, x, y)
  b = n - a
  s = (a * x + b * y)
  if s % 2 != 0
    return 0
  s = s / 2
  (d, u, v) = EXTENDED-EUCLID(x, y)
  if s % d != 0
    return 0
  u0 = (u * (s / d)) % y
  // 求取使u满足u<=a的最大解。
  u1 = u0 + ⌊(a - u0) / (y / d)⌋ * (y / d)
  v1 = (s - u1 * x) / y
  if 0 <= u1 <= a and 0 <= v1 <= b
    return 1
  v0 = (v * (s / d)) % x
  // 求取使v满足v<=b的最大解。
  v2 = v0 + ⌊(b - v0) / (x / d)⌋ * (x / d)
  u2 = (s - v2 * y) / x
  if 0 <= u2 <= a and 0 <= v2 <= b
    return 1
  return 0

b

这是一个多项式时间的算法即可完成。将所有币依照币值大小从大到小分配，每次分配给持有币值总数较小的那个人，更具体的过程由DIVIDING-MONEY-B给出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
DIVIDING-MONEY-B(X, n)
  Bonnie-s = 0
  Clyde-s = 0
  RANDOMIZED-QUICKSORT(X, 1, n)
  for i = n downto 1
    if Bonnie-s <= Clyde-s
      Bonnie-s = Bonnie-s + X[i]
      X[i] will be assigned to Bonnie
    else
      Clyde-s = Clyde-s + X[i]
      X[i] will be assigned to Clyde
  if Bonnie-s == Clyde-s
    return 1
  else
    return 0

可见，这个算法是多项式的，接下来说明这个算法能够正确地运行。假设现在遍历到\(x_i\)，Bonnie得到了\(s_B\)美元，Clyde得到了\(s_C\)美元。如果当前\(2\)个人得到的钱相等，那么将\(x_i\)可以随机分配给一个人，不失一般性，假设分配给了Bonnie，因此在整个过程中，总有\(s_B\ge s_C\)。如果现在\(s_B>s_C\)，由于\(\forall j\le i,x_i\mid x_j\)均成立，因此总有\(x_i\mid s_B-s_C\)，并假设分配\(x_{i-1}\)之前，有\(s_B=s_C\)（这样的起点\(i\)必定存在，例如\(i=2\)，在分配\(x_1\)给\(B\)前有\(s_B=s_C\)），那么接下来按顺序将所有钱都给Clyde，直到\(s_B=s_C\)这个临界点，如果能够达到\(s_B=s_C\)，那么以这个临界点为下一个起点。否则说明接下来剩下的钱都不足以弥补当前\(s_B-s_C\)的差值。因此，DIVIDING-MONEY-B是多项式时间内可行的算法。

c

这恰好是题目34.5-5所提到的集合划分问题SET-PARTITION，它已经被证明是NP完全的。

d

这个问题是NP完全的，如下是证明。

先将这个问题定义成一种语言SET-PARTITION-100：

\[\text{SET-PARTITION-100} = \left\{\langle S\rangle : \text{there exists a set }A\subseteq S\text{ such that }\left|\sum_{x\in A} x-\sum_{x\in\overline{A}}x\right|\le 100\right\}\]

首先证明SET-PARTITION-100属于\(\text{NP}\)。对于\(S\)和它的一个非空子集\(A\)，检验程序只需要判断\(\displaystyle{\left|\sum_{x\in A} x-\sum_{x\in\overline{A}}x\right|\le 100}\)是否满足即可，它可以在多项式时间内运行，因此SET-PARTITION-100属于\(\text{NP}\)。

接下来证明SET-PARTITION-100是NP困难的，考虑使用集合划分问题进行规约，即证明\(\text{SET-PARTITION}\le_P\text{SET-PARTITION-100}\)。对于SET-PARTITION问题中的任意一个实例\(\langle S\rangle\)，规约算法\(F\)构造出如下一个SET-PARTITION-100问题的实例\(\langle S'\rangle\)，使得\(S\)能够划分成两个和值相等的子集，当且仅当\(S'\)能够划分成两个和值相差不超过\(100\)的子集。

规约过程是：令\(S'=\{101x\mid x\in S\}\)。可见只是将集合\(S\)中的每个数乘上\(101\)，再将它插入集合\(S'\)。可见这个过程是多项式可以完成的。

现在证明\(S\)能够划分成两个和值相等的子集，当且仅当\(S'\)能够划分成两个和值相差不超过\(100\)的子集。

充分性：如果\(S\)能够划分成两个和值相等的集合\(A,\overline{A}\)，将\(A,\overline{A}\)中的所有元素都乘上\(101\)，得到\(A',\overline{A'}\)。可见\(A',\overline{A'}\)也是\(S'\)的一个划分，并且差值为\(0\cdot 101=0\)，因此\(A',\overline{A'}\)为\(S'\)一个满足条件的划分。

必要性：假设\(S'\)包含两个和值相差不超过\(100\)的集合\(A',\overline{A'}\)。由于\(S'\)中所有数都是\(101\)的倍数，因此\(A',\overline{A'}\)的元素和也都是\(101\)的倍数，因此如果要满足假设，两个集合的元素和必须相等。因此，将\(A',\overline{A'}\)中的所有元素都除上\(101\)，得到\(A,\overline{A}\)。可见\(A,\overline{A}\)是\(S\)一个满足条件的划分。

因此\(\text{SET-PARTITION}\le_P\text{SET-PARTITION-100}\)。由于SET-PARTITION是NP完全的，那么SET-PARTITION-100是NP困难的，也是NP完全的，原结论成立。

34-3

a

题目20.2-7所给出的判断二分图的算法即为所求，其时间复杂度为\(O(V+E)\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
DETERMINE-WRESTLERS(G)
  for each vertex u in G.V
    u.type = NIL
  for each vertex s in G.V
    if s.type == NIL
      s.type = babyface
      Q = ∅
      ENQUEUE(Q, s)
      while Q != ∅ 
        u = DEQUEUE(Q)  
        for each vertex v in G.Adj[u] 
          if v.type == NIL
            if u.type == babyface
              v.type = heel
            else
              v.type = babyface
            ENQUEUE(Q, s)
          else if v.type == u.type
            return NIL
  return G.V

b

这个判定性问题是：对于图\(G=(V,E)\)，是否至多可以用\(k\)种颜色进行着色。假设判定性问题的语言定义为K-COLOR：

\[\begin{aligned} \text{K-COLOR}=\{\langle G, k\rangle:&G = (V, E)\text{ is an undirected graph, }\\ &k \ge 1\text{ is an integer, and}\\ &\text{there exists a function }c:V\rightarrow\{1,2,\dots,k\}\text{ such that } \forall (u,v)\in E,c(u)\neq c(v)\} \end{aligned}\]

接下来证明K-COLOR能够在多项式时间内能够解决，当且仅当图着色问题可以在多项式时间内解决。

必要性：显而易见，图着色问题如果能够在多项式算法内解决，那么K-COLOR只需要统计图着色问题求解中所使用的颜色个数\(k'\)，再判断是否不超过给定的\(k\)值即可。因此K-COLOR也可以在多项式时间内解决。

充分性：假设K-COLOR多项式时间内可解决。可见，只需要最多\(|V|\)种颜色，就可以将图\(G\)完成着色。因此图着色问题考虑使用K-COLOR作为子程序，依照二分法的思想，即可能够判断出对图\(G\)的着色最少颜色数，那么图着色问题至多只需要询问\(O(\lg V)\)次K-COLOR。由于K-COLOR是多项式时间内可解决的，因此图着色问题也是多项式时间内可解决的。

因此原结论成立。

c

首先证明K-COLOR属于\(\text{NP}\)。对于\(G\)和它的一个着色函数\(c\)，检验程序只需要判断是否\(\forall (u,v)\in E,c(u)\neq c(v)\)均成立，并判断\(c(u)\)的取值是否在\([1,k]\)中即可。它可以在多项式时间内运行，因此K-COLOR属于\(\text{NP}\)。

接下来证明K-COLOR是NP困难的，考虑使用三着色问题进行规约，即证明\(\text{3-COLOR}\le_P\text{K-COLOR}\)。对于3-COLOR问题中的任意一个实例\(\langle G\rangle\)，规约算法\(F\)构造出如下一个K-COLOR问题的实例\(\langle G,k\rangle\)，使得图\(G\)是\(3\)着色的，当且仅当图\(G\)是\(k\)着色的。

规约过程是：只需要令\(k=3\)即可。

现在证明图\(G\)是\(3\)着色的，当且仅当图\(G\)是\(k\)着色的。当\(k=3\)时，这两个问题是两个完全相同的问题，因此充分性和必要性均成立。

因此\(\text{3-COLOR}\le_P\text{K-COLOR}\)。由于题目已经假设了3-COLOR是NP完全的，因此K-COLOR是NP困难的，也是NP完全的，原结论成立。

d

在图\(G=(V,E)\)中，\(3\)个特殊节点\(\text{RED,TRUE,FALSE}\)两两相连，因此\(G\)中的\(3\)中颜色只能用\(c(\text{RED}),c(\text{TRUE}),c(\text{FALSE})\)分别表示。从图34.20中可以看出，\(\forall i\in[1,n]\)，节点\(x_i,\neg x_i,\text{RED}\)这\(3\)个节点两两相连，因此\(x_i\)和\(\neg x_i\)这两个节点只能其中一个着色为\(c(\text{TRUE})\)，另一个为\(c(\text{FALSE})\)。

对于每对节点\(x_i,\neg x_i\)，如果公式在公式\(\phi\)中，最终\(x_i\)赋值为\(1\)，那么节点\(x_i\)着色为\(c(\text{TRUE}),\neg x_i\)着色成\(c(\text{FALSE})\)；如果\(x_i\)赋值为\(0\)，那么节点\(x_i\)着色为\(c(\text{FALSE}),\neg x_i\)着色成\(c(\text{TRUE})\)即可。

因此，对于\(\phi\)中的任意一种赋值，都对应着只包含文字的图的其中一种\(3\)着色。

e

假设将每个组件中，先从左到右，再从上到下的\(5\)个节点分别命名为\(a,b,c,d,e\)。

那么考虑枚举节点\(x,y,z,a,b,c,d,e\)的着色情况，一共有\(2^3\cdot3^5\)种不同的情况。对每种情况进行判断，最终可以得到一个组件图中有如下\(3\)着色的方式，一共有\(20\)种：

\(\begin{array}{|c|c|c|c|c|c|c|c|}\hline x&y&z&a&b&c&d&e\\\hline c\text{(TRUE)}&c\text{(FALSE)}&c\text{(FALSE)}&c\text{(FALSE)}&c\text{(RED)}&c\text{(TRUE)}&c\text{(FALSE)}&c\text{(RED)}\\\hline c\text{(TRUE)}&c\text{(FALSE)}&c\text{(FALSE)}&c\text{(FALSE)}&c\text{(TRUE)}&c\text{(RED)}&c\text{(FALSE)}&c\text{(RED)}\\\hline c\text{(FALSE)}&c\text{(TRUE)}&c\text{(FALSE)}&c\text{(RED)}&c\text{(FALSE)}&c\text{(TRUE)}&c\text{(FALSE)}&c\text{(RED)}\\\hline c\text{(FALSE)}&c\text{(TRUE)}&c\text{(FALSE)}&c\text{(TRUE)}&c\text{(FALSE)}&c\text{(RED)}&c\text{(FALSE)}&c\text{(RED)}\\\hline c\text{(TRUE)}&c\text{(TRUE)}&c\text{(FALSE)}&c\text{(RED)}&c\text{(FALSE)}&c\text{(TRUE)}&c\text{(FALSE)}&c\text{(RED)}\\\hline c\text{(TRUE)}&c\text{(TRUE)}&c\text{(FALSE)}&c\text{(FALSE)}&c\text{(RED)}&c\text{(TRUE)}&c\text{(FALSE)}&c\text{(RED)}\\\hline c\text{(FALSE)}&c\text{(FALSE)}&c\text{(TRUE)}&c\text{(RED)}&c\text{(TRUE)}&c\text{(FALSE)}&c\text{(RED)}&c\text{(FALSE)}\\\hline c\text{(FALSE)}&c\text{(FALSE)}&c\text{(TRUE)}&c\text{(TRUE)}&c\text{(RED)}&c\text{(FALSE)}&c\text{(RED)}&c\text{(FALSE)}\\\hline c\text{(TRUE)}&c\text{(FALSE)}&c\text{(TRUE)}&c\text{(RED)}&c\text{(TRUE)}&c\text{(FALSE)}&c\text{(RED)}&c\text{(FALSE)}\\\hline c\text{(TRUE)}&c\text{(FALSE)}&c\text{(TRUE)}&c\text{(FALSE)}&c\text{(RED)}&c\text{(TRUE)}&c\text{(RED)}&c\text{(FALSE)}\\\hline c\text{(TRUE)}&c\text{(FALSE)}&c\text{(TRUE)}&c\text{(FALSE)}&c\text{(RED)}&c\text{(TRUE)}&c\text{(FALSE)}&c\text{(RED)}\\\hline c\text{(TRUE)}&c\text{(FALSE)}&c\text{(TRUE)}&c\text{(FALSE)}&c\text{(TRUE)}&c\text{(RED)}&c\text{(FALSE)}&c\text{(RED)}\\\hline c\text{(FALSE)}&c\text{(TRUE)}&c\text{(TRUE)}&c\text{(TRUE)}&c\text{(RED)}&c\text{(FALSE)}&c\text{(RED)}&c\text{(FALSE)}\\\hline c\text{(FALSE)}&c\text{(TRUE)}&c\text{(TRUE)}&c\text{(RED)}&c\text{(FALSE)}&c\text{(TRUE)}&c\text{(RED)}&c\text{(FALSE)}\\\hline c\text{(FALSE)}&c\text{(TRUE)}&c\text{(TRUE)}&c\text{(RED)}&c\text{(FALSE)}&c\text{(TRUE)}&c\text{(FALSE)}&c\text{(RED)}\\\hline c\text{(FALSE)}&c\text{(TRUE)}&c\text{(TRUE)}&c\text{(TRUE)}&c\text{(FALSE)}&c\text{(RED)}&c\text{(FALSE)}&c\text{(RED)}\\\hline c\text{(TRUE)}&c\text{(TRUE)}&c\text{(TRUE)}&c\text{(RED)}&c\text{(FALSE)}&c\text{(TRUE)}&c\text{(RED)}&c\text{(FALSE)}\\\hline c\text{(TRUE)}&c\text{(TRUE)}&c\text{(TRUE)}&c\text{(FALSE)}&c\text{(RED)}&c\text{(TRUE)}&c\text{(RED)}&c\text{(FALSE)}\\\hline c\text{(TRUE)}&c\text{(TRUE)}&c\text{(TRUE)}&c\text{(RED)}&c\text{(FALSE)}&c\text{(TRUE)}&c\text{(FALSE)}&c\text{(RED)}\\\hline c\text{(TRUE)}&c\text{(TRUE)}&c\text{(TRUE)}&c\text{(FALSE)}&c\text{(RED)}&c\text{(TRUE)}&c\text{(FALSE)}&c\text{(RED)}\\\hline \end{array}\)

按照上面的表可以发现，这个组件图如果是\(3\)着色的，那么\(x,y,z\)必定有一个着色成\(c\text{(TRUE)}\)，原结论成立。

需要注意的是，只要\(x,y,z\)不同时被着色成\(c\text{(FALSE)}\)，那么另外\(7\)种组合着色情况都是有对应的\(3\)着色方案对应着。

f

首先证明3-COLOR属于\(\text{NP}\)。这个证明过程和题目34-3-c相同，只需要取\(k=3\)即可。因此3-COLOR属于\(\text{NP}\)。

接下来证明3-COLOR是NP困难的，考虑使用3-CNF可满足性问题问题进行规约，即证明\(\text{3-CNF-SAT}\le_P\text{3-COLOR}\)。对于3-CNF-SAT问题中的任意一个实例\(\langle \phi\rangle\)，规约算法\(F\)构造出如下一个3-COLOR问题的实例\(\langle G\rangle\)，使得3-CNF布尔公式\(\phi\)是可满足的，当且仅当图\(G\)是\(3\)着色的。

规约过程是：按照题目34-3-c和题目34-3-d之间的提示构造出了一个图\(G=(V,E)\)。\(V\)一共有\(2n+5m+3\)个节点，其中包含了\(2n\)个文字节点，\(m\)个组件中，每个组件有\(5\)个节点，以及\(3\)个特殊节点；\(E\)一共有\(3n+10m+3\)条边，其中有\(3n+3\)条文字边，\(10m\)条子句边。因此\(G\)可以在多项式时间内构造出来，故规约算法\(F\)是多项式时间的。

现在证明3-CNF布尔公式\(\phi\)是可满足的，当且仅当图\(G\)是\(3\)着色的。

充分性：由于\(\phi\)是可满足的，因此考虑其中一组可满足行赋值，并将\(2n\)个文字节点然上对应的颜色。这也意味着，对于所有子句\(\phi_i\)，每个子句至少有一个文字的值为\(1\)。可以在表中选择对应的表项，将图\(G\)中对应的组件内部的\(5\)个节点染上表项对应颜色。因此，每个文字节点和组件内部的节点颜色都不会和相邻节点颜色相同，所求着色方式说明图\(G\)是\(3\)着色的。

必要性：由于图\(G\)是\(3\)着色的，因此存在一种\(3\)着色方案。对于图\(G\)的第\(i\)个组件，它的着色方式必定是\(20\)个表项之一，然而所有表项中，\(x,y,z\)三个节点必定其中一个着色为\(c(\text{TRUE})\)，因此\(\phi_i\)对应文字也为\(1\)，对于其它子句也是如此。此外，这个\(3\)着色方案中，如果\(x_i\)被染成\(c(\text{TRUE})\)，那么\(x_i\)赋值为\(1\)，否则赋值为\(0\)。最终这个着色方案意味着这个3-CNF公式\(\phi\)是可满足的。

因此\(\text{3-CNF-SAT}\le_P\text{3-COLOR}\)。由于3-CNF-SAT是NP完全的，因此3-COLOR是NP困难的，也是NP完全的，原结论成立。

34-4

a

这个判定性问题是：是否存在一个\(n\)阶排列\(\sigma\)，使得按照顺序\(a_{\sigma(1)},a_{\sigma(2)},\dots,a_{\sigma(n)}\)执行任务，可以获得至少\(k\)的利润。可以将这个判定问题定义成一种语言K-PROFIT-DEADLINES：

\[\begin{aligned} \text{K-PROFIT-DEADLINES}=\{\langle A, k\rangle:&A=\{a_1,a_2,\dots,a_n\}\text{ is a tasks set, }\\ &k \ge 0\text{ is an integer, and}\\ &\text{there exists a sequence to finish thest task and get at least profit }k\} \end{aligned}\]

b

首先证明K-PROFIT-DEADLINES属于\(\text{NP}\)。给定一个任务清单\(A\)和整数\(k\)，以及一个完成顺序\(\sigma\)，检验程序需要模拟这些任务的完成时间，并且需要判断完成时间是否会超过截止时间，如果没有超过截止时间就算上利润\(p_i\)，最终判断获得的总利润\(k'\)是否超过\(k\)即可。因此检验程序可以在多项式时间内完成模拟，因此K-PROFIT-DEADLINES属于\(\text{NP}\)。

接下来证明K-PROFIT-DEADLINES是NP困难的，考虑使用子集和问题问题进行规约，即证明\(\text{SUBSET-SUM}\le_P\text{K-PROFIT-DEADLINES}\)。对于SUBSET-SUM问题中的任意一个实例\(\langle S,t\rangle\)，规约算法\(F\)构造出如下一个K-PROFIT-DEADLINES问题的实例\(\langle A,k\rangle\)，使得\(S\)包含一个和为\(t\)的子集，当且仅当\(A\)中的任务按照某个顺序执行，能够获得至少\(k\)的利润。

规约过程是：对于集合\(S\)中的第\(i\)个数\(x_i\)，可以构造如下任务\(a_i:t_i=x_i,p_i=a_i,d_i=t\)。此外，至少得到利润\(k=t\)。可见这个规约过程仅仅是将\(S\)中的每个数都建立了一个任务，并且添加了一个数\(t\)作为利润上限。这些内容可以在多项式时间内构造出来，因此规约算法\(F\)是多项式时间的。

现在证明\(S\)包含一个和为\(t\)的子集，当且仅当\(A\)中的任务按照某个顺序执行，能够获得至少\(t\)的利润。

充分性：如果\(S\)包含一个和为\(t\)的子集\(S'\)，那么只需要按任意顺序执行\(S'\)在中\(A'\)对应的任务（\(A-A'\)的任务按随意顺序执行，反正得不到利润），就可以得到恰好\(t\)的利润，这个任务执行计划是满足要求的。

必要性：假设\(A\)中的任务按某种顺序执行可以得到至少\(t\)利润。由于\(A\)中所有任务的截止时间都相等（均为\(t\)），因此在\(t\)时间前执行的任务并不需要固定的顺序。此外，由于每个任务单位时间内所获得的利润都是\(1\)，因此在时间\(t\)内，恰好只能获得利润\(t\)。也就是说，存在一个\(A\)子集\(A'\)，其利润之和恰好为\(t\)。将集合\(A'\)中的任务映射回\(S\)中的数，那么就得到了一个子集和为\(t\)的集合。

因此\(\text{SUBSET-SUM}\le_P\text{K-PROFIT-DEADLINES}\)。由于SUBSET-SUM是NP完全的，因此K-PROFIT-DEADLINES是NP困难的，也是NP完全的，原结论成立。

c

由于超过了任务期限后再完成任务，再也不能得到利润，因此我们可以先选择尽力完成一部分能够得到利润的任务，再完成剩下的另一部分任务。选定了一部分任务后，只有按照截止日期按顺序完成，才能够达到最大利润。因此需要对任务按照截止时间进行排序。

令状态\(f[i,j](i,j\ge 0)\)表示时间\(j\)内完成前\(i\)个任务所能获得最大的利润。那么不难写出关于\(f[i,j]\)的状态转移方程：

\(f[i,j]= \left \{\begin{aligned} &0 & & \text{if}\quad i=0 \\ &f[i-1,j] & & \text{if}\quad i>0\land(j<t_i\lor j>d_i) \\ &\max\{f[i-1,j-t_i]+p_i,f[i-1,j]\} & & \text{if}\quad i>0\land(t_i\le j\land j\le d_i) \\ \end{aligned}\right.\)

那么对于状态\(f[i,j]\)，要么不完成（或者无法完成）第\(i\)个任务，从\(f[i-1,j]\)转移过来，要么尽力完成第\(i\)个任务，并获得\(p_i\)的利润，从\(f[i-1,j-t_i]\)转移而来。

至此，\(\displaystyle{f[n,T]}\)则是可以获得的最大利润，其中\(\displaystyle{T=\sum_{i=1}^n t_i}\)。

由于此时仅要求给出的是一个判定性算法，因此只需要对至少获取的利润\(k\)和\(f[n,T]\)进行比较即可。具体过程由程序K-PROFIT-DEADLINES'给出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//A中每个任务都带有3个属性t, p, d，分别表示任务的运行时间，利润以及截止时间。
K-PROFIT-DEADLINES'(A, n, k)
  sort A[1 : n] by attribute d
  T = 0
  for i = 1 to n
    T = T + A[i].t
  let f[0 : n, 0 : T] be a new table by 0
  for i = 1 to n
    for j = 1 to T
      f[i, j] = f[i - 1, j]
    A[i].d = min{A[i].d, T}
    for j = A[i].t to A[i].d
      f[i, j] = min{f[i, j], f[i - 1, j - A[i].t] + A[i].p}
  return f[i, T] >= k

由于每个任务的运行时间不超过\(n\)，因此\(T\le n^2\)。因此算法K-PROFIT-DEADLINES'的时间复杂度为\(O(nT)=O(n^3)\)，它是多项式的。

d

题目34-c的动态规划算法即可直接计算出最大利润值。修改后的程序为PROFIT-DEADLINES，它的时间复杂度同样为\(O(n^3)\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
PROFIT-DEADLINES(A, n)
  sort A[1 : n] by attribute d
  T = 0
  for i = 1 to n
    T = T + A[i].t
  let f[0 : n, 0 : T] be a new table by 0
  for i = 1 to n
    for j = 1 to T
      f[i, j] = f[i - 1, j]
    A[i].d = min{A[i].d, T}
    for j = A[i].t to A[i].d
      f[i, j] = min{f[i, j], f[i - 1, j - A[i].t] + A[i].p}
  return f[i, T]