《Python Algorithm》10.匹配，割，流

这是一篇关于.匹配，割，流的思维导图 .如果残留网络上找不到增广路径,则当前流为最大 流;反之,如果当前流不为最大流,则一定有增广路径。

《Python Algorithm》10.匹配，割，流

• 引言
  • 本章给出一些单独的算法用于许多变种和应用
  • 核心问题
    • 找到网络中的最大流
  • 解决策略
    • Ford和Fulkerson的增广路径方法
  • 两个基础问题
    • 二部图匹配
    • 不相交路径
• 二部图匹配
  • 二部图
    • 无向图的结点可以分为两个子集V1、V2
    • 交集为空，并集为全集
    • 图中任意边的两个端点，分别属于V1和V2
  • 二部图匹配
    • 匹配
      • 图的一个边的集合中任意两边不相邻
    • 极大匹配
      • 一个匹配中添加任意其他边不再是匹配
    • 最大匹配
      • 边数最多的匹配
  • 例
    • Ch4：电影与座位问题
    • Ch7：稳定婚姻问题
    • 指派问题
  • 迭代改进
  • 策略
    • 类似Ch7的Gale-Shapley算法
      • 女性可以反悔
      • 本章关键
    • 过程
      • 找到一个没结婚的男人
        • 如果没有，则结束
      • 找到一些订婚和取消的交错序列，以便以订婚结束
      • 如果找到，则有比取消多一个的订婚
  • 增广路径
    • 定义
      • P是图G中一条连通两个未匹配顶点的路径
      • 已匹配（属于M）和待匹配（不属于M）的边在P中交替出现
    • 结论
      • P的路径长度必为奇数，且第一条边和最后一条边不属于M
      • 不断寻找增广路径可以得到一个更大的匹配M'，直到找不到更多的增广路径
      • M为G的最大匹配当且仅当不存在M的增广路径
      • 最大匹配书M+最大独立数N=总的结点数
  • 代码实现
    • 使用增广路径找到一个最大二部图匹配
    • O(nm)
• 不相交路径
  • 匹配的应用
    • 计数不相交边的路径
  • 不相交路径可以共享结点，但不能共享边
    • 不再限制是二部图
    • 当允许通用的有向图时，可以自由的指派路径起点和终点
  • 最简单和最通用的解决方案
    • 指派两个特殊的点
      • s：源点
      • t：汇点
    • 称为s-t图或s-t网络
    • 应用
      • 网络中的边连通性
      • 找到多核CPU的通讯路径
  • 规则
    • 除s和t外，进入某结点的路径数等于出结点的路径数
    • 至多一个路径可以通过任意给定边
  • 代码实现
    • 使用标记法遍历寻找增广路径计数边不相交路径
  • 证明
    • 我们能发现k个不相交路径，并有一个大小为k的边分离器
    • 我们可以发现不相交路径的最大数
    • 没有增广路径
  • 门格尔理论
• 最大流
  • 本章核心
    • 生成
      • 二部图匹配
      • 不相交路径
    • 最小割问题的镜像
  • 概念
    • 容量
      • 每个边的任意值的正数权值
      • 边的最大流量
    • 流量
      • 每个边被指派的数值
  • 注意
    • 流网络通常被定义为有向的，实际也可以找到无向图的最大流
  • 解决
    • Ford-Fulkerson方法
      • 按容量值将边分割成多条
      • 规则
        • 除s、t外进入节点的流的数量等于出节点的数量
        • 流的多数c(e)单元通过任意给定边
          • c(e)：边e的容量
      • 创建增广矩阵
      • 没有运行时间保证
        • 容量不合理，可能无法终止
        • 按BFS遍历，得到Edmonds-Karp算法
          • O(nm2)
  • 代码实现
    • 使用BFS和标记法找增广路径
    • Ford-Fulkerson方法
  • sidebar
    • 残余网络
      • 残余网络Gf，原始流网络G，流f
      • 在Gf中，有一个从u到v的边，当且仅当
        • 在G中从u到v有个不饱和的边
        • 在G中从u到v有正向流
      • G中特殊的增广遍历在Gf中完全普通的遍历
      • 终止
        • 残余网络中没有路径从源点到汇点
• 最小割
  • 最小割
    • 对于图中两个节点，如果去掉一些边，刚好让他们无法连通的话，去掉的边的集合叫做割
    • 权重之和最小的割叫最小割
  • 最大流最小割理论
    • 最大流的流量=最小割的截量
  • 证明
    • 我们已发现一个大小为k的流和容量为k的割
    • 我们已发现最大流
    • 没有增广路径了
  • 证明的意义
    • Ford-Fulkerson方法是正确的
    • 使用它找到最小割
  • 应用
    • 分配不同处理器（CPU、GPU），使减少通讯开销
  • sidebar
    • 对偶性
      • 优化
        • primal
        • dual
      • 更多
        • Duality in Optimization and Variational Inequalities, by Go and Yang.
• 最小费用最大流和分配问题
  • 注意
    • 本节可能较难，并对本书其他部分无影响
  • 问题
    • 为每条边添加费用
    • 总费用为所有边e的w(e)·f(e)之和
      • w：费用
      • f：流函数
  • 应用
    • 最小费用二部图匹配问题
  • Busacker-Gowen方法
    • 找到最小费用增广路径
      • 用带权图的最短路径算法，而不只是BFS
      • 如果假定代价函数为正，则可用Dijkstra找增广路径
      • 一旦推入一些流从u到v，则遍历（虚构的）反向边vu（负费用）
      • Dijkstra第一次迭代很好，后边不行
        • Edomonds-Karp，适应所有权重
          • 使之均正
          • 遍历时形成telescoping sum，确保最短路径仍旧最短
    • 参数
      • w(u,v)：边权重
        • 根据增广路径遍历规则改变
      • h(v) = d(s,v)
      • w'(u,v) = w(u,v) + h(u) - h(v)
    • 运行时间
      • 取决于选择的最短路径算法
      • Dijkstra
        • O(kmlg n)
    • 代码实现
• 一些应用
  • baseball elimination
    • 问题
      • 你有一个部分完成的锦标赛
      • 你想知道某个队是否能赢得锦标赛
      • 即如果他们至多赢W场接下来的比赛，是否可能没有其他队伍多于W场胜利
    • 解决
  • 选择代表
    • 问题
      • 一个城镇，n个居民x，m个俱乐部c，k个政治团体p
      • 每个居民是至少一个俱乐部的成员，是且仅是一个政治团体的成员
      • 每个俱乐部必须任命一个成员作为代表参加镇议会
      • 每个政治团体pi的代表最多ui个
    • 解决
  • 假期医生
    • 问题
      • 指定假期医生安排
      • 每个假日必须指定至少一个医生
      • 限制
        • 每个医生只在一些假期可用
        • 每个医生只能被指定总共在假期工作c天
        • 每个医生每个假期只能被指定工作1天
    • 解决
  • 供需问题
    • 问题
      • 管理行星间送货业务
      • 尝试分配某种商品
      • 每个行星有特定的供应或需求
      • 你的路径有确定的容量
    • 解决
  • 一致性矩阵舍入
    • 问题
      • 有一个浮点数矩阵
      • 希望四舍五入到整数
      • 每列和行都有和，和也要被舍入
      • 你可以自由选择每种情况向上或向下舍入
      • 每行/列舍入数值的和和舍入后的行/列和相同
    • 解决
• 扩展阅读
  • 流算法
    • Dinic算法
      • 和Edmonds-Karp算法非常相关
    • push-relabel算法
      • 快于Edmonds-Karp算法
  • 二部图匹配
    • Hopcroft-Karp算法
      • 改善运行时间
    • 最小代价偶匹配
      • Hungarian算法
      • CSA算法
  • 更多先进的流问题
    • circulations
    • 多物资流问题
  • 更多应用
    • Network Flows: Theory, Algorithms, and Applications by Ahuja, Magnanti, and Orlin
    • Flows in Networks, by Ford and Fulkerson