算法导论34.2 Exercises 答案

发表于 分类于 阅读次数： 本文字数： 4.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\)个节点对串接起来，从而得到图\(T_3\)中一条长度为\(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})\)去除，并加入边\((u_i,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\)的一条哈密顿回路，原结论成立。