算法导论34.2 Exercises 答案

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

34.2-1

对于图$G_1=(V_1,E_1),G_2=(V_2,E_2)$是否是同构的这个判断性问题，其证据是存在一个函数$f:V_1\rightarrow V_2$，并且$\forall (u,v)\in E_1$当且仅当$(f(u),f(v))\in E_2$。

为了方便，验证该语言的算法由GRAPH-ISOMORPHISM-VERIFY给出，并且这个算法以非编码的形式表示。

1
2
3
4
5
6
7
8
9
10
11
12
GRAPH-ISOMORPHISM-VERIFY(G1, G2, f)
  E1 = G1.E
  E2 = G2.E
  for each edge (u, v) in E1
    if (u, v) in E2
      remove edge (u, v) in E2
    else
      return 0
  if E2 == ∅
    return 1
  else
    return 0

可见，如果将$E_2$视为一个哈希表，那么GRAPH-ISOMORPHISM-VERIFY能够以$O(E_2)$的时间复杂度完成。因此它是一个多项式可验证的算法，因此GRAPH-ISOMORPHISM属于$\text{NP}$。

34.2-2

如果图$G=(V,E)$是一个哈密顿图，那么$G$必定存在一个经过所有顶点的环$C$，其长度为$|V|$。如果$|V|$是奇数，那么这意味着$C$是一个奇环，这个环不可能出现在一个二分图中。因此，任何带有奇数个顶点的二分图都是非哈密顿图。

34.2-3

将HAM-CYCLE作为子程序，我们可以构造出一个算法GEN-HAM-CYCLE来列出一条哈密顿回路的边的集合。

1
2
3
4
5
6
7
8
9
10
11
GEN-HAM-CYCLE(G)
  EC = ∅
  E = G.E
  V = G.V
  while E != ∅
    select (u, v) from E randomly
    E = E - {(u, v)}
    if HAM-CYCLE((V, E ∪ EC)) == 0
      EC = EC ∪ {(u, v)}
  parse EC into a path P
  return P

这个算法的基本思想是，遍历$E$中的每一条边$(u,v)$，并尝试删去，如果删去边$(u,v)$后的图仍然是一个哈密顿图，那么就真实地删去它；否则保留下来，它将是某条哈密顿回路中的关键的一条边。

因此如果HAM-CYCLE属于$P$，意味着HAM-CYCLE的时间复杂度为$O(V^k)$，其中$k$是一个正常数。在GEN-HAM-CYCLE中，它对HAM-CYCLE最多进行了$|E|=O(V^2)$次的调用，因此GEN-HAM-CYCLE的时间复杂度为$O(V^k)\cdot O(V^2)=O(V^{k+2})$，即列出一条哈密顿回路中的所有顶点是多项式可解的。

34.2-4

假设现在存在两个程序$B_1,B_2$可以分别在多项式时间$O(n^{k_1}),O(n^{k_2})$内分别能够检测$y$是否为$x$属于$L_1,L_2$的证据。那么可以构造出如下程序用于语言$L_1\cup L_2,L_1\cap L_2,L_1L_2,\overline{L_1},L_1^{\ast}$：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 假设字符串的下标从1开始。
B-UNION(B1, B2, x, y)
  if B1(x, y) == 1 or B2(x, y) == 1
    return 1
  else
    return 0
  
B-INTERSECTION(B1, B2, x, y)
  if B1(x, y) == 1 and B2(x, y) == 1
    return 1
  else
    return 0

B-CONCATENATION(B1, B2, x, y)
  // 考虑其中有一个为ε空字符串的情况。
  if (B1(x, y) == 1 and B2(ε, y) == 1) or (B1(ε, y) == 1 and B2(x, y) == 1)
    return 1
  n = x.size()
  for i = 1 to n - 1
    if B1(x[1 : i], y) == 1 and B2(x[i + 1 : n], y) == 1
      return 1
  return 0

B-KLEENE-STAR(B1, x, y)
  n = x.size()
  let f[0 : n] be a new array by 0
  f[0] = 1
  for i = 1 to n
    for j = 1 to i
      if f[j - 1] == 1 and B1(x[j : i], 1) == 1
        f[i] = 1
        break
  return f[n]

算法B-UNION和B-INTERSECTION分别调用了$1$次$B_1$和$B_2$，因此其时间复杂度均为$O(n^{\max(k_1,k_2)})$。算法B-CONCATENATION对$B_1,B_2$分别至多调用了$(n+1)$次，并且最大的规模为$n$，因此其时间复杂度为$(n+1)\cdot(O(n^{k_1})+O(n^{k_2}))=O(n^{\max(k_1,k_2)+1})$。B-KLEENE-STAR算法对$B_1$进行了$\dfrac{n(n+1)}{2}$次调用，最大的一次规模为$n$，因此其时间复杂度为$\dfrac{n(n+1)}{2}\cdot O(n^{k_1})=O(n^{k_1+2})$。综上所述，B-UNION, B-INTERSECTION, B-CONCBTENBTION, B-KLEENE-STAR可以在多项式时间内对各自的语言完成判定，因此语言$L_1\cup L_2,L_1\cap L_2,L_1L_2,L_1^{\ast}\in \text{NP}$。

然而，对于一个输入$x$和其证据$y$，如果$A_1(x,y)=0$，那么这并不意味着$x\in \overline{L_1}$，这仅仅说明这并不能证明$x\in L_1$（也就是说，可能还会有其它证据$y’$说明$x\in L_1$）。

34.2-5

考虑现在存在某个算法$A$判断字符串$x$是否在某个语言$L$中，其中$L\in\text{NP}$。

由于$L\in \text{NP}$，因此存在一个时间复杂度为$O(n^k)$的检验算法$B$，用于检验$y$是否为$x$属于$L$的证据。这意味着，算法$B$至多只能查看$O(n^k)$比特，因此$y$的长度至多为$O(n^k)$。

那么算法$A$最多只能枚举$2^{O(n^k)}$个字符串进行检验，每次检验所需要花费的时间为$O(n^k)$，因此算法$A$的运行时间为$O(n^k)\cdot2^{O(n^k)}=2^{O(n^k)}$。

34.2-6

给定一个图$G=(V,E)$和一条路径$P$，判断其是否为哈密顿通路是很简单的：只需要判断$V$中的节点是否在$P$中都出现且仅出现一次，并且相邻的两个节点的边都在$E$中即可，花费的时间为$O(V)$。也就是说，这是一个多项式时间内能够检验路径$P$是否为哈密顿通路的算法。因此，HAM-PATH属于$\text{NP}$。

34.2-7

当一个有向无环图包含一条哈密顿通路，图$G$有且仅有一个拓扑序列。因此只需要对图$G$进行拓扑排序，并将这个拓扑序列视为是一条路径$P$，然后判断路径$P$是否为哈密顿通路即可。程序HAM-PATH-DAG给出了大致过程：

1
2
3
4
5
6
HAM-PATH-DAG(G)
  topologically sort the vertices of G and get the topologically sorted order P
  if P is a hamiltonian path of G
    return 1
  else
    return 0

整个过程主要在于对图$G$进行拓扑排序，因此整个算法的时间复杂度为$O(V+E)$，它是多项式时间算法。

34.2-8

令语言$\overline{L}$表示除了重言式以外，其它所有公式所组成的语言。

考虑$\overline{L}$的检验问题：给定一个布尔公式$x$和一组输入变量$y$，如果布尔公式的值为$0$，那么输出$1$，否则输出$0$。

可见，只要给定了这个一个布尔公式和其输入，那么这个布尔公式的值可以以线性（即多项式时间）内计算出来。因此，$\overline{L}\in \text{NP}$。

最终得到语言TAUTOLOGY属于$\text{co-NP}$。

34.2-9

对于任意$L\in P$，按照题目34.1-6的结论，都有$\overline{L}\in P$。由于$P\subseteq \text{NP}$，因此$\overline{L}\in \text{NP}$，最终得到$L\in\text{co-NP}$。

34.2-10

由于$\text{NP}\neq \text{no-NP}$，因此存在语言$L\in \text{NP}-\text{co-NP}$，因此有$L\not\in \text{NP}-\text{co-NP}$。按照题目34.2-9的结论，以及$P\in\text{NP}$，因此有$P\subseteq \text{NP}\cap\text{co-NP}$。也就是说$L\not\in P$。因此$P\neq \text{NP}$。

34.2-11

首先考虑树版本下的这个问题，并使用归纳法进行证明。

假设当前的一棵树为$T=(V,E)$，那么为这棵树每对距离至多为$3$的节点对相连后，得到的图为$T_3=(V,E_3)$。

对于一棵$3$个节点的树，原结论明显成立，因为此时$T_3$是$3$个节点的完全图，因此存在了一条哈密顿回路，原结论成立。

接下来考虑一棵$n(n>3)$个节点的树$T=(V,E)$。假设对于$k=3,4,\dots,n-1$，所有$k$个节点的树中，每对距离至多为$3$的节点对相连后所得到的图，都存在一条哈密顿回路。考虑将$T$中的某个内部节点$w$删去，那么$T$将形成$k(k>1)$个连通块。考虑对第$i$个连通块$T^{(i)}$构造一个点二元组$(u_i,v_i)$：

  • 如果$T^{(i)}$只有$1$个节点$w_i$，那么令$u_i=v_i=w_i$。
  • 如果$T^{(i)}$有$2$个节点，考虑$T$中$T^{(i)}$和$w$相连的那个节点为$w_i$，令$u_i=w_i,v_i$为另一个节点。
  • 如果$T^{(i)}$有超过$3$个节点，考虑$T$中$T^{(i)}$和$w$相连的那个节点为$w_i$，令$u_i=w_i$。根据假设，$T_3^{(i)}$必定存在一个哈密顿回路$C^{(i)}$，那么令$v_i$为$w_i$在$C^{(i)}$中其中一个相邻的节点。

那么接下来可以将这$k$个节点对串接起来，从而得到图$T3$中一条长度为$n-1$的简单回路$C$（也就是说，$w$不在里面）。构造方式如下：对于$\forall i\in[1,k]$，如果第$i$个连通块具有超过$3$个节点，那么将$T_3^{(i)}$中指定的哈密顿回路断开边$(u_i,v_i)$，从而得到一条起点为$u_i$，终点为$v_i$的哈密顿通路$P_i$，并且有$P_i\subset C$。接下来对$\forall i\in[1,k-1]$，有$(v{i},u{i+1})\in P_i$，同时让$(v_k,u_1)\in C$（这是因为$\delta(u_i,w)=1,\delta(v_i,w)\le 2$，因此$(v_i,u{i+1}),(v_k,u_1)\in E_3$）。

由此那么我们成功构造出了长度为$n-1$的一条简单回路$C$。需要注意的是，由于剩下的节点数至少为$3$，因此$C$必定不包含重边。

接下来将$w$加入$C$中，最终构造出一条哈密顿回路。方式如下：选择一条边$(v{i},u{i+1})$去除，并加入边$(ui,w),(v{i+1},w)$即可得到$C’$，此时$C’$为$T$的一条哈密顿回路，原结论成立。

因此，树版本下的这道题目得到解决。接下来一般连通图下的版本：对于一般的连通图$G=(V,E’)$，总存在一棵生成树$T=(V,E)$，使得$E\subseteq E’$。也就是说，对于图$G_3=(V,E_3’)$，也有$E_3\subseteq E_3’$。按照上面的结论，构造出的环$C’$是$T_3=(V,E_3)$的一条哈密顿路，因此$C’$也是$G_3$的一条哈密顿回路，原结论成立。