算法导论34 Problems 答案

发表于 2023-07-25 更新于 2025-12-23 分类于算法导论阅读次数：本文字数： 13k 阅读时长 ≈ 12 分钟

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$的独立集，如果仍然有，说明这个顶点不是必要的，可以删除。否则必须保留下来。

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’$，在图$G=(V,E)$中，将$V’$和$V’$关联的所有边删去后，剩下的图不会含有任何一条边，因此$V-V’$是$G$的一个独立集。因此对于$G$的一个最小点覆盖$V_0$，那么得知$V-V_0$就是图$G$的一个最大独立集。

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

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

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

求出$G$的最大匹配。
再次从$L$中所有节点非匹配节点出发，寻找一条增广路径（且一定寻找失败）。
取$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$中节点所对应的匹配边，是指增广路径算法中有访问的边。接下来验证这个点覆盖确实覆盖了所有边：

左部节点$l\in L$是非匹配点，右部节点$r\in R$也是非匹配点。这种边是不可能存在的，因为这是一条增广路径。
$l$是匹配点，$r$也是匹配点。这种边被覆盖了，因为每条匹配边的其中一个节点都在$V_0$中。
$l$是匹配点，$r$是非匹配点。这说明$l$没有被访问到，否则找到了通向$r$的增广路径，因此这条边是被$L_0$中的节点覆盖。
$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=\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给出：

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

可见，这个算法是多项式的，接下来说明这个算法能够正确地运行。假设现在遍历到$xi$，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)$。

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

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

令状态$fi,j$表示时间$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(jd_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'给出。

//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]