【正文】 最小割集為 ? ?),(),(),(),( 23141 vvvvvvSS s?。 81 vs vt v4 v2 v3 v1 (15,11) (9,9) (3,0) (5,4) (6,5) (7,7) (10,9) (11,11) (4,4) (0,+∞) (vs,4) ? ?1 3 1 4 2( , ) ( , ) , ( , ) , ( , )sS S v v v v v v?用標(biāo)號(hào)法在求得最大流的同時(shí)，可得到一個(gè)最小割集，從圖可知，標(biāo)號(hào)點(diǎn)的集合為 S={vs ,v1}， 此時(shí)割集為 ， 82 例 11 用標(biāo)號(hào)法求圖 vs到 vt的最大流。因?yàn)?(vs,v2)?E，但 fs2=cs2，所以 v2不能標(biāo)號(hào)。 77 vs vt v4 v2 v3 v1 (15,11) (9,9) (3,0) (5,4) (6,5) (7,7) (10,9) (11,11) (4,4) (0,+∞) (vs,7) (v1,3) (v2,1) (v2,3) (v3,3) （ II）調(diào)整過(guò)程 由于 δ t=3，所以調(diào)整量為 3，即增廣鏈 μ上的前向邊流量加 3，后向邊流量減 3 。因?yàn)?δ t= min{δ 3, c3tf3t}=min {3,3}=3, δ t’ = min{δ 4, c4tf4t}= min {1,1}=1，所以 vt的標(biāo)號(hào)應(yīng)?。?v3,3）。 74 vs vt v4 v2 v3 v1 (15,8) (9,9) (3,3) (5,1) (6,5) (7,7) (10,9) (11,8) (4,4) (0,+∞) (vs,7) (v1,3) (v2,1) (v2,3) (v3,3) （ 5）由于與 v3相鄰且沒(méi)有標(biāo)號(hào)的頂點(diǎn)為 vt，并且 vt也與已標(biāo)號(hào)的頂點(diǎn) v4相鄰，所以 vt既可以以 v3為基礎(chǔ)獲得標(biāo)號(hào) (v3,δ t)，也可以以 v4為基礎(chǔ)獲得標(biāo)號(hào) (v4,δ t’)。 73 vs vt v4 v2 v3 v1 (15,8) (9,9) (3,3) (5,1) (6,5) (7,7) (10,9) (11,8) (4,4) (0,+∞) (vs,11) (v1,3) (v2,1) (v2,3) （ 5）檢查與 v2相鄰 且沒(méi)有標(biāo)號(hào) 的頂點(diǎn) v3， v4， 因?yàn)?v2,v3)?E，并且 f23=1c23=5，所以 v3可以獲得標(biāo)號(hào) (v2,δ3)，其中 δ3 =min{δ2, c23f23}=min{3,4}=3。 因?yàn)?v1,v3)?E，但 f13=c13，所以 v3不能標(biāo)號(hào)。因?yàn)?(vs,v2)?E，但 fs2=cs2，所以 v2不能標(biāo)號(hào)。 69 vs vt v4 v2 v3 v1 (15,8) (9,9) (3,3) (5,1) (6,5) (7,7) (10,9) (11,8) (4,4) (0,+∞) (vs,11) (v1,3) (v1,4) (v2,3) (v4,4) （ II）調(diào)整過(guò)程 由于 δ t=4，所以調(diào)整量為 4，即增廣鏈 μ上的前向邊流量加 4。因?yàn)?δ t= min{δ 3, c3tf3t}=min {3,3}=3, δ t’ = min{δ 4, c4tf4t}= min {4,5}=4，所以 vt的標(biāo)號(hào)應(yīng)取（ v4,4）。 (vs,11) (v1,3) (v1,4) (v2,3) 67 vs vt v4 v2 v3 v1 (15,4) (9,9) (3,3) (5,1) (6,5) (7,7) (10,5) (11,8) (4,0) (0,+∞) (vs,11) (v1,3) (v1,4) (v2,3) （ 5）由于與 v3相鄰且沒(méi)有標(biāo)號(hào)的頂點(diǎn)為 vt，并且 vt也與已標(biāo)號(hào)的頂點(diǎn) v4相鄰，所以 vt既可以以 v3為基礎(chǔ)獲得標(biāo)號(hào) (v3,δ t)，也可以以 v4為基礎(chǔ)獲得標(biāo)號(hào) (v4,δ t’)。因?yàn)?(v1,v3)?E，但 f13=c13，所以 v3不能標(biāo)號(hào)。 (vs,11) 65 vs vt v4 v2 v3 v1 (15,4) (9,9) (3,3) (5,1) (6,5) (7,7) (10,5) (11,8) (4,0) (0,+∞) （ 3）檢查與 v1相鄰 且沒(méi)有標(biāo)號(hào) 的頂點(diǎn) v2， v3， v4， 因?yàn)?v2,v1)?E，并且 f210，所以 v2可以獲得標(biāo)號(hào) (v1,δ2)，其中 δ2 =min{δ1, f21}=min{9,3}=3。 vs vt v4 v2 v3 v1 (15,4) (9,9) (3,3) (5,1) (6,5) (7,7) (10,5) (11,8) (4,0) 63 解 （ I）標(biāo)號(hào)過(guò)程 （ 1）首先給發(fā)點(diǎn) vs標(biāo)以 (0,+∞). vs vt v4 v2 v3 v1 (15,4) (9,9) (3,3) (5,1) (6,5) (7,7) (10,5) (11,8) (4,0) (0,+∞) 64 vs vt v4 v2 v3 v1 (15,4) (9,9) (3,3) (5,1) (6,5) (7,7) (10,5) (11,8) (4,0) (0,+∞) （ 2）檢查與 vs相鄰的頂點(diǎn) v1， v2，因?yàn)?vs,v1)?E，并且 fs1=4cs1=15，所以 v1可以獲得標(biāo)號(hào) (vs,δ 1)，其中 δ 1 =min{+∞, 154}=11。ijtijtijijffff δδ.),(,),(,),(μμμ?????jijijivvvvvv調(diào)整結(jié)束后，去掉所有標(biāo)號(hào)，返回標(biāo)號(hào)過(guò)程重新進(jìn)行標(biāo)號(hào)過(guò)程。最后按下式修改可行流 f。例如設(shè)終點(diǎn) vt的第一個(gè)標(biāo)號(hào)為 k，則 (vk,vt)是增廣鏈上的邊，然后根據(jù) vk的第一個(gè)標(biāo)號(hào)，找到下一個(gè)頂點(diǎn)，即若 vk的第一個(gè)標(biāo)號(hào)為 j，則 (vj,vk)（或者 (vk,vj)）是增廣鏈上的邊，直到用此方法找到 vs為止。 60 重復(fù)過(guò)程（ 2），可能出現(xiàn)兩種結(jié)果，其一是終點(diǎn) vt得到標(biāo)號(hào)，說(shuō)明存在一條增廣鏈，則轉(zhuǎn)到調(diào)整過(guò)程，其二是終點(diǎn) vt不能獲得標(biāo)號(hào)，說(shuō)明不存在增廣鏈，這時(shí)可行流 f即為最大流。 （ a）若 (vi,vj)?E，并且 fijcij，則給頂點(diǎn) vj以標(biāo)號(hào) (i,δ j)，其中 δ j =min{δ i , cij fij}。 1 標(biāo)號(hào)過(guò)程 （ 1）首先給發(fā)點(diǎn) vs標(biāo)號(hào) (0,+∞ )。 59 求網(wǎng)絡(luò) G的最大流的標(biāo)號(hào)法分為兩步，第 1步是標(biāo)號(hào)過(guò)程，通過(guò)標(biāo)號(hào)尋找增廣鏈；第 2步是調(diào)整過(guò)程，沿增廣鏈個(gè)性可行流 f的流量。如果在 G中不存在關(guān)于可行流 f的增廣鏈，則可行流 f就是最大流。 三、求最大流的標(biāo)號(hào)算法 由上面定理 1可知可行流 f是否是最大流，關(guān)鍵看網(wǎng)絡(luò) G中是否存在關(guān)于可行流 f的增廣鏈，定理 1的證明過(guò)程為我們提供了尋找增廣鏈的方法及改進(jìn)可行流 f的方法。 58 定理 1 可行流 f *是最大流當(dāng)且僅當(dāng) G中不存在關(guān)于 f *的增廣鏈。 二、最大流最小割集定理 由上面例子可知，如果找到網(wǎng)絡(luò) G的一個(gè)可行流，其流量等于網(wǎng)絡(luò) G的最小割集容量，則該可行流一定是最大流。而網(wǎng)絡(luò)G的最大流量一定不會(huì)超過(guò)容量最小割集的容量，稱網(wǎng)絡(luò) G中容量最小的割集為 G的最小割集。 v1 v2 v3 v4 v5 vs vt (13,7) (5,5) (9,9) (4,4) (6,6) (5,2) (5,0) (4,0) (5,5) (4,4) (9,7) (10,5) 圖 57 如果從網(wǎng)絡(luò) G中去掉割集 (S,T)中的邊，從vs就沒(méi)有路可以到達(dá) vt。割集 (S,T)中所有邊的容量之和稱為割集(S,T)的容量，記為 C(S,T)，即 ( , ) ( , )( , )ijijv v S TC S T c?? ?56 例如圖 ,設(shè) S1={vs}， T 1={ v1, v2, v3, v4, v5, vt}，則 (S1, T1)={ (vs,v1)， (vs,v2)}，其容量為 C (S1, T1)=22。 54 例如圖 ，鏈 μ={vs, v1, v2, v3, v5, vt}就是一條增廣鏈，因?yàn)?μ +={(vs,v1)， (v2,v3)， (v3,v5)， (v5,vt)}中的邊均為非飽和邊，而 μ ={(v1,v2)}中的邊為非零流邊。 若 (vi,vj) ?μ ，則 0fij?cij，即 μ 中每一邊是非零流邊。 即 μ +={(vs,v1)， (v2,v5)， (v5, vt)}， μ ={(v1,v2)}。 (v2,v5)為飽和邊，(vs,v1)為非飽和邊，并且 (v2,v5)， (vs,v1)均為非零流邊， (v3,v5)是零流邊。 另一類(lèi)邊與鏈的正方向相反，稱它們?yōu)楹笙蜻叄?μ上后向邊的全體記為 μ 。 設(shè) μ是網(wǎng)絡(luò) G中一條聯(lián)結(jié)發(fā)點(diǎn) vs和收點(diǎn) vt的鏈 。最大流問(wèn)題