algorithm - 完美匹配的二分流网络的残差图中怎么会存在有向环呢？

Question

我正在研究算法分析。我目前正在阅读 Network Flow算法。我正在考虑申请 Network Flow有关查找的算法 bipartite matchings成本最低。

• 让G与相应的网络流量 G'
• 让M成为perfect matching在G
• 让G<sub>M</sub>成为residual graph与此匹配关联

来自 Jon Kleinberg 和 Eva Tardos 的 Algorithm Design 7.13 第 406 页，

Theorem 7.62状态:

(7.62) Let M be a perfect matching. If there is a negative-cost directed cycle C in G_M, then M is not minimum cost

这个定理是有道理的，但是我很困惑 bipartite flow network's residual graph的 perfect matching实际上可以包含一个循环。我能看到一个循环的唯一方法是如果 sink或 source参与。

然而在一个perfect matching source将不包含离开它的边缘，并且 sink将不包含进入它的边缘。此外，内部节点中发生的循环似乎与 Bipartite graph 的定义相矛盾。 .

有人可以在残差图中提供这样一个循环的例子吗？

Answer 1

当然。考虑图中 a = 成本和 c = 容量:

  a=3,c=1
Ao----->oB
  \    ^
   \  /a=1,c=1
    \/
    /\
   /  \a=1,c=1
  /    v
Co----->oD
  a=3,c=1

所以显然有 2 个可能的最大流量。一个使用水平边缘，另一个使用对角线。

对于水平方向的流动，我们有一个残差图:

  a=-3,c=1
Ao<-----oB
  \    ^
   \  /a=1,c=1
    \/
    /\
   /  \a=1,c=1
  /    v
Co<-----oD
 a=-3,c=1

注意循环 B->A->D->C，容量为 1，成本为 -3 + 1 -3 + 1 = -4。

这个循环的直观解释是，沿着循环边缘的一个单位的流量每增加一次 - 或者相反，沿着相反方向的边缘的流量每减少一次 - 我们将减少总流量成本 4因为我们将用成本较低的对角线边缘的流量代替相对昂贵的水平边缘的流量。

在最小成本流的增广路径算法中，我们将继续沿着这个循环插入 1 个单位的流，并最终沿着对角线得到一个新的、更便宜的流。这将提供新的残差图:

  a=3,c=1
Ao----->oB
  ^    /
   \  /a=-1,c=1
    \/
    /\
   /  \a=-1,c=1
  v    \
Co----->oD
  a=3,c=1

现在循环是 A->B->C->D，成本为 3 - 1 + 3 - 1 = 4，因此沿对角线的最大流是最小成本最大流。