割(P,P)的容量是它的每条孤的容量之和记为C,) 即 C(P,P)=∑ t∈P,j∈P 对于不同的割它的容量显然是不同的。 对网络中N中的割(P,P),若不存在割(P,P)使 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,对任 一可行流∫和任一割(),成立v C(P P 证明:因为∫是可行流,根据流的平衡条件 可知: 对于发点s∈P有 多 ∑fs-∑fs= 多J∈ 对于P中不是发点s和收点t的中间点k有 ∑f=∑f ∑/-∑/k=0(2)
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)。 由于对任意的流和割都有Ⅴ ≤C(PP), 因此一定有 Vimaxscmin'(P,P)
此定理给出了流 f 的上界 C(P, P )。 由于对任意的流和割都有 Vf C(P, P )， 因此一定有 VfmaxCmin(P, P )