第4章：網(wǎng)絡(luò)規(guī)劃

第四章：網(wǎng)絡(luò)規(guī)劃4.1圖一、起源

1736年瑞士數(shù)學(xué)家歐拉（E.Euler）在求解七橋一筆畫(huà)難題時(shí)，就用了點(diǎn)線圖來(lái)分析論證：每個(gè)點(diǎn)均有奇數(shù)條邊時(shí)，一筆畫(huà)問(wèn)題無(wú)解。ACBDCDAB(前蘇)哥尼斯堡城中的普雷格爾河1二、圖的概念

圖由代表所研究對(duì)象的點(diǎn)和表示對(duì)象之間關(guān)聯(lián)性質(zhì)的線構(gòu)成，一般稱(chēng)為點(diǎn)線圖。上面表示的圖就是點(diǎn)線圖，其中（a）圖的線不帶表示關(guān)聯(lián)方向的箭頭，一般稱(chēng)為邊，這樣的圖稱(chēng)為無(wú)向圖；（b）圖的帶有表示關(guān)聯(lián)方向的箭頭，一般稱(chēng)為弧，這樣的圖稱(chēng)有向圖。記為G={V,E}，其中點(diǎn)集和線集分別表示為

V={v1,v2,…,vn},vj

也稱(chēng)為頂點(diǎn)、端點(diǎn)或節(jié)點(diǎn)；E={e1,e2,…,em},ei可以是邊，也可以是弧。

V1V2V3V4V5V6V7V8V1V2V4V3V5V6V7V8V9e1e2e3e4e5e6e7e8e9e10e11e13e122

1、點(diǎn)：以無(wú)向圖為例點(diǎn)的次數(shù)（度數(shù)）：與點(diǎn)vi關(guān)聯(lián)的邊數(shù)稱(chēng)為的次數(shù)（度數(shù)），記為d(vi)。如：d(v1)=5，稱(chēng)頂點(diǎn)v1的次數(shù)為5，或稱(chēng)v1為5度關(guān)聯(lián)。奇點(diǎn)：次數(shù)（度數(shù)）為奇數(shù)的點(diǎn)叫奇點(diǎn)。如：v1,v2等均是奇點(diǎn)。偶點(diǎn)：次數(shù)（度數(shù)）為偶數(shù)的點(diǎn)叫偶點(diǎn)。如v7,v8等均是偶點(diǎn)。懸掛點(diǎn)：次數(shù)（度數(shù)）為1的點(diǎn)叫懸掛點(diǎn)。如：v4,v5均是懸掛點(diǎn)。孤立點(diǎn)：次數(shù)（度數(shù)）為0的點(diǎn)叫孤立點(diǎn)。即與任何邊都沒(méi)有關(guān)聯(lián)的頂點(diǎn)。如v9為孤立點(diǎn)。

2、邊：以無(wú)向圖為例可用{vi,vj}表示。多重邊：關(guān)聯(lián)于兩個(gè)相鄰頂點(diǎn)的邊稱(chēng)為多重邊。如：e11與e13稱(chēng)為多重邊。環(huán)：兩端點(diǎn)接于同一頂點(diǎn)的邊稱(chēng)為環(huán)。如：e12稱(chēng)為環(huán)。懸掛邊：與懸掛點(diǎn)關(guān)聯(lián)的邊叫懸掛邊。如e3,e7均是懸掛邊。V1V2V4V3V5V6V7V8V9e1e2e3e4e5e6e7e8e9e10e11e13e123三、鏈和路

1、鏈：從某點(diǎn)開(kāi)始的點(diǎn)邊交替序列稱(chēng)為鏈。如上圖中的{v4,e3,v2,e1,v1,e4,v3,e2,v2,e1,v1,e6,v6,e8,v7}稱(chēng)為一條鏈。

圈：首尾相連的鏈叫圈。

2、路：無(wú)重復(fù)點(diǎn)和無(wú)重復(fù)邊的鏈叫做路。如上圖中的{v4,e3,v2,e1,v1,e4,v3,e5,v6,e9,v8}稱(chēng)為一條路?；芈罚菏孜蚕噙B的路叫回路。如上圖中的{v1,e4,v3,e5,v6,e6,v1}稱(chēng)為一回路。V1V2V4V3V5V6V7V8V9e1e2e3e4e5e6e7e8e9e10e11e13e12以上點(diǎn)邊序列中的邊表示為e={vi,vj},所以點(diǎn)邊序列可由點(diǎn)列確定。如上面的回路可寫(xiě)為{v1,v3,v6,v1}。在有向圖中，弧區(qū)分為正向弧和反向弧，其鏈和路的概念與無(wú)向圖相似，點(diǎn)弧序列中弧也有正向弧和反向弧之分。四、連通圖：

任意兩點(diǎn)之間可由一條鏈連接起來(lái)相通的圖叫連通圖。否則，稱(chēng)為非連通圖。如：上圖就不是連通圖，因?yàn)辄c(diǎn)V9與任何點(diǎn)之間均沒(méi)有鏈連接起來(lái)相通。

4五、子圖和部分圖：設(shè)G1={V1，E1}，G2={V2，E2}，G={V，E}1、子圖：若V2V1，E2

E1，則稱(chēng)G2是G1的一個(gè)子圖。真子圖：若V2V1，E2

E1，則稱(chēng)G2是G1的一個(gè)真子圖。

2、部分圖：若V2=V1，E2

E1，則稱(chēng)G2是G1的一個(gè)部分圖，即包含原圖全部頂點(diǎn)的子圖。

3、零圖：若E=ф，則稱(chēng)G為零圖，即由許多孤立點(diǎn)構(gòu)成的圖。

4、空?qǐng)D：若V=ф和E=ф

，則稱(chēng)G為空?qǐng)D。六、同形圖：兩個(gè)圖，從外表上看不一致，但它們保持了各自代表的對(duì)象間相同的關(guān)聯(lián)性質(zhì)，稱(chēng)為同形圖，如下面兩個(gè)圖就是同形圖。

結(jié)論：圖的頂點(diǎn)可以任意挪動(dòng)位置，而邊是完全彈性的，只要在不拉斷的條件下，可從一個(gè)形狀的圖變形為另一個(gè)形狀的圖，且關(guān)聯(lián)性質(zhì)不變。

V1V2V3V4V5e1e2e3e4e5e6e7V1V2V3V4V5e1e2e3e4e5e6e754.2樹(shù)一、樹(shù)的概念

一個(gè)無(wú)圈的連通圖稱(chēng)為樹(shù)。

如：在有線通訊網(wǎng)和交通網(wǎng)中，在保證節(jié)點(diǎn)連通的條件下，邊數(shù)最少（可以節(jié)省材料和投資）的線路圖必然是樹(shù)，如下圖所示

：v1v2v3v4v5v6v1v2v3v4v5v6邊為樹(shù)枝，次為1的頂點(diǎn)為樹(shù)葉。一些行政管理機(jī)構(gòu)和軍隊(duì)的建制也常用樹(shù)來(lái)表示相互隸屬關(guān)系；圖書(shū)分類(lèi)、會(huì)計(jì)科目、決策過(guò)程等等也都可以畫(huà)成樹(shù)圖。

二、樹(shù)的性質(zhì)

①、任何樹(shù)必有樹(shù)葉(即次數(shù)為1的節(jié)點(diǎn))。

②、樹(shù)中任意兩點(diǎn)之間有且僅有一條鏈連接相通。任意去掉一條樹(shù)枝，該樹(shù)就被分割成兩互不連通的子圖。

③、一連通圖可能具有很多樹(shù)，這些樹(shù)都是原連通圖的部分圖，即包括了原連通圖的所有頂點(diǎn)。6三、圖的部分樹(shù)若圖G={V,E}的部分圖T={V,E’}是樹(shù)，則T稱(chēng)為圖G的一個(gè)部分樹(shù)。即：連接圖全部頂點(diǎn)的最小邊數(shù)的部分圖。定理1：圖G是連通的充分必要條件為

圖G有部分樹(shù)。v1v2v3v4v5v6v1v2v3v4v5v6v1v2v3v4v5v67四、賦權(quán)無(wú)向圖的最小部分樹(shù)1、最小部分樹(shù)定義：權(quán)數(shù)之和(數(shù)量指標(biāo)之和)為最小的部分樹(shù)叫最小部分樹(shù)。

v1v2v3v4v5v6132873566v1v2v3v4v5v613736∑ei

=1+3+3+7+6=20v1v2v3v4v5v612536∑ei

=1+2+3+5+6=172、最小部分樹(shù)定理：若T*是圖G的一棵樹(shù)，則

T*是最小樹(shù)充分必要條件為對(duì)T*外的每條邊(vi,vj)，其權(quán)wij≥max{wii1，wi1i2，，wikj}

其中：{vi,vi1,,vj}是T*內(nèi)連接點(diǎn)vi和vj的唯一的鏈。883、最小部分樹(shù)求法①避圈法：將連通圖所有邊按權(quán)從小到大排序，每步從未選的邊中選一條權(quán)最小的邊逐條銜接，但不能成圈。②破圈法：在連通圖中任取一圈，去掉一條權(quán)數(shù)最大的邊，在余下的圖中重復(fù)以上步驟，直至無(wú)圈為止。例：某工廠內(nèi)聯(lián)結(jié)六個(gè)車(chē)間的道路網(wǎng)如下圖示，巳知每條道路的長(zhǎng)度，要求沿道路架設(shè)聯(lián)結(jié)六個(gè)車(chē)間的電話網(wǎng)，使電話線總長(zhǎng)度最短?v1v2v3v4v5v6132873566v1v2v3v4v5v612356∑ei

=1+2+3+5+6=17v1v2v3v4v5v6132873566∑ei

=1+2+3+5+6=1794.3網(wǎng)絡(luò)最短路線問(wèn)題一、最短路線問(wèn)題的概念

v1v2v3v5v6v7v4718234312274二、原理：Be1lman優(yōu)化原理。在網(wǎng)絡(luò)圖中的表述如下：若{V1，V2，，Vn}是從V1到

Vn的最短路徑，Vk

是其中任一點(diǎn)，則

{V1，V2，，Vk}也是從V1到

Vk的最短路徑。

v1vkvn10三、最短路線求法

T,P標(biāo)號(hào)算法：1959年狄克斯特拉E.W.Dijkstra提出，僅適用于所有弧權(quán)dij≥0的網(wǎng)絡(luò)圖。用指標(biāo)函數(shù)迭代逐步正向搜索，直至指標(biāo)函數(shù)衰減穩(wěn)定為止。

T(Vj)k=min{T(Vj)k-1，P(Vi)+dij}

其中：T---為臨時(shí)或試探性標(biāo)號(hào)，表示V1到Vj的估計(jì)最短距離，后要改為P標(biāo)號(hào)。

(所有求出的T標(biāo)號(hào)中，選最優(yōu)者改為P標(biāo)號(hào))P---為永久性標(biāo)號(hào)，表示V1到Vj的最短距離

T(Vj)k

表示第k步從V1到Vj的估計(jì)最短距離；

P(Vi)表示從V1到Vi的最短距離；

dij

表示從Vi到Vj的實(shí)際距離。例1：求下列網(wǎng)絡(luò)中，從V1到V7的最短路徑及最短路徑距離。v1v2v3v5v6v7v471823431227411解：⑴先用T,P標(biāo)號(hào)法求從V1到各點(diǎn)Vj的最短距離：T(Vj)k=min{T(Vj)k-1，P(Vi)+dij}

第一步：T(Vj)=，(j=1,…,7)，v7v1v2v3v5v6v47182343122740144579第二步：從V1可達(dá)V2、V3，修改其T標(biāo)號(hào)，將已求出的所有T標(biāo)號(hào)中的最優(yōu)者改為P標(biāo)號(hào)。

T(V2)①=min{T(V2)，P(V1)+d12}=min{，0+7}=7

T(V3)①=min{T(V3)，P(V1)+d13}=min{，0+1}=1第三步：從V3可達(dá)V2、V4、V6，修改其T標(biāo)號(hào)，將已求出的所有T標(biāo)號(hào)中的最優(yōu)者改為P標(biāo)號(hào)。

T(V2)②=min{T(V2)①，P(V3)+d32}=min{7，1+3}=4

T(V4)①=min{T(V4)，P(V3)+d34}=min{，1+4}=5

T(V6)①=min{T(V6)，P(V3)+d36}=min{，1+3}=4第四步：A.從V2可達(dá)V4、V5，修改其T標(biāo)號(hào)。

T(V4)②=min{T(V4)①，P(V2)+d24}=min{5，4+2}=5

T(V5)①=min{T(V5)，P(V2)+d25}=min{，4+8}=12

B.從V6可達(dá)V4、V7，修改其T標(biāo)號(hào)，將已求出的所有T標(biāo)號(hào)中的最優(yōu)者改為P標(biāo)號(hào)。

T(V4)③=min{T(V4)②，P(V6)+d64}=min{5，4+4}=5

T(V7)①=min{T(V7)，P(V6)+d67}=min{，4+7}=11第五步：從V4可達(dá)V7，修改其T標(biāo)號(hào)，將已求出的所有T標(biāo)號(hào)中的最優(yōu)者改為P標(biāo)號(hào)。

T(V7)②=min{T(V7)①，P(V4)+d47}=min{11，5+2}=7第六步：從V7可達(dá)V5，修改其T標(biāo)號(hào)，將已求出的所有T標(biāo)號(hào)中的最優(yōu)者改為P標(biāo)號(hào)。

T(V5)②=min{T(V5)①，P(V7)+d75}=min{12，7+2}=9P(V1)=0①=P(V3)②=P(V6)③=P(V2)③=P(V4)④=P(V7)⑤=P(V5)⑥12

⑵用反向跟蹤法求最短路徑：設(shè)Vj的緊前點(diǎn)為Vk，則P(Vk)=

P(Vj)-dkj

第一步：求V7的緊前點(diǎn)為Vk：P(Vk)=

P(V7)-dk7=7-{d47,d67}

=7-{2,7}={5,0}={P(V4),P(V6)}=P(V4)v7v1v2v3v5v6v47182343122740144579第二步：求V4的緊前點(diǎn)為Vk：P(Vk)=

P(V4)-dk4=5-{d54,d24,d34,d64}

=5-{1,2,4,4}={4,3,1,1}={P(V5),P(V2),P(V3),P(V6)}=P(V3)第三步：求V3的緊前點(diǎn)為Vk：P(Vk)=

P(V3)-dk3=1-d13=1-1=0=P(V1)

故所求的最短路為：V1V3V4V7142

所求的最短路距離為：1+4+2=7134.4網(wǎng)絡(luò)最大流問(wèn)題一、問(wèn)題的提出

交通網(wǎng)絡(luò)中要研究車(chē)輛的最大通過(guò)能力；生產(chǎn)流水線網(wǎng)絡(luò)上產(chǎn)品的最大加工能力；供水網(wǎng)絡(luò)中通過(guò)的最大水流量；信息網(wǎng)中信息最大傳送能力等等?；∪萘縞ij：網(wǎng)絡(luò)的組成弧都具有確定的通過(guò)能力(有時(shí)稱(chēng)為硬件能力)；弧流量fij：實(shí)際通過(guò)弧的流量(有時(shí)稱(chēng)為軟件能力)；

研究的問(wèn)題：因各弧容量的配置關(guān)系不調(diào)，有些流量常常達(dá)不到容量值。因此，研究實(shí)際能通過(guò)網(wǎng)絡(luò)的最大流量問(wèn)題，可以評(píng)估網(wǎng)絡(luò)的最大運(yùn)載能力，明確為使最大流量增大應(yīng)如何改造網(wǎng)絡(luò)。v1v2v3v5v6v470100904070904080100,50,50,60,50,40,90,50,80,30源點(diǎn)匯點(diǎn)14二、基本概念

1、容量網(wǎng)絡(luò)：標(biāo)有弧容量cij的網(wǎng)絡(luò)叫容量網(wǎng)絡(luò)。

2、網(wǎng)絡(luò)流：容量網(wǎng)絡(luò)中，實(shí)際通過(guò)各弧的流量集F={fij}稱(chēng)為網(wǎng)絡(luò)流。由于各弧容量的配置可能不協(xié)調(diào)，實(shí)際通過(guò)各弧的流量fij不可能處處都達(dá)到容量值cij。

3、可行流：對(duì)給定的容量網(wǎng)絡(luò)，在滿(mǎn)足下列兩個(gè)條件①、②的網(wǎng)絡(luò)流稱(chēng)為可行流：

①容量約束條件：0≤fij≤cij。即0≤f12≤70，0≤f13≤100，0≤f14≤90，0≤f26≤80，0≤f34≤40，

0≤f35≤70，0≤f45≤40，0≤f46≤100，0≤f56≤90。

②節(jié)點(diǎn)流量平衡條件：每個(gè)節(jié)點(diǎn)的流入總量等于流出總量。V1:Q=f12+f13+f14；V2:f12=f26

；V3:f13=f34+f35V4:f14+f34=f45+f46；V5:f35+f45=f56；V6:f26+f46+f56=Q?？尚辛骺偞嬖?，如零流{fij=0}就是一個(gè)可行流,即容量網(wǎng)絡(luò)沒(méi)有給出流量fij時(shí),就認(rèn)為fij=0。

4、最大流：使得從網(wǎng)絡(luò)源點(diǎn)（或稱(chēng)發(fā)點(diǎn)）到匯點(diǎn)（或稱(chēng)收點(diǎn)）的總流量Q達(dá)到最大的可行流F={fij}

稱(chēng)為最大流。v1v2v3v5v6v470100904070904080100,50,50,60,50,40,90,50,80,30源點(diǎn)匯點(diǎn)C12C26C13C14C34C46C45C56C35,f12,f26,f14,f13,f34,f46,f45,f35,f5615三、增廣鏈

給出網(wǎng)絡(luò){cij,fij}，其中{fij}為可行流，fij

v1v2v3v4v5v6354112352,3,3,3,1,1,1,1,2,0v1v2v3v4v65415,3,3,1,1

1、增廣鏈定義：一條從起點(diǎn)到終點(diǎn)的鏈，且正向弧必是非飽和弧，反向弧必是非零弧。即：正向飽和弧和反向零弧均不入鏈。正向非飽和弧充許增大流量，反向非零弧，充許減小流量（維持節(jié)點(diǎn)量平衡）。如鏈：L={v1,v3,v2,v4,v6}為一條增廣鏈。其中：正向弧集L+={(v1,v3),(v2,v4),(v4,v6)}均為非飽和弧。反向弧集L-={(v3,v2)}為非零弧。在增廣鏈上存在增大輸送能力的潛力。

2、增廣鏈作用：網(wǎng)絡(luò)可行流為網(wǎng)絡(luò)最大流的判別方法。檢查該可行流中是否存在增廣鏈，若不存在，則當(dāng)前可行流為最大流；否則，當(dāng)前可行流為非最大流，總流量還可增大。注：網(wǎng)絡(luò)流非最大時(shí)，往往存在多條增廣鏈。16四、最小割v1v2v3v4v5v6354112352

1、割集概念的引入：一個(gè)容量網(wǎng)絡(luò)，由于各弧容量Cij配置得不合適，結(jié)果有的地方能通過(guò)較大流量，而有的地方能通過(guò)的流量較量卻較小。小的地方就限制了最大流的上限值，稱(chēng)為網(wǎng)絡(luò)流的“瓶頸”（或俗稱(chēng)“卡脖子”地區(qū)）。因此,研究從起點(diǎn)到終點(diǎn)的流徑中，哪些弧容量起了限制最大流作用，而割集就是研究網(wǎng)絡(luò)流“瓶頸”的一種工具。

2、割集的定義：使連通圖分成兩個(gè)互不連通子圖的弧的最小集合，記為S={(vI,,vj)}。

S1={(V1,V2),(V1,V3)}容量C1=3+5=8

S2={(V2,V4),(V3,V5)}

容量C2=4+2=6

S3={(V4,V6),(V3,V5)}

容量C3=5+2=7

S4={(V1,V2),(V3,V5)}容量C4=3+2=5

3、最小割集(最小割)的定義：所有割集中容量最小的割集，記為S(v*,v*)。實(shí)際流F的流量Q（F）≤C(v*,v*)。

4、最小割集與最大流定理：容量網(wǎng)絡(luò)中，實(shí)際流F所能達(dá)到的最大流量Q(F*)等于該容量網(wǎng)絡(luò)最小割的容量C(v*,v*)。

即：Q(F*)=C(v*,v*)17五、最大流與最小割求法---標(biāo)號(hào)法

1、原理：從網(wǎng)絡(luò)圖的一可行流出發(fā)，用給頂點(diǎn)標(biāo)號(hào)的方法找增廣鏈。若找得到增廣鏈,說(shuō)明當(dāng)前流非最大,則沿增廣鏈方向增大可行流得新可行流，然后在新可行流中繼續(xù)找增廣鏈，直到在某個(gè)新可行流中找不到增廣鏈時(shí)，這個(gè)新可行流就是最大流，同時(shí)也得到最小割。2、標(biāo)號(hào)形式：(±vi,Δfij），其中Δfij=例1求下圖容量網(wǎng)絡(luò)中，從v1到v6的最大流和最小割。v1v2v3v4v5v6354112352第一步：給出一個(gè)初始可行流，應(yīng)盡量接近最大流。（容量網(wǎng)絡(luò)給出時(shí)，fij=0）一般原則：①、找出回路，給回路上各弧同一流量值，使回路上某些容量較小的弧優(yōu)先達(dá)到飽和。

②、找出從起點(diǎn)到終點(diǎn)的路，給路上各弧同一流量值，使路上某些容量較小的弧優(yōu)先達(dá)到飽和。v1v2v3v4v5v6354112352,1,1,1,3,3,3,1+1,118第二步：給頂點(diǎn)標(biāo)號(hào)找增廣鏈。①對(duì)起點(diǎn)v1標(biāo)號(hào)(0，∞)。v1v2v3v4v5v6354112352,3,3,3,1,1,1,1,2,0(0，∞)②從v1可達(dá)v2，v3：(v1,v2)為正向飽和弧，不入鏈，v2不標(biāo)號(hào)；

(v1,v3)為正向非飽和弧，入鏈，v3標(biāo)(＋v1,4)。(+v1，4)③從v3可達(dá)v2，v5：(v3,v2)為反向非零弧，入鏈，v2標(biāo)（－v3，1）

(v3,v5)為正向飽和弧，不入鏈，v5不標(biāo)號(hào)。（-v3，1）④從v2可達(dá)v4，v5

：(v2,v4)為正向非飽和弧，入鏈，v4標(biāo)(+v2,1)(v2,v5)為反向非零弧，入鏈，v5標(biāo)(-v2,1)(+v2,1)(-v2,1)⑤從v4可達(dá)v6：(v4，v6)為正向非飽和弧，入鏈，v6標(biāo)（+v4,2）。（+v4，2）從v5可達(dá)v6：(v5，v6)為正向非飽和弧,入鏈，v6標(biāo)（+v5,1）。（+v5，1）故：當(dāng)前可行流非最大流，沿增廣鏈L1方向調(diào)整流量l(正向弧增加流量l，反向弧減少流量1)，其余弧流量不變，得一新可行流。+1-1+1+1v1v2v3v4v5v6354112352,3,4,4,2,1,0,1,2,0得一條增廣鏈：L1={v1,v3,v2,v4,v6}得另一條增廣鏈：L2=｛v1,v3,v2,v5,v6｝19第三步：給新可行流各頂點(diǎn)標(biāo)號(hào)找增廣鏈。①對(duì)起點(diǎn)v1標(biāo)號(hào)(0，∞)。v1v2v3v4v5v6354112352,3,4,4,2,1,0,1,2,0(0，∞)(+v1，3)②從v1可達(dá)v2，v3：(v1,v2)為正向飽和弧，不入鏈，v2不標(biāo)號(hào)；

(v1,v3)為正向非飽和弧，入鏈，v3標(biāo)(＋v1,3)。③從v3可達(dá)v2，v5：(v3,v2)為反向零弧，不入鏈，v2不標(biāo)號(hào)

(v3,v5)為正向飽和弧，不入鏈，v5不標(biāo)號(hào)。標(biāo)號(hào)過(guò)程中斷，找不到增廣鏈，當(dāng)前可行流為最大流。第四步：確定最小割和最大流量。①最小割：將已標(biāo)號(hào)的頂點(diǎn)v1、v3構(gòu)成非空集v*={v1,v3}，未標(biāo)號(hào)的其它頂點(diǎn)v2,v4,v5,v6構(gòu)成補(bǔ)集

v*={v2,v4,v5,v6},形成最小割(將v*,v*分開(kāi))：Smin={(v1,v2),(v3,v5)},其容量為C(v*,v*)=3+2=5Smin={(v1,v2),(v3,v5)},其容量為C(v*,v*)=3+2=5②最大流量Ｑ(F*):根據(jù)最大流――最小割定理有Ｑ(F*)=C(v*,v*)=5注：最小割Smin所包含弧（v1,v2）,(v3,v5)為網(wǎng)絡(luò)關(guān)鍵弧。若要增大網(wǎng)絡(luò)最大流，必須首先設(shè)法改善這些關(guān)鍵弧的狀況，提高它們?nèi)萘?；如果最小割中的弧通過(guò)能力一旦降低，則會(huì)使總流量減小。另外，在各弧容量一定的網(wǎng)絡(luò)中，最大流的總流量是唯一的，最小割卻不一定是唯一的。20ABCEDSFGHT30,2015,1520,520,2010,1020,2010,1010,510,1010,1020,