第十章以路的流 图10-3 解在图10-3所示的网络G中图上=，小7=，，小那么制 K(,T1)={1,,(2,4) 制K的容量 c(,71)=9+9=18. 注意在线成上述划的边集合中不句括(，2) 我们用表10-1列出图10-3中全部不同的割K及割K的容量c(M,) 表10-1 K(,T) cy,7) ,2,的，4， (s,,(s,2】 15 8,1 t2,均，4：t (s,y),(U1,2),(U1,s) 21 S.U7 v1.U3.U4.t (s.1),(y,v4) 17 ,4, 8,1, U2,U, (s,2,(o1,2,(g,,(,t) 19 5,2,4 ,3,t （s,1),(U4,3),(U4,t) 24 ,,2, (2,a,(g,) s,1,2,4 3, (1,),(u4,g(v4,) 25 8,的，2，g,4 (g,t,(4,t) 15 具有最小容量的制称为最小割。由表10-1可这，图10-3中制K(,T)={(,,(,t} 的容量c(,7)=14是最小制 若用f(%,7)表示割中所有→71方向边的流量的总和，f(T1,M)表示割中所有 71一上方向边的流量的总和，则 f%,7)= (10.5) 0,) f,)= (10.6) G.0e71.M) 因为从源s到汇t的流量实际上等于从一了的流量中减去一的流量所 以对应于割处的流量为： (f)=f%,V)-f,) (10.7)4 ✎✑✏✓✒✕✔✓✖✑✗✓✘ ⑥ 10–3 ⑤ : ⑩ ⑥ 10–3 ✝ ➧ ✍❲✟✚✠ G ✦ , ⑥ V1 = {s, v1, v2}, V 1 = {v3, v4,t}, ❆✖❇✖➈ K(V1, V 1) = {(v1, v3),(v2, v4)}. ➈ K ✍✖➆✖➱✖✜ c(V1, V 1) = 9 + 9 = 18. ⑦✿⑩✻✖þ✮①➈✖✍s✖➯✁☞ ✦❏✁⑧✁⑨ (v3, v2)✜ ❼✖❽✖❊➦ 10–1 ❘❩ ⑥ 10–3 ✦✓✇✁⑩❏✁④✍✖➈ K ➁✖➈ K ✍✖➆✖➱ c(V1, V 1). ➦ 10–1 V1 V 1 K(V1, V 1) c(V1, V 1) s v1, v2, v3, v4,t (s, v1),(s, v2) 15 s, v1 v2, v3, v4,t (s, v2),(v1, v2),(v1, v3) 21 s, v2 v1, v3, v4,t (s, v1),(v2, v4) 17 s, v1, v2 v3, v4,t (v1, v3),(v2, v4) 18 s, v1, v3 v2, v4,t (s, v2),(v1, v2),(v3, v2),(v3,t) 19 s, v2, v4 v1, v3,t (s, v1),(v4, v3),(v4,t) 24 s, v1, v2, v3 v4,t (v2, v4),(v3,t) 14 s, v1, v2, v4 v3,t (v1, v3),(v4, v3),(v4,t) 25 s, v1, v2, v3, v4 t (v3,t),(v4,t) 15 ❭❪✩➌➆➱✍➈➚✘❷❶❹❸❹❺☞✜ ❚✡➦ 10–1 ✓❹❻, ⑥ 10–3 ✦➈ K(V1, V 1) = {(v2, v4),(v3,t)} ✍✖➆✖➱ c(V1, V 1) = 14 ✰✩✖➌✖➈✖✜ ❂❊ f(V1, V 1) ➦✖➧➈❲✦✝❪ V1 → V 1 ❋❲➥s ✍✖✛✖➱✖✍✁✴✖➇,f(V 1, V1) ➦✖➧➈❲✦✝❪ V 1 → V1 ❋❲➥s ✍✖✛✖➱✖✍✁✴✖➇, ✃: f(V1, V 1) = X (i,j)∈(V1,V 1) fi,j (10.5) f(V 1, V1) = X (j,i)∈(V 1,V1) fj,i (10.6) ✩✖✘✁❃✖Û s Ð✖Ü t ✍✖✛✖➱❯✖❱✖✮ï ✲❃ V1 → V 1 ✍✖✛✖➱❲✦✓❼✖❧ V 1 → V1 ✍✖✛✖➱, ✝ ✔✖❂✖❃✲ ➈✁❽✖✍✖✛✖➱✖✘: v(f) = f(V1, V 1) − f(V 1, V1) (10.7)