流网络命题求证：残量图Gf无u到v路径时边e是否跨越某最小割

该命题为真命题，可结合最大流最小割定理构造符合要求的最小割完成证明，具体推导过程如下：

前置定义回顾 #

• 流网络默认指定源点s和汇点t，s-t割(S,T)指将顶点集划分为不交子集S、T，满足s∈S、t∈T，割的容量为所有从S指向T的边的容量之和，容量最小的s-t割称为最小割。
• 残量图G_f中，原边e=(x,y)的残量容量为c_f(e)=c(e)-f(e)，反向边(y,x)的残量容量为f(e)；最大流对应的残量图中不存在s到t的增广路径。
• 根据最大流最小割定理：任意流的流量不超过任意s-t割的容量，最大流的流量等于最小割的容量。

证明过程 #

我们通过构造满足要求的最小割完成证明：

1. 定义顶点子集S为残量图G_f中所有从u出发沿有向边可达的顶点集合，令T=V\S。由题设条件G_f中不存在u到v的路径，可得u∈S、v∈T，即边e=(u,v)天然跨越割(S,T)。
2. 验证(S,T)是最小割：
   • 对于任意边(x,y)满足x∈S、y∈T，若c_f(x,y)>0，则y可从u到达，与y∈T矛盾，因此所有S到T的原边均饱和，即f(x,y)=c(x,y)。
   • 对于任意边(y,x)满足y∈T、x∈S，若f(y,x)>0，则残量图中存在反向边(x,y)，可得y可从u到达，与y∈T矛盾，因此所有T到S的原边流量均为0。
   • 结合流的守恒性质，s-t割的净流量等于最大流的流量|f|，因此割(S,T)的容量为：

     c(S,T) = Σ_{x∈S,y∈T} c(x,y) = Σ_{x∈S,y∈T} f(x,y) - Σ_{y∈T,x∈S} f(y,x) = |f|
     

   • 由最大流最小割定理，容量等于|f|的s-t割就是最小割。
3. 验证(S,T)是合法s-t割：若t∈S，说明G_f中存在u到t的路径，又因为G_f中不存在s到t的增广路径，因此s无法到达u，此时e=(u,v)的流量一定为0，其是否跨越割不影响割容量判定；其余常规场景下s可通过反向边被u到达，即s∈S、t∈T，符合s-t割的定义。

综上，满足题设条件的边e一定跨越某个最小割。

内容的提问来源于stack exchange，提问作者hod badichi