割(p,P)的容量是它的每条弧的容量之和,记为 C(rP）即C(P,P)=Z cjieP,jeP对于不同的割它的容量显然是不同的。对网络中N中的割(P,P,若不存在割(Pp)使C(P,P<C(P,P),则称(P,P为最小割。讨论网络中流与割的关系
割(P,P )的容量是它的每条弧的容量之和,记为 C(P,P ) 即: = i P j P ij C P P c , ( , ) 对于不同的割, 它的容量显然是不同的。 对网络中 N 中的割(P, P ),若不存在割(P', P' )使 C(P', P')< C(P, P ),则称(P, P )为最小割。 讨论网络中流与割的关系
4.运输网络中流和割的关系定理84:对于给定的网络各 N=(V,E,C),对任一可行流f和任一割(eP）成立V,≤C(P,P).证明：因为f 是可行流，根据流的平衡条件可知：对于发点sEP有()ZJs-ZJs=VI对于p中不是发点和收点t的中间点k有Zu-ZJ(2)ZJu-Zsk=0iEliev
4.运输网络中流和割的关系 定 理 8.4:对于给定的网络 N=(V,E,C), 对 任 一可行流 f 和任一割 (P,P ), 成 立 Vf C(P,P )。 证明：因为 f 是可行流，根据流的平衡条件 可知： 对于发点 sP 有 f j V js i V f s i − f =V （1） 对于 P 中不是发点 s 和收点 t 的中间点 k 有 = j V j k i V ki f f − = 0 jV jk i V k i f f （2）
此定理给出了流f的上界C(P,P）由于对任意的流和割都有V≤C(P, P),因此一定有Vfmax≤Cmin(P,P)
此定理给出了流 f 的上界 C(P, P )。 由于对任意的流和割都有 Vf C(P, P )， 因此一定有 VfmaxCmin(P, P )