算法导论 34 Problems 答案

34-1

a

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

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

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

$$\begin{array}{rl}\text{INDEPENDENT-SET}=\{⟨G,k⟩:& G=(V,E)\text{ is anundirected graph, }\\ & k\ge 0\text{ is an integer, and}\\ & G\text{ contains a independent set at least }k\text{ vertex}\}\end{array}$$

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

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

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

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

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

必要性：如果 $G^{\prime }$ 中存在一个大小为 $k$ 的独立集 $V_1$，那么在 $G^{\prime }$ 的补图 $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$ 的独立集，如果仍然有，说明这个顶点不是必要的，可以删除。否则必须保留下来。

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)$。

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^{\prime }$，在图 $G=(V,E)$ 中，将 $V^{\prime }$ 和 $V^{\prime }$ 关联的所有边删去后，剩下的图不会含有任何一条边，因此 $V-V^{\prime }$ 是 $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，其时间复杂度取决于增广路径算法的时间复杂度，因此这个算法是多项式时间的。

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={\displaystyle \frac{ax+(n-a)y}{2}}$ 块钱。

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

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 给出：

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$，由于 $\mathrm{\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}=\{⟨S⟩:\text{there exists a set }A\subseteq S\text{ such that }|\sum _{x\in A}x-\sum _{x\in \bar{A}}x|\le 100\}$$

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

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

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

现在证明 $S$ 能够划分成两个和值相等的子集，当且仅当 $S^{\prime }$ 能够划分成两个和值相差不超过 $100$ 的子集。

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

必要性：假设 $S^{\prime }$ 包含两个和值相差不超过 $100$ 的集合 $A^{\prime },\overline{A^{\prime }}$。由于 $S^{\prime }$ 中所有数都是 $101$ 的倍数，因此 $A^{\prime },\overline{A^{\prime }}$ 的元素和也都是 $101$ 的倍数，因此如果要满足假设，两个集合的元素和必须相等。因此，将 $A^{\prime },\overline{A^{\prime }}$ 中的所有元素都除上 $101$，得到 $A,\bar{A}$。可见 $A,\bar{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)$。

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{array}{rl}\text{K-COLOR}=\{⟨G,k⟩:& G=(V,E)\text{ is anundirected graph, }\\ & k\ge 1\text{ is an integer, and}\\ & \text{there exists a function }c:V\to \{1,2,\dots ,k\}\text{ such that }\mathrm{\forall }(u,v)\in E,c(u)\ne c(v)\}\end{array}$$

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

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

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

因此原结论成立。

c

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

接下来证明 K-COLOR 是 NP 困难的，考虑使用三着色问题进行规约，即证明 $\text{3-COLOR}{\le }_P\text{K-COLOR}$。对于 3-COLOR 问题中的任意一个实例 $⟨G⟩$，规约算法 $F$ 构造出如下一个 K-COLOR 问题的实例 $⟨G,k⟩$，使得图 $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 中可以看出，$\mathrm{\forall }i\in [1,n]$，节点 $x_i,\mathrm{\neg }{x}_i,\text{RED}$ 这 $3$ 个节点两两相连，因此 $x_i$ 和 $\mathrm{\neg }{x}_i$ 这两个节点只能其中一个着色为 $c(\text{TRUE})$，另一个为 $c(\text{FALSE})$。

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

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

e

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

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

$\begin{array}{|cccccccc|}\hline x& y& z& a& b& c& d& e\\ c\text{(TRUE)}& c\text{(FALSE)}& c\text{(FALSE)}& c\text{(FALSE)}& c\text{(RED)}& c\text{(TRUE)}& c\text{(FALSE)}& c\text{(RED)}\\ c\text{(TRUE)}& c\text{(FALSE)}& c\text{(FALSE)}& c\text{(FALSE)}& c\text{(TRUE)}& c\text{(RED)}& c\text{(FALSE)}& c\text{(RED)}\\ c\text{(FALSE)}& c\text{(TRUE)}& c\text{(FALSE)}& c\text{(RED)}& c\text{(FALSE)}& c\text{(TRUE)}& c\text{(FALSE)}& c\text{(RED)}\\ c\text{(FALSE)}& c\text{(TRUE)}& c\text{(FALSE)}& c\text{(TRUE)}& c\text{(FALSE)}& c\text{(RED)}& c\text{(FALSE)}& c\text{(RED)}\\ c\text{(TRUE)}& c\text{(TRUE)}& c\text{(FALSE)}& c\text{(RED)}& c\text{(FALSE)}& c\text{(TRUE)}& c\text{(FALSE)}& c\text{(RED)}\\ c\text{(TRUE)}& c\text{(TRUE)}& c\text{(FALSE)}& c\text{(FALSE)}& c\text{(RED)}& c\text{(TRUE)}& c\text{(FALSE)}& c\text{(RED)}\\ c\text{(FALSE)}& c\text{(FALSE)}& c\text{(TRUE)}& c\text{(RED)}& c\text{(TRUE)}& c\text{(FALSE)}& c\text{(RED)}& c\text{(FALSE)}\\ c\text{(FALSE)}& c\text{(FALSE)}& c\text{(TRUE)}& c\text{(TRUE)}& c\text{(RED)}& c\text{(FALSE)}& c\text{(RED)}& c\text{(FALSE)}\\ c\text{(TRUE)}& c\text{(FALSE)}& c\text{(TRUE)}& c\text{(RED)}& c\text{(TRUE)}& c\text{(FALSE)}& c\text{(RED)}& c\text{(FALSE)}\\ c\text{(TRUE)}& c\text{(FALSE)}& c\text{(TRUE)}& c\text{(FALSE)}& c\text{(RED)}& c\text{(TRUE)}& c\text{(RED)}& c\text{(FALSE)}\\ c\text{(TRUE)}& c\text{(FALSE)}& c\text{(TRUE)}& c\text{(FALSE)}& c\text{(RED)}& c\text{(TRUE)}& c\text{(FALSE)}& c\text{(RED)}\\ c\text{(TRUE)}& c\text{(FALSE)}& c\text{(TRUE)}& c\text{(FALSE)}& c\text{(TRUE)}& c\text{(RED)}& c\text{(FALSE)}& c\text{(RED)}\\ c\text{(FALSE)}& c\text{(TRUE)}& c\text{(TRUE)}& c\text{(TRUE)}& c\text{(RED)}& c\text{(FALSE)}& c\text{(RED)}& c\text{(FALSE)}\\ c\text{(FALSE)}& c\text{(TRUE)}& c\text{(TRUE)}& c\text{(RED)}& c\text{(FALSE)}& c\text{(TRUE)}& c\text{(RED)}& c\text{(FALSE)}\\ c\text{(FALSE)}& c\text{(TRUE)}& c\text{(TRUE)}& c\text{(RED)}& c\text{(FALSE)}& c\text{(TRUE)}& c\text{(FALSE)}& c\text{(RED)}\\ c\text{(FALSE)}& c\text{(TRUE)}& c\text{(TRUE)}& c\text{(TRUE)}& c\text{(FALSE)}& c\text{(RED)}& c\text{(FALSE)}& c\text{(RED)}\\ c\text{(TRUE)}& c\text{(TRUE)}& c\text{(TRUE)}& c\text{(RED)}& c\text{(FALSE)}& c\text{(TRUE)}& c\text{(RED)}& c\text{(FALSE)}\\ c\text{(TRUE)}& c\text{(TRUE)}& c\text{(TRUE)}& c\text{(FALSE)}& c\text{(RED)}& c\text{(TRUE)}& c\text{(RED)}& c\text{(FALSE)}\\ c\text{(TRUE)}& c\text{(TRUE)}& c\text{(TRUE)}& c\text{(RED)}& c\text{(FALSE)}& c\text{(TRUE)}& c\text{(FALSE)}& c\text{(RED)}\\ 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 问题中的任意一个实例 $⟨\varphi ⟩$，规约算法 $F$ 构造出如下一个 3-COLOR 问题的实例 $⟨G⟩$，使得 3-CNF 布尔公式 $\varphi$ 是可满足的，当且仅当图 $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 布尔公式 $\varphi$ 是可满足的，当且仅当图 $G$ 是 $3$ 着色的。

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

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

因此 $\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{array}{rl}\text{K-PROFIT-DEADLINES}=\{⟨A,k⟩:& 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 leastprofit }k\}\end{array}$$

b

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

接下来证明 K-PROFIT-DEADLINES 是 NP 困难的，考虑使用子集和问题问题进行规约，即证明 $\text{SUBSET-SUM}{\le }_P\text{K-PROFIT-DEADLINES}$。对于 SUBSET-SUM 问题中的任意一个实例 $⟨S,t⟩$，规约算法 $F$ 构造出如下一个 K-PROFIT-DEADLINES 问题的实例 $⟨A,k⟩$，使得 $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^{\prime }$，那么只需要按任意顺序执行 $S^{\prime }$ 在中 $A^{\prime }$ 对应的任务（$A-A^{\prime }$ 的任务按随意顺序执行，反正得不到利润），就可以得到恰好 $t$ 的利润，这个任务执行计划是满足要求的。

必要性：假设 $A$ 中的任务按某种顺序执行可以得到至少 $t$ 利润。由于 $A$ 中所有任务的截止时间都相等（均为 $t$），因此在 $t$ 时间前执行的任务并不需要固定的顺序。此外，由于每个任务单位时间内所获得的利润都是 $1$，因此在时间 $t$ 内，恰好只能获得利润 $t$。也就是说，存在一个 $A$ 子集 $A^{\prime }$，其利润之和恰好为 $t$。将集合 $A^{\prime }$ 中的任务映射回 $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]=\{\begin{array}{rlrl}& 0& & \text{if}i=0\\ & f[i-1,j]& & \text{if}i>0\wedge (j<t_i\vee j>d_i)\\ & max\{f[i-1,j-t_i]+p_i,f[i-1,j]\}& & \text{if}i>0\wedge (t_i\le j\wedge j\le d_i)\end{array}$

那么对于状态 $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' 给出。

//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)$。

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]