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 是可行流，根据流的平衡条件 可知： 对于发点 sP 有 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  jV jk i V k i f f （2）