定義4961.doc

定義4961 ，定義4961。
歡迎下載！
網(wǎng)絡 定義4.9.61無自回路的有向賦權圖G=(V,E)稱為網(wǎng)絡(network) 定義4.9.62在網(wǎng)絡中，有向邊(u,v )上的權稱為容量(capacity),j記為C(u,v).網(wǎng)絡中沒有引入邊的結點(即該結點的入 度為0)稱為源(Source),用字母s表示,沒有引出邊的結點(即該結點的出度為0)稱為 匯(Trap),用字母t表示 一.運輸網(wǎng)絡 定義4.9.6-3具有擔擱源和單個匯的網(wǎng)絡稱為運輸網(wǎng)絡(TransportNetwork). 運輸網(wǎng)絡的實際意義可以用公路系統(tǒng),鐵路系統(tǒng)或洪水系統(tǒng),供電系統(tǒng)等來說 明,也就是 “貨物從產(chǎn)地s,通過許多中轉地,到目的地t”這類情況的一般模型,這里將源看成產(chǎn) 地,將匯看成目的地,將其他結點看成中轉站,有向邊可以看成連接兩站的道路,容 量則是一段道路允許的通行能力的上限.下圖即是一個例子: 在運輸網(wǎng)絡中要考慮的問題是從源到匯的實際流通量,顯然它和每條有向邊的容 量有關,也和每個結點的轉運能力有關.為此,除了容量之外,還對每條有向邊(vi,vj) 賦予一個稱為流(flow)的非負實數(shù)Φ(vi,vj). Φ是網(wǎng)絡中有向邊集到非負實數(shù)的一個函數(shù),稱為流函數(shù)(Flow Function),它滿足下列條件的:1.對每條有向邊(u,v),有Φ(u,v)<=C(u,v); 2.除源和匯以外,對每個結點v,滿足 ∑Φ(u,v)=∑Φ(v,u) (u,v)∈E(v,u)∈E 3.對于源和匯,滿足∑Φ(u,v)=∑Φ(v,t) (s,u)∈E(v,t)∈E 對運輸貨物來講,條件1的意思是每條道路的流通能力不能超過道路的承受能力, 條件2的意思是每個中轉站都保持出入平衡,即流入量等于流出量,條件3的意思 是源的流出量W等于匯的總流入量, W稱為網(wǎng)絡的流量(Discharge).很明顯,它是現(xiàn)實問題的一個理想數(shù)學模型.圖(b )給出了(a)中運輸網(wǎng)絡的一個流. 由Φ的三個條件容易導出: W=