算法导论 25 Problems 答案

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

25-1

a

证明方式和题目 20-3-a 相似。

充分性：由于 G 有一条欧拉回路 C，因此在 C 中，当有一条入边进入节点 v，总有一条出边离开节点 v（重复经过节点 v 的无向边是不同的）。由于这些边恰好包含了 E 中所有的边各一次，只要 v 在 C 上出现了 kv 次，那么就有 kv 条不同的无向边进入 C，kv 条不同的无向边离开 v，那么 v 的度数为 2kv，即所有节点的度数都是偶数，原结论成立。

必要性：对于任意一条从 s 出发的一条路径 P，它必定能回到 s，使用反证法证明这个结论。如果从 s 出发存在一条路径它不能回到 s，也就是说，有一条路径 P′ 是 s−v1−v2−⋯−vk，并且 vk≠s，并且从 vk 之后所有已经没有出边可走。那么令 v=vk，统计路径 P′ 得到 v 的出现次数为 k，那么可以知道离开 v 的边数为 k−1（因为已经没有边走出来了），而进入 v 的边数为 k，那么节点 v 的度数为 2k−1，这和节点 v 是偶数的结论矛盾，因此 P 必定是一条回路。那么，接下来我们找出 G 的其中一条回路 C1，那么如果 C1 是一条欧拉回路，那么完成；否则，去除 C1 中的所有边，节点度数的性质仍然保持不变，由于 G 是连通图，那么可以找到另一条和 C1 点相交，边不相交的回路 C2，并且将交点一处整合成一条回路（如下图所示），直到所有的边都已经被使用。

如图所示，我们已经找到了两个环 C1:b−d−a−b 和 C2:b−e−c−b，那么我们可以整合成回路 C:b−d−a−b−c−e−b。

b

该算法 EULER-CYCLE' 和题目 20-3-b 所提出的类似，区别在于 EULER-CYCLE 在访问完一条边 (u,v) 后，需要在 v 的邻接表删除一个 u。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
EULER-CYCLE-UNDIRECTED-DFS(G, A, u)
  while G.Adj[u] != ∅
    select v from G.Adj[u] randomly and remove it from G.Adj[u]
    remove a u from G.Adj[v]
    dfs(v)
  INSERT(A, u)

EULER-CYCLE-UNDIRECTED(G)
  select s ∈ G.V randomly
  Let A be new array
  EULER-CYCLE-DFS(G, A, s)
  reverse A
  return A

c

对于一个 1- 正则图 G1=(V,E1)，由于每个节点的度数均为 1，因此仅有 1 个节点与它相邻。因此 G1 的节点个数必定为偶数，且 E1 是它的一个完美匹配。

对于一个 2k- 正则二分图 G2k=(V,E2k),V=L∪R，由于所有节点的度数都为偶数，因此 G2k 必定存在一条欧拉回路 C。并且 C 为 E 中的所有无向边都指定了一个方向，并且这条回路的节点是 L,R 相间的。不失一般性，我们去掉所有从 R 到 L 定向的所有边，那么每个节点的度数只剩下原来的一半，即 2k−1，剩下的图是一个 2k−1- 正则图，那么继续递归进行操作，直到这个图是一个 1- 正则图，那么我们就得到了 G2k 的一个完美匹配。如果我们去掉的是从 L 到 R 定向的所有边，那么接下来得到的完美匹配和前面得到的完美匹配是不相交的。

最终，整个问题相当于使用了一次分治算法。具体过程由 GEN-DISJOINT-PERFECT-MATCHING 给出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
GEN-DISJOINT-PERFECT-MATCHING-AUX(G, A)
  if |G.E| * 2 == |G.V|
    INSERT(A, G.E)
  else
    E1 = Ø
    E2 = Ø
    P = EULER-CYCLE-UNDIRECTED(G)
    for i = 2 to P.size
      if i % 2 == 0
        E1 = E1 ∪ {P[i - 1], P[i]}
      else
        E2 = E2 ∪ {P[i - 1], P[i]}
    GEN-DISJOINT-PERFECT-MATCHING-AUX((G.V, E1), A)
    GEN-DISJOINT-PERFECT-MATCHING-AUX((G.V, E2), A)
GEN-DISJOINT-PERFECT-MATCHING(G)
  Let A be a new array
  GEN-DISJOINT-PERFECT-MATCHING-AUX(G, A)

接下来考虑程序 GEN-DISJOINT-PERFECT-MATCHING-AUX 的时间复杂度。每次调用 GEN-DISJOINT-PERFECT-MATCHING-AUX 时，首先都会对 G 中的所有边进行 O(1) 时间的处理，接下来将这些边进行均匀地分成两部分进行递归处理。由于这个程序最多递归 lg⁡d 层，因此整个程序的时间复杂度为 O(Elg⁡d)。

25-2

a

FIND-AUGMENTING-PATH 的第 10 行代码可以改等价地改为 δ=min{r.σ:r∈R−FR}，它将可以遍历所有 R−FR 中的节点进行求出，因此时间复杂度为 O(n)。

b

在第 11-14 行结束后，FL 中每个 l 节点的属性 h 都减少了 δ，而对于 r∈R−Fr，属性 h 的值未曾改变。按照 σ 参数的定义：r.σ=min{l.h+r.h−w(l,r):l∈FL} 可以得知，r.δ 减少了 δ。因此只需要插入如下两行代码就可以以 O(n) 的时间完成对 R−FR 所有节点 δ 属性的更新。

1
2
for each vertex r ∈ R - FR
  r.δ = r.δ - δ

c

只需要在每次对集合 FL 更新时，对 R−FR 中的所有节点的 δ 属性进行进行更新即可，一次刷新只需要 O(n) 的时间。由于 FIND-AUGMENTING-PATH 的增长步数最多只有 n 次，因此这个步骤在一次调用 FIND-AUGMENTING-PATH 中，所需要花费的时间为 n⋅O(n)=O(n2)。

也就是说，只需要在第 26 行的下面插入如下两行代码即可。

1
2
for each vertex r ∈ R - FR
  r.δ = min{r.δ, v.h + r.h - w(v, r)}

d

经过修改后，以及题目 25.3-5 的修改，得到新版的寻找増广路径算法为 FIND-AUGMENTING-PATH''' 如下。

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
FIND-AUGMENTING-PATH'''(w, n, h, match)
  Q = Ø
  FL = Ø
  FR = Ø
  for each unmatched vertex l ∈ L
    l.π = NIL
    ENQUEUE(Q, l)
    FL = FL ∪ {l}
  for each vertex r in R
    r.δ = min{h[l] + h[r] − w(l, r) : l ∈ FL}
  repeat
    if Q is empty
      δ = min { h[l] + h[r] − w(l, r) : l ∈ FL and r ∈ R − FR }
      for each vertex l ∈ FL
        h[l] = h[l] − δ
      for each vertex r ∈ FR
        h[r] = h[r] + δ
      for each vertex r ∈ R - FR
        r.δ = r.δ - δ
        if r.δ == 0
          for each l ∈ FL
            if h[l] + h[r] == w(l, r)
              r.π = l
              break
          if match[r] == 0
            // 代表r仍然未被匹配
            an M-augmenting path has been found (exit the repeat loop)
          else 
            ENQUEUE(Q, r)
            FR = FR ∪ {r}
    u = DEQUEUE(Q)
    if 1 <= u <= n
      // 这时u是左部节点
      for r = n + 1 to n + n
        if h[u] + h[r] == w(u, r) and r ∉ FR 
          r.π = u
          if match[r] == 0
            an M-augmenting path has been found (exit the repeat loop)
          else
            ENQUEUE(Q, r)
            FR = FR ∪ {r}
    else
      // 这时u是右部节点
      l = match[u]
      l.π = u
      FL = FL ∪ {l}
      ENQUEUE(Q, l)
      for each vertex r ∈ R - FR
        r.δ = min{r.δ, l[h] + r[h] - w(v, r)}
  until an M-augmenting path has been found
  using the predecessor attributes π, construct an M-augmenting path P by tracing back from the unmatched vertex in R
  return P

在程序 FIND-AUGMENTING-PATH''' 的 repeat ... until 循环中，所有的 for 循环都是线性的。中间那个用于更新 R−FR 中每个节点的 δ 属性的 for 循环中，内部的 for 循环每个节点 r 节点最多只能进入一次，然后要么找到了增广路径，repeat ... until 跳出，要么被添加进集合 FR 中，之后再也不会进入。除此之外，repeat ... until 循环体内的其它所有 for 循环都是单层的。因此一次 repeat ... until 循环的时间复杂度为 O(n)，调用一次 FIND-AUGMENTING-PATH''' 所需要花费的时间为 O(n2)。

由于匈牙利算法至多需要寻找 n 次增广路径，因此优化后的匈牙利算法的时间复杂度为 n⋅O(n2)=O(n3)。

25-3

a

对于原二分图 G=(V,E),V=L∪R，可以构造完全二分图 G′=(V,E′)，即对于 ∀l∈L,r∈R，都有 (l,r)∈E′。对于 ∀(l,r)∈E，有 w′(l,r)=w(l,r)，对于 ∀(l,r)∈E′−E，有 w′(l,r)=−∞。使用图 G′ 运行匈牙利算法的结果即为所求。

b

与题目 25-3-a 建立的图 G′ 一致。令 δ=min{x(l,r)∣(l,r)∈E}。对于 ∀(l,r)∈E，有 w′(l,r)=w(l,r)+δ+1，对于 ∀(l,r)∈E′−E，有 w′(l,r)=−∞。由于 G 必定包含一个完美匹配，因此使用图 G′ 运行匈牙利算法的结果即为所求。

c

考虑将图 G=(V,E) 中的每个节点 v 拆分成两个节点 vin,vout。通过图 G，构造二分图 G′=(V′,E′),V′=L∪R，其中 L={vout∣v∈V},R={vin∣v∈V}。对于 ∀(u,v)∈E，都有 (uout,vin)∈E′，并且 w′(uout,vin)=w(u,v)。使用题目 25-3-b 的构造方法，对图 G′ 求出的一个最大二分匹配 M′，所在 E 对应的边集 M 即为所求。因为在 M′ 中，G′ 的所有节点都出现了一次。也就是说，在图 G 中，求出来的 M 都代表了每个节点的一条出边和入边，这意味着这些节点只在一个环中。

25-4

a

M∗ 是最大匹配的一个最优解，并且假设任意匹配的空间为 S，那么有 M∗∈S。对于分数匹配，假设任意匹配的空间为 S′，对于所有的边，都有 x(l,r)∈[0,1] 而非 {0,1}，因此 S⊆S′，即最大匹配的所有解也是最大分数匹配的解。由于 M∗ 是最大匹配，因此 ∀M∈S,|M|≤|M∗| 均成立，即 M∗ 是 S 中的一个全局最优解，但是 M∗ 在 S′ 中只是一个局部最优解，那么存在一个全局最优解 x∗∈S′ 使得 |x∗|≥|M∗|，原结论成立。

b

考虑 G=(V,E) 中的其中一个分数匹配 x。那么考虑将 x 转换成一个不会更劣的整数匹配 x′。

首先考虑边集 H={(u,v)∈E,0<x(u,v)<1}。如果 H 为空，那么整个过程完成。如果 H 为空，那么整个过程结束。如果 H 包含一个环 C，那么由于 G 是一个二分图，因此 C 必定是个偶环。为这个环 C 中的所有边进行定向得到有向环 C′，那么 C′ 中必定有 |C|/2 条边是从 L 指向 R 的，有 |C|/2 条边是从 R 指向 L 的。令 EL={(l,r)∣(l,r)∈C′,l∈L,r∈R},ER=C′−EL

不失一般性，考虑消去一条 ER 中的边。令 δ=min{x(l,r)∣(l,r)∈ER}。那么构造新的分数匹配 x′：

x′(l,r)={x(l,r)+δif(l,r)∈ELx(l,r)−δif(l,r)∈ERx(l,r)if(l,r)∈E−C

那么在下一轮迭代中，由 x′ 所诱导出来的边集 H′ 至少比原来少一条边。最终直到 H′ 没有环为止。

现在，假设由 x 诱导出来的边集 H 是没有环的。令 P 是 H 中的其中一条最长路，令 sP,tP 表示 P 的起点和终点，那么 sP 和 tP 除了 H 中的边，其他与 sP 或 tP 相邻的边的分数值 x 为 0，因为如果为 1，那么 sP 或 tP 的分数之和大于 1，这是不可能的；如果位于区间 (0,1)，那么与 sP,tP 相邻的这些边也会在 H 中，这不是一条最长路。

那么接下来，每次找到一条关于边集 H 中长度为 2 的路径，并且这条路径中某个节点在 H 中出现 1 次。不失一般性，假设这条路径为 a−b−c，并且 a 在 H 中只出现一次。那么考虑去掉边 (b,c)，令 x′(a,b)=x(a,b)+x(b,c),x′(b,c)=0（注意此处的 a 边权之和仍然不会超出 1，因为 b 的边权和不变）。最终得到的新匹配 x′ 所诱导的边集 H′ 也会少一条边，最终直到 H 不存在长度为 2 以上的路径。

最终，对于 ∀(u,v):x(u,v)>0，由于 H 中不存在长度至少为 2 的路径，因此只需要令 x′(u,v)=1。那么得到 x′(u,v)≥x(u,v)。最终得到了一个比分数匹配可能更优的整数匹配，原结论成立。

大致的过程由 GEN-INTEGER-MATCHING 给出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
GEN-INTEGER-MATCHING(G, x)
  while the edge set H = {(u, v) |(u, v) ∈ G.E, 0 < x(u, v) < 1} still contain a cycle C
    generate the directed cycle C' from C
    EL = {(l, r) ∣ (l, r) ∈ C', l ∈ L, r ∈ R}
    ER = H - EL
    δ = min{x(l, r) ∣ (l, r) ∈ ER}
    for each edge (u, v) in EL
      x(u, v) = x(u, v) + δ
    for each edge (u, v) in ER
      x(u, v) = x(u, v) - δ
  while the longest path length of (V, H) exceeds 2
    let a - b - c be a path of length of 2 s.t. a incident only once in H
    x(a, b) = x(a, b) + x(b, c)
    x(b, c) = 0
  E = Ø
  for each edge (u, v) in G.E
    if x(u, v) > 0
      E = E ∪ {(u, v)}
  return E

c

与题目 25-4-b 类似，改动的地方在于：

  1. 当考虑是让 EL 和 ER 中的边消去一条时，不是再随便消去，而是计算 sL=∑(u,v)∈ELx(u,v) 和 sR=∑(u,v)∈ERx(u,v) 的值，如果 sL>sR，那么选择消去 ER 的边，否则选择消去 EL 中的边。这将会使得分数匹配的解更优。
  2. 去除长度至少为 2 的路径时，不能再使用以上的方法，因为有可能 w(b,c)>w(a,b)，使得解的最优性降低。做法是：在 H 中选择一条长度至少 2 的路径 P，并且 P 两端的节点在 H 中只出现一次。可见，P 是一条在点集 L,R 交替的路径，为 P 进行定向得到 P′。令 FL={(l,r)∣(l,r)∈P′,l∈L,r∈R},FR=P−FL，考虑从 FL 或者 FR 消去一条边，计算 tL=∑(u,v)∈FLx(u,v) 和 tR=∑(u,v)∈FRx(u,v) 的值，如果 tL>tR，那么选择消去 ER 的边，否则选择消去 EL 中的边，这个过程和为消去环的过程相同。

其他过程和 25-4-b 一致，这说明可以将一个带权分数最大匹配转化成一个更优的带权整数最大匹配，使得原结论成立。大致的过程由 GEN-INTEGER-MATCHING-WEIGHTED 给出。

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
UPDATE-X-FRACTIONAL-MATCHING(C, x, w)
  generate the directed edges set C' from C s.t. all of the edges in the same direction
  EL = {(l, r) ∣ (l, r) ∈ C', l ∈ L, r ∈ R}
  ER = H - EL
  SL = 0
  SR = 0
  for each edge (u, v) in EL
    SL = SL + w(u, v)
  for each edge (u, v) in ER
    SR = SR + w(u, v)
  if SL > SR
    δ = min{x(l, r) ∣ (l, r) ∈ ER}
    for each edge (u, v) in EL
      x(u, v) = x(u, v) + δ
    for each edge (u, v) in ER
      x(u, v) = x(u, v) - δ
  else
    δ = min{x(l, r) ∣ (l, r) ∈ EL}
    for each edge (u, v) in ER
      x(u, v) = x(u, v) + δ
    for each edge (u, v) in EL
      x(u, v) = x(u, v) - δ
  
GEN-INTEGER-MATCHING(G, x, w)
  while the edge set H = {(u, v) |(u, v) ∈ G.E, 0 < x(u, v) < 1} still contain a cycle C
    UPDATE-X-FRACTIONAL-MATCHING(C, x, w)
  while the longest path P length of (V, H) exceeds 2
    UPDATE-X-FRACTIONAL-MATCHING(P, x, w)
  E = Ø
  for each edge (u, v) in G.E
    if x(u, v) > 0
      E = E ∪ {(u, v)}
  return E

d

令图 G=(V,E),V={a,b,c},E={(a,b),(b,c),(a,c)}。

那么，图 G 的最大整数匹配 |M∗| 为 1，为其中一条边。但图 G 的最大分数匹配 |x∗| 为 1.5，其中 x∗(a,b)=x∗(b,c)=x∗(a,c)=0.5。

25-5

令图 G=(V,E) 为题目中所给定二分图，V=L∪R。本题将考虑使用差分约束来求解。那么对于 ∀l∈L，有 l.d=l.h，并且 ∀r∈R，有 r.d=−r.h。那么给定匹配 M，问题转化为求解所有节点的 d 属性，使得：

  • ∀l∈L,r∈R,l.d−r.d≥w(l,r) 都成立。
  • ∀(l,r)∈M∗,l.d−r.d=w(l,r) 都成立。

考虑构造如下约束图 G′=(V′,E′)。其中 V′=V∪{v0}。那么考虑将如下三种边加入 E′ 中：

  • ∀v∈V,(v0,v)∈E，都有 w′(v0,v)=0。
  • ∀(l,r)∈M∗，都有 (l,r)∈E′,w′(l,r)=−w(l,r),(r,l)∈E′,w′(r,l)=w(l,r)。
  • ∀(l,r)∈E−M∗。都有 (l,r)∈E′,w′(l,r)=−w(l,r)。

对约束图 G′ 以 v0 为起点调用 BELL-MANFORD 算法后，计算出了每个节点的 d 属性，那么根据 d 属性可以计算出 h 属性，最终 h 属性为所求。整个算法的时间复杂度为 O(|V|3)。