0%

【知识总结】 网络流

网络的基本概念

  • 网络:弧带权的有向图
    • 弧的权又称弧的容量,记作$c(a)\geq 0$
    • 只讨论简单的有向图(无环弧、无并行弧)
    • 有一个特殊的源点,记作$s$
    • 有一个特殊的汇点,记作$t$
  • 流:
    • $f$:定义在弧上的非负实值函数
    • $f^+(v)$:顶点$v$的所有出弧的流量和
    • $f^-(v)$:顶点$v$的所有入弧的流量和
  • 可行流:
    • 容量约束:$\forall a\in A(G),0\leq f(a)\leq c(a)$
    • 守恒约束:$\forall v\in V(G)\setminus \{s,t\},f^+(v)=f^-(v)$
  • 对于任意网络,可行流总是存在的,比如:零值流
  • 流量:
    • $f^-(t)-f^+(t)$
  • 必有$f^-(t)-f^+(t)=f^+(s)-f^-(s)$
  • 最大流:流量最大的可行流
  • f增广路
    • 底图中的一条s-t路
    • 经过的每条正向弧$a\in A(G):f(a)<c(a)$
    • 经过的每条反向弧$a\in A(G):f(a)>0$
  • 增广路的“可增量”