【知识总结】 网络流

网络的基本概念

• 网络：弧带权的有向图
  • 弧的权又称弧的容量，记作
  • 只讨论简单的有向图（无环弧、无并行弧）
  • 有一个特殊的源点，记作
  • 有一个特殊的汇点，记作
• 流：
  • ：定义在弧上的非负实值函数
  • ：顶点的所有出弧的流量和
  • ：顶点的所有入弧的流量和
• 可行流：
  • 容量约束：
  • 守恒约束：
• 对于任意网络，可行流总是存在的，比如：零值流
• 流量：
• 必有
• 最大流：流量最大的可行流
• f增广路
  • 底图中的一条s-t路
  • 经过的每条正向弧
  • 经过的每条反向弧
• 增广路的“可增量”