V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
olist
V2EX  ›  算法

最大流 push-relabel 算法相关的一个习题

  •  
  •   olist · 2021-06-24 19:13:46 +08:00 · 924 次点击
    这是一个创建于 1008 天前的主题,其中的信息可能已经有所发展或是发生改变。
    算法导论习题 26.5-5:Suppose that at some point in the execution of a push-relabel algorithm, there exists an integer 0<k<=|V|-1 for which no vertex has v.h=k. Show that all vertices with v.h>k are on the source side of a minimum cut.
    想了很久也没有证明出来。
    第 1 条附言  ·  2021-06-25 11:31:05 +08:00
    知道答案了,大致说下思路给以后可能需要的读者。
    首先可以根据 k 将所有的点分成左右两部分(左边点的高度大于 k ),同时得到一个割( cut ) c 。由于此时的残留网络( residual network )中只有从右到左的边,我们已经找到了一个预流( preflow ) pf,相应的有一个流( flow ) f,它们的在 c 上的净流量等于从左到右的总容量。据此,我们可以把左边的所有点合并成一个新的源点,新图的一个最大流也是原图的一个最大流,同时新图的任一个最小割也是原图的一个最小割,左边的所有的点在原图的最小割的左侧。
    目前尚无回复
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5386 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 31ms · UTC 08:37 · PVG 16:37 · LAX 01:37 · JFK 04:37
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.