0

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

  • 让G对应的网络流G'
  • 让M我们perfect matching进入G
  • 让G<sub>M</sub>与residual graph此匹配相关联

来自 Jon Kleinberg 和 Eva Tardos 的算法设计7.13 第 406 页，

Theorem 7.62状态：

(7.62) 令 M 为完美匹配。如果 G M中存在负成本有向循环 C ，则 M 不是最小成本

这个定理是有道理的，但是，我对 abipartite flow network's residual graph的 aperfect matching如何实际上包含一个循环感到困惑。我可以看到一个循环的唯一方法是是否涉及sink或source。

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

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

4

1 回答 1

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，因此沿对角线的最大流量是最小成本最大流量。

于 2014-04-08T04:55:38.260 回答