图：网络流算法

最小割问题

流网络

• 正常的有向图（V,E)且包括一个源顶点和目标顶点t
• 每条边e∈E都有一个容量：c（e）≥0
• 不关心走的距离是不是最短的，关心的是流向目标顶点的容量（能不能稳定保持这样的流量）
• 找到最小割能判断出这个网络是否可行

最大流问题

• st-流（st-flow）f是一个函数：
  • 容量问题：对于任意一条边e∈E：流小于等于容量
  • 总量问题：对于任意非s，t的顶点，流入的量等于流出的量
  • 流值：val（f）=流出的量-流入的量
• 最大流问题的一般解法
  • 比如贪心算法
    1. 对每一条边e∈E，设f（e）=0
    2. 在顶点s和t之间找到一条路径P，并保证每条边f（e）<c(e)
    3. 沿着路径P增加流量
    4. 重复这个过程，直到不能再增加为止
• 残差网络
• 增广路径

福德 — 富克逊算法

• 流网络
• 残差网络

最大流-最小割理论

• 流值引理

  • 假设流f
  • 假设流f和任意分割（A,B),则流值f小于等于分割的容量

• 最大流与最小割等价

  • 当福德-富克逊算法停止时，即可获得最大流

  • 这个算法并不完美

    • 如果边容量为正整数，算法会在多项式时间内停止
    • 如果边容量数值为有理数，算法会在指数时间内停止
    • 如果边容量数值为无理数，可能会无法停止