[关闭]
@zqbinggong 2018-03-24T05:20:53.000000Z 字数 2380 阅读 522

chap26 最大流

流网络 Ford-Fulkerson方法 最大二分匹配 算法导论

内容


流网络

  1. 流网络:

    • , directed.
    • Each edge ; has a capacity
    • If, then
    • If , then reverse edge . (Can work around this restriction.
    • Source vertex , sink vertex , assume for all , so that each vertex lies on a path from source to sink and
  2. 流:
    此处输入图片的描述

    此处输入图片的描述

  3. 可以通过增加中间结点的方式将不能有反平行边的限制去除,
  4. 对于具有对个源结点和汇点的情况,可以加入一个超级源结点和超级汇点来转化成单个源结点和汇点的问题,这两个加入的点的容量都是无穷大

Ford-Fulkerson方法

  1. Ford-Fulkerson方法依赖于残存网络、增广路径和切割这三个重要思想,其正确性由最大流最小切割定理保证
  2. 残存网络: 可以看成是去除了反向边限制的流网络,由流网络和流生成

    • 残存容量:
    • 残存网络的流,定义:,可以证明是原流网络的一个流,其值为
  3. 增广路径:增广路径是残存网络中一条从源结点到汇点简单路径

    • p的残存容量:
    • 残存网络的一个流定义为:
    • 的一个流
  4. 流网络的切割:切割,

    • 净流量:
    • 容量:
    • 由于流量守恒,必然导致:1.所有切割的净流量都等于;2.最大流的值不会超过最小切割的容量
  5. 最大流最小切割定理:以下条件等价:

    • 1.的一个最大流
    • 2.残存网络不包括任何增广路径
    • 3.,其中是流网络的某个切割

基本的Ford-Fulkerson算法

ford-fulkerson(G,s,t)

for each edge(u,v) in G.E
    (u,v).f = 0
while there exists a path p from s to t in the residual network G_f
    c_f(p) = min{...}
    for each edge(u,v) in p
        if (u,v) in E
            (u,v).f += c_f(p)
        else
            (v,u).f -= c_f(p)
  1. 假定所选择的任意增广路径和所有的容量都是整数,如果容量为有理数,可以乘上某个系数转化成整数
  2. 若f是某个最大流,则while循环最多|f|次(对应每次流只增加1)
  3. 用有向图来表示残差网络,使用广度或者深度有限搜索,在此图中找到一条增广路径的时间是,(注意到),因而总时间为,适用于流较小的情况

Edmonds-Karp算法

  1. 对增广路径的选择不再任意,而是选择一条从源结点s到汇点t的最短路径,这可以通过广度优先搜索来实现
  2. 时间为
  3. ,其中找最短路径,流递增操作共执行

最大二分匹配

  1. 匹配: 给定一个无向图,一个匹配是边的一个子集,使得对于所有的结点,子集中最多有一条边与之相连。
  2. 最大匹配即含有最多边的匹配
  3. 二分图: 即结点集合可以划分成,其中L和R不相交,并且边集合中所有边都横跨L和R。进一步假定集合中的每个结点都至少有一条边(方便转化成最大流问题)
  4. 实际应用,将L看成是机器集合,R是任务集合,E中有边(u,v)则表示机器u能够处理任务v。最大匹配能够让尽可能多的机器运转起来
  5. 寻找最大二分匹配的做法就是将二分图转化成流网络,具体做法就是将L看成源结点集合,R看成是汇点集合,因而首先加上一个超级源结点s和超级汇点t以及这两者对应的边,原图中所有无向边的方向都定义成从L指向R,最后给流网络中所有边都赋予单位容量
  6. 引理26.9:给定二分图和对应的流网络,若中存在一个匹配,则中存在一个整数值的流使得,反之亦成立。并且满足的边都是M中的边
  7. 完整性定理26.10: 如果容量函数c只能去整数值,则Ford-Fulkerson方法所生成的最大流f满足|f|是整数值的性质,而且对于所有的结点u和v,f(u,v)的值都是整数
  8. 推论26.11 二分图G中的一个最大匹配的基数等于其对应的流网络中某一最大流f的值
  9. 总结就是,两者完全等价:,并且

习题

to be continued


代码实现

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注