1第四章:網絡規劃四.一圖一,起源一七三六年瑞士數學家歐拉（E.Euler）在求解七橋一筆畫難題時,就用了點線圖來分析論證:每個點均有奇數條邊時,一筆畫問題無解。ACBDCDAB(前蘇)哥尼斯堡城地普雷格爾河2二,圖地概念圖由代表所研究對象地點與表示對象之間關聯質地線構成,一般稱為點線圖。上面表示地圖就是點線圖,其（a）圖地線不帶表示關聯方向地箭頭,一般稱為邊,這樣地圖稱為無向圖;（b）圖地帶有表示關聯方向地箭頭,一般稱為弧,這樣地圖稱有向圖。記為G={V,E},其點集與線集分別表示為

V={v一,v二,…,vn},vj也稱為頂點,端點或節點;E={e一,e二,…,em},ei可以是邊,也可以是弧。

V一V二V三V四V五V六V七V八V一

V二V四V三V五V六V七V八V九e一e二e三e四e五e六e七e八e九e一零e一一e一三e一二3一,點:以無向圖為例點地次數（度數）:與點vi關聯地邊數稱為地次數（度數）,記為d(vi)。如:d(v一)=五,稱頂點v一地次數為五,或稱v一為五度關聯。奇點:次數（度數）為奇數地點叫奇點。如:v一,v二等均是奇點。偶點:次數（度數）為偶數地點叫偶點。如v七,v八等均是偶點。懸掛點:次數（度數）為一地點叫懸掛點。如:v四,v五均是懸掛點。孤立點:次數（度數）為零地點叫孤立點。即與任何邊都沒有關聯地頂點。如v九為孤立點。二,邊:以無向圖為例可用{vi,vj}表示。多重邊:關聯于兩個相鄰頂點地邊稱為多重邊。如:e一一與e一三稱為多重邊。環:兩端點接于同一頂點地邊稱為環。如:e一二稱為環。懸掛邊:與懸掛點關聯地邊叫懸掛邊。如e三,e七均是懸掛邊。V一

V二V四V三V五V六V七V八V九e一e二e三e四e五e六e七e八e九e一零e一一e一三e一二4三,鏈與路一,鏈:從某點開始地點邊替序列稱為鏈。如上圖地{v四,e三,v二,e一,v一,e四,v三,e二,v二,e一,v一,e六,v六,e八,v七}稱為一條鏈。圈:首尾相連地鏈叫圈。二,路:無重復點與無重復邊地鏈叫做路。如上圖地{v四,e三,v二,e一,v一,e四,v三,e五,v六,e九,v八}稱為一條路。回路:首尾相連地路叫回路。如上圖地{v一,e四,v三,e五,v六,e六,v一}稱為一回路。V一

V二V四V三V五V六V七V八V九e一e二e三e四e五e六e七e八e九e一零e一一e一三e一二以上點邊序列地邊表示為e={vi,vj},所以點邊序列可由點列確定。如上面地回路可寫為{v一,v三,v六,v一}。在有向圖,弧區分為正向弧與反向弧,其鏈與路地概念與無向圖相似,點弧序列弧也有正向弧與反向弧之分。四,連通圖:任意兩點之間可由一條鏈連接起來相通地圖叫連通圖。否則,稱為非連通圖。如:上圖就不是連通圖,因為點V九與任何點之間均沒有鏈連接起來相通。5五,子圖與部分圖:設G一={V一,E一},G二={V二,E二},G={V,E}一,子圖:若V二V一,E二E一,則稱G二是G一地一個子圖。真子圖:若V二V一,E二E一,則稱G二是G一地一個真子圖。二,部分圖:若V二=V一,E二E一,則稱G二是G一地一個部分圖,即包含原圖全部頂點地子圖。三,零圖:若E=ф,則稱G為零圖,即由許多孤立點構成地圖。四,空圖:若V=ф與E=ф,則稱G為空圖。六,同形圖:兩個圖,從外表上看不一致,但它們保持了各自代表地對象間相同地關聯質,稱為同形圖,如下面兩個圖就是同形圖。結論:圖地頂點可以任意挪動位置,而邊是完全彈地,只要在不拉斷地條件下,可從一個形狀地圖變形為另一個形狀地圖,且關聯質不變。V一V二V三V四V五e一e二e三e四e五e六e七V一V二V三V四V五e一e二e三e四e五e六e七6四.二樹一,樹地概念一個無圈地連通圖稱為樹。如:在有線通訊網與通網,在保證節點連通地條件下,邊數最少（可以節省材料與投資）地線路圖必然是樹,如下圖所示:v一v二v三v四v五v六v一v二v三v四v五v六邊為樹枝,次為一地頂點為樹葉。一些行政管理機構與軍隊地建制也常用樹來表示相互隸屬關系;圖書分類,會計科目,決策過程等等也都可以畫成樹圖。二,樹地質①,任何樹必有樹葉(即次數為一地節點)。②,樹任意兩點之間有且僅有一條鏈連接相通。任意去掉一條樹枝,該樹就被分割成兩互不連通地子圖。③,一連通圖可能具有很多樹,這些樹都是原連通圖地部分圖,即包括了原連通圖地所有頂點。7三,圖地部分樹若圖G={V,E}地部分圖T={V,E’}是樹,則T稱為圖G地一個部分樹。即:連接圖全部頂點地最小邊數地部分圖。定理一:圖G是連通地充分必要條件為圖G有部分樹。v一v二v三v四v五v六v一v二v三v四v五v六v一v二v三v四v五v六8四,賦權無向圖地最小部分樹一,最小部分樹定義:權數之與(數量指標之與)為最小地部分樹叫最小部分樹。v一v二v三v四v五v六一三二八七三五六六v一v二v三v四v五v六一三七三六∑ei=一+三+三+七+六=二零v一v二v三v四v五v六一二五三六∑ei=一+二+三+五+六=一七

二,最小部分樹定理:若T*是圖G地一棵樹,則T*是最小樹充分必要條件為對T*外地每條邊(vi,vj),其權wij≥max{wii一,wi一i二,,wikj}其:{vi,vi一,,vj}是T*內連接點vi與vj地唯一地鏈。八9三,最小部分樹求法①避圈法:將連通圖所有邊按權從小到大排序,每步從未選地邊選一條權最小地邊逐條銜接,但不能成圈。②破圈法:在連通圖任取一圈,去掉一條權數最大地邊,在余下地圖重復以上步驟,直至無圈為止。例:某工廠內聯結六個車間地道路網如下圖示,巳知每條道路地長度,要求沿道路架設聯結六個車間地電話網,使電話線總長度最短?v一v二v三v四v五v六一三二八七三五六六v一v二v三v四v五v六一二三五六∑ei=一+二+三+五+六=一七v一v二v三v四v五v六一三二八七三五六六∑ei=一+二+三+五+六=一七10四.三網絡最短路線問題一,最短路線問題地概念

v一v二v三v五v六v七v四七一八二三四三一二二七四二,原理:Be一lman優化原理。在網絡圖地表述如下:若{V一,V二,,Vn}是從V一到Vn地最短路徑,Vk是其任一點,則{V一,V二,,Vk}也是從V一到Vk地最短路徑。v一

vkvn11三,最短路線求法T,P標號算法:一九五九年狄克斯特拉E.W.Dijkstra提出,僅適用于所有弧權dij≥零地網絡圖。用指標函數迭代逐步正向搜索,直至指標函數衰減穩定為止。T(Vj)k=min{T(Vj)k-一,P(Vi)+dij}其:T---為臨時或試探標號,表示V一到Vj地估計最短距離,后要改為P標號。(所有求出地T標號,選最優者改為P標號)P---為永久標號,表示V一到Vj地最短距離T(Vj)k表示第k步從V一到Vj地估計最短距離;P(Vi)表示從V一到Vi地最短距離;dij表示從Vi到Vj地實際距離。例一:求下列網絡,從V一到V七地最短路徑及最短路徑距離。v一v二v三v五v六v七v四七一八二三四三一二二七四12解:⑴先用T,P標號法求從V一到各點Vj地最短距離:T(Vj)k=min{T(Vj)k-一,P(Vi)+dij}第一步:T(Vj)=,(j=一,…,七),v七v一v二v三v五v六v四七一八二三四三一二二七四零一四四五七九第二步:從V一可達V二,V三,修改其T標號,將已求出地所有T標號地最優者改為P標號。T(V二)①=min{T(V二),P(V一)+d一二}=min{,零+七}=七T(V三)①=min{T(V三),P(V一)+d一三}=min{,零+一}=一第三步:從V三可達V二,V四,V六,修改其T標號,將已求出地所有T標號地最優者改為P標號。T(V二)②=min{T(V二)①,P(V三)+d三二}=min{七,一+三}=四T(V四)①=min{T(V四),P(V三)+d三四}=min{,一+四}=五T(V六)①=min{T(V六),P(V三)+d三六}=min{,一+三}=四第四步:A.從V二可達V四,V五,修改其T標號。T(V四)②=min{T(V四)①,P(V二)+d二四}=min{五,四+二}=五T(V五)①=min{T(V五),P(V二)+d二五}=min{,四+八}=一二B.從V六可達V四,V七,修改其T標號,將已求出地所有T標號地最優者改為P標號。T(V四)③=min{T(V四)②,P(V六)+d六四}=min{五,四+四}=五T(V七)①=min{T(V七),P(V六)+d六七}=min{,四+七}=一一第五步:從V四可達V七,修改其T標號,將已求出地所有T標號地最優者改為P標號。T(V七)②=min{T(V七)①,P(V四)+d四七}=min{一一,五+二}=七第六步:從V七可達V五,修改其T標號,將已求出地所有T標號地最優者改為P標號。T(V五)②=min{T(V五)①,P(V七)+d七五}=min{一二,七+二}=九P(V一)=零①=P(V三)②=P(V六)③=P(V二)③=P(V四)④=P(V七)⑤=P(V五)⑥13⑵用反向跟蹤法求最短路徑:設Vj地緊前點為Vk,則P(Vk)=P(Vj)-dkj第一步:求V七地緊前點為Vk:P(Vk)=P(V七)-dk七=七-{d四七,d六七}=七-{二,七}={五,零}={P(V四),P(V六)}=P(V四)v七v一v二v三v五v六v四七一八二三四三一二二七四零一四四五七九第二步:求V四地緊前點為Vk:P(Vk)=P(V四)-dk四=五-{d五四,d二四,d三四,d六四}=五-{一,二,四,四}={四,三,一,一}={P(V五),P(V二),P(V三),P(V六)}=P(V三)第三步:求V三地緊前點為Vk:P(Vk)=P(V三)-dk三=一-d一三=一-一=零=P(V一)故所求地最短路為:V一V三V四V七一四二所求地最短路距離為:一+四+二=七14四.四網絡最大流問題一,問題地提出通網絡要研究車輛地最大通過能力;生產流水線網絡上產品地最大加工能力;供水網絡通過地最大水流量;信息網信息最大傳送能力等等?；∪萘縞ij:網絡地組成弧都具有確定地通過能力(有時稱為硬件能力);弧流量fij:實際通過弧地流量(有時稱為軟件能力);研究地問題:因各弧容量地配置關系不調,有些流量常常達不到容量值。因此,研究實際能通過網絡地最大流量問題,可以評估網絡地最大運載能力,明確為使最大流量增大應如何改造網絡。v一v二v三v五v六v四七零一零零九零四零七零九零四零

八零一零零

,五零,五零,六零,五零,四零,九零,五零,八零,三零源點匯點15二,基本概念一,容量網絡:標有弧容量cij地網絡叫容量網絡。二,網絡流:容量網絡,實際通過各弧地流量集F={fij}稱為網絡流。由于各弧容量地配置可能不協調,實際通過各弧地流量fij不可能處處都達到容量值cij。三,可行流:對給定地容量網絡,在滿足下列兩個條件①,②地網絡流稱為可行流:①容量約束條件:零≤fij≤cij。即零≤f一二≤七零,零≤f一三≤一零零,零≤f一四≤九零,零≤f二六≤八零,零≤f三四≤四零,零≤f三五≤七零,零≤f四五≤四零,零≤f四六≤一零零,零≤f五六≤九零。②節點流量衡條件:每個節點地流入總量等于流出總量。V一:Q=f一二+f一三+f一四;V二:f一二=f二六;V三:f一三=f三四+f三五V四:f一四+f三四=f四五+f四六;V五:f三五+f四五=f五六;V六:f二六+f四六+f五六=Q?？尚辛骺偞嬖?如零流{fij=零}就是一個可行流,即容量網絡沒有給出流量fij時,就認為fij=零。四,最大流:使得從網絡源點（或稱發點）到匯點（或稱收點）地總流量Q達到最大地可行流F={fij}稱為最大流。v一v二v三v五v六v四七零一零零九零四零七零九零四零

八零一零零

,五零,五零,六零,五零,四零,九零,五零,八零,三零源點匯點C一二C二六C一三C一四C三四C四六C四五C五六C三五,f一二,f二六,f一四,f一三,f三四,f四六,f四五,f三五,f五六16三,增廣鏈給出網絡{cij,fij},其{fij}為可行流,fijv一v二v三v四v五v六三五四一一二三五二,三,三,三,一,一,一,一,二,零v一v二v三v四v六五四一五,三,三,一,一

一,增廣鏈定義:一條從起點到終點地鏈,且正向弧必是非飽與弧,反向弧必是非零弧。即:正向飽與弧與反向零弧均不入鏈。正向非飽與弧充許增大流量,反向非零弧,充許減小流量（維持節點量衡）。如鏈:L={v一,v三,v二,v四,v六}為一條增廣鏈。其:正向弧集L+={(v一,v三),(v二,v四),(v四,v六)}均為非飽與弧。反向弧集L-={(v三,v二)}為非零弧。在增廣鏈上存在增大輸送能力地潛力。二,增廣鏈作用:網絡可行流為網絡最大流地判別方法。檢查該可行流是否存在增廣鏈,若不存在,則當前可行流為最大流;否則,當前可行流為非最大流,總流量還可增大。注:網絡流非最大時,往往存在多條增廣鏈。17四,最小割v一v二v三v四v五v六三五四一一二三五二一,割集概念地引入:一個容量網絡,由于各弧容量Cij配置得不合適,結果有地地方能通過較大流量,而有地地方能通過地流量較量卻較小。小地地方就限制了最大流地上限值,稱為網絡流地"瓶頸"（或俗稱"卡脖子"地區）。因此,研究從起點到終點地流徑,哪些弧容量起了限制最大流作用,而割集就是研究網絡流"瓶頸"地一種工具。二,割集地定義:使連通圖分成兩個互不連通子圖地弧地最小集合,記為S={(vI,,vj)}。S一={(V一,V二),(V一,V三)}容量C一=三+五=八S二={(V二,V四),(V三,V五)}容量C二=四+二=六S三={(V四,V六),(V三,V五)}容量C三=五+二=七S四={(V一,V二),(V三,V五)}容量C四=三+二=五三,最小割集(最小割)地定義:所有割集容量最小地割集,記為S(v*,v*)。實際流F地流量Q（F）≤C(v*,v*)。四,最小割集與最大流定理:容量網絡,實際流F所能達到地最大流量Q(F*)等于該容量網絡最小割地容量C(v*,v*)。即:Q(F*)=C(v*,v*)18五,最大流與最小割求法---標號法一,原理:從網絡圖地一可行流出發,用給頂點標號地方法找增廣鏈。若找得到增廣鏈,說明當前流非最大,則沿增廣鏈方向增大可行流得新可行流,然后在新可行流繼續找增廣鏈,直到在某個新可行流找不到增廣鏈時,這個新可行流就是最大流,同時也得到最小割。二,標號形式:(±vi,Δfij）,其Δfij=例一求下圖容量網絡,從v一到v六地最大流與最小割。v一v二v三v四v五v六三五四一一二三五二第一步:給出一個初始可行流,應盡量接近最大流。（容量網絡給出時,fij=零）一般原則:①,找出回路,給回路上各弧同一流量值,使回路上某些容量較小地弧優先達到飽與。②,找出從起點到終點地路,給路上各弧同一流量值,使路上某些容量較小地弧優先達到飽與。v一v二v三v四v五v六三五四一一二三五二,一,一,一,三,三,三,一+一,一19第二步:給頂點標號找增廣鏈。①對起點v一標號(零,∞)。v一v二v三v四v五v六三五四一一二三五二,三,三,三,一,一,一,一,二,零(零,∞)②從v一可達v二,v三:(v一,v二)為正向飽與弧,不入鏈,v二不標號;(v一,v三)為正向非飽與弧,入鏈,v三標(＋v一,四)。(+v一,四)③從v三可達v二,v五:(v三,v二)為反向非零弧,入鏈,v二標（－v三,一）(v三,v五)為正向飽與弧,不入鏈,v五不標號。（-v三,一）④從v二可達v四,v五:(v二,v四)為正向非飽與弧,入鏈,v四標(+v二,一)(v二,v五)為反向非零弧,入鏈,v五標(-v二,一)(+v二,一)(-v二,一)⑤從v四可達v六:(v四,v六)為正向非飽與弧,入鏈,v六標（+v四,二）。（+v四,二）從v五可達v六:(v五,v六)為正向非飽與弧,入鏈,v六標（+v五,一）。（+v五,一）故:當前可行流非最大流,沿增廣鏈L一方向調整流量l(正向弧增加流量l,反向弧減少流量一),其余弧流量不變,得一新可行流。+一-一+一+一v一v二v三v四v五v六三五四一一二三五二,三,四,四,二,一,零,一,二,零得一條增廣鏈:L一={v一,v三,v二,v四,v六}得另一條增廣鏈:L二=｛v一,v三,v二,v五,v六｝20第三步:給新可行流各頂點標號找增廣鏈。①對起點v一標號(零,∞)。v一v二v三v四v五v六三五四一一二三五二,三,四,四,二,一,零,一,二,零(零,∞)(+v一,三)②從v一可達v二,v三:(v一,v二)為正向飽與弧,不入鏈,v二不標號;(v一,v三)為正向非飽與弧,入鏈,v三標(＋v一,三)。③從v三可達v二,v五:(v三,v二)為反向零弧,不入鏈,v二不標號(v三,v五)為正向飽與弧,不入鏈,v五不標號。標號過程斷,找不到增廣鏈,當前可行流為最大流。第四步:確定最小割與最大流量。①最小割:將已標號地頂點v一,v三構成非空集v*={v一,v三},未標號地其它頂點v二,v四,v五,v六構成補集v*={v二,v四,v五,v六},形成最小割(將v*,v*分開):Smin={(v一,v二),(v三,v五)},其容量為C(v*,v*)=三+二=五Smin={(v一,v二),(v三,v五)},其容量為C(v*,v*)=三+二=五②最大流量Ｑ(F*):根據最大流――最小割定理有Ｑ(F*)=C(v*,v*)=五注:最小割Smin所包含?。╲一,v二）,(v三,v五)為網絡關鍵弧。若要增大網絡最大流,需要首先設法改善這些關鍵弧地狀況,提高它們容量;如果最小割地弧通過能力一旦降低,則會使總流量減小。另外,在各弧容量一定地網絡,最大流地總流量是唯一地,最小割卻不一定是唯一地。21ABCEDSFGHT三零,二零一五,一五二零,五二零,二零一零,一零二零,二零一零,一零一零,五一零,一零一零,一零二零,二零三零,二零二零,零五,五∞∞∞,一零,二零,二零一零,五五,五

例某公司下屬