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

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

  •  
  •   olist · 332 天前 · 512 次点击
    这是一个创建于 332 天前的主题,其中的信息可能已经有所发展或是发生改变。
    算法导论习题 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 条附言  ·  331 天前
    知道答案了,大致说下思路给以后可能需要的读者。
    首先可以根据 k 将所有的点分成左右两部分(左边点的高度大于 k ),同时得到一个割( cut ) c 。由于此时的残留网络( residual network )中只有从右到左的边,我们已经找到了一个预流( preflow ) pf,相应的有一个流( flow ) f,它们的在 c 上的净流量等于从左到右的总容量。据此,我们可以把左边的所有点合并成一个新的源点,新图的一个最大流也是原图的一个最大流,同时新图的任一个最小割也是原图的一个最小割,左边的所有的点在原图的最小割的左侧。
    目前尚无回复
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   1022 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 20:26 · PVG 04:26 · LAX 13:26 · JFK 16:26
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.