增广路定理 简证

Part 1

一个网络流正在流动。

现在任意割断它,分成源点所在的S点集、汇点所在的T点集。

除了源点,其它点都没有实际输出,

除了汇点,其它点都没有实际获得,

所以,S到T的净输出 = 源点的输出 = 总流量。

所以,网络中任意一个割的净流 = 网络当前的总流量。

因为割的净流 <= 这个割的容量(显然),

所以网络总流量 = 此流量下任意一个割的净流 <= 这个割的容量,

所以任何一种网络流的总流量 <= 任意一个割(割的大小指的是割的容量)。

Part 2

如果一张网络它没有增广路了,

那么源点到汇点顺着“有残余容量的边”(残余网络)不能到达汇点。

现在,源点顺着残余网络能够到达的所有点,叫作点集S,

整张图其它点叫作点集T。

则S连向T的那些边没有残余容量。(否则,顺着此边流过去的点也是源点能到达的点,也属于点集S)

如果割掉这些边,

那么,此割的净流 = 此割的容量(因为没有残余容量)。

因为当前网络的流量 = 该流量下任意一个割的净流,

所以当前网络的流量 = 此割的容量。

因为任何一种网络流的流量 <= 任意一个割的容量,

所以,当前网络流就是上面一个不等式左右两边的交界,

即:任何一种网络流 <= 当前网络流 = 此割的容量 <= 任何一个割的容量。

所以这个网络流是网络最大流。而且此割是最小的一个割,最大流 = 最小割。

原文地址:https://www.cnblogs.com/cicos/p/10283582.html