【正文】 慮路徑（ vi,v1,vj）是否存在。 167。 ? ? ? ? ijPEe cPC ?? m in 結(jié)論：最佳路徑本質(zhì)上是通過(guò)定義在每條弧上的權(quán)值來(lái)定義的。 資源分配（ 3） 二、 資源分配目標(biāo)方程 若資源分配要求供應(yīng)點(diǎn)與需求點(diǎn)之間總的加權(quán)距離為最小，則相應(yīng)的目標(biāo)方程是 若要求距離最小時(shí)，目標(biāo)方程是 若要求所有的需求點(diǎn)在一給定的服務(wù)半徑 s內(nèi)，則目標(biāo)方程是 其中 ? ?? ??nimjijid1 1min??????????? sdsddcijijijiij ,?? ?? ??nimjijd1 1m in? ?? ??nimjijc1 1m in167。 啟發(fā)式方法的 局限性 ： （ 1）并不保證全局的最佳結(jié)果，但非常接近； （ 2）并不平衡供應(yīng)點(diǎn)間的負(fù)擔(dān)； （ 3）并不限制供應(yīng)點(diǎn)的容量； （ 4）初始點(diǎn)集的不同會(huì)影響最終結(jié)果。 反向弧 ：鏈上與鏈方向相反的弧。 流分析（ 9） （二）調(diào)整過(guò)程 ： 從 vt開(kāi)始逆向跟蹤，找到可增流鏈（ vs,v2,v4,vt）。 （三）最大值 ： 633* ???? ?jsjxH167。 求下圖所示網(wǎng)絡(luò)的最大流。 167。 解： （一）標(biāo)號(hào)過(guò)程： 給 Vs標(biāo)上（ 0， +∞ ）； 檢查 Vs，在?。?vs， v1）上， Xs1=0， Cs1=3， Xs1Cs1，給 v1標(biāo)號(hào) (s， δ 1），其中， δ 1= min{Cs1Xs1,δ s}= min{3, +∞}=3 同理，給 v2標(biāo)號(hào) (s， δ 2）， 其中， δ 2= min{Cs2Xs2,δ s}= min{5, +∞}=5 167。 ? ?????????????ijiijtiHtsisiHxx,0,? ????????????????????????ijijijiijcxtiHtsisiHxxH0,0,m a x最大流問(wèn)題的優(yōu)化模型： 167。 （ 3） 供應(yīng)點(diǎn)區(qū)域性調(diào)整 ： （ 4） 重復(fù)第 2步和第 3步直到兩步都無(wú)新的替換為止 。 資源分配（ 2） 資源分配的數(shù)學(xué)模型： 設(shè)有 n個(gè)需求點(diǎn) Pi（ xi,yi）， bi是每個(gè)需求點(diǎn)的需求量（ i=1,2,… ,n） , m個(gè)供應(yīng)點(diǎn) Q j（ uj,vj） （ j=1,2,… ,m） 。 最大容量路徑 設(shè) G＝ V,E是一個(gè)非空的簡(jiǎn)單有限圖。 A*算法 A*算法的基本步驟 ： 兩個(gè)鏈表： T表示已經(jīng)生成但尚未擴(kuò)展的結(jié)點(diǎn)集合； S表示已經(jīng)擴(kuò)展的結(jié)點(diǎn)集合。于是，算法停止。其他點(diǎn)： ds=∞,p s=?。 最佳路徑 ： 是滿足某種最優(yōu)化條件的一條路徑。 站的屬性主要有兩種：資源需求量和阻礙強(qiáng)度。 網(wǎng)絡(luò)分析的基本研究對(duì)象 ：線狀目標(biāo)。 圖論基礎(chǔ)（ 13） 出度和入度 出度 :有向圖 D中從頂點(diǎn) v為起點(diǎn)的弧的數(shù)目叫做 v的出度，記作 。令邊是僅有一端為 U1中頂點(diǎn)的各條邊的最短邊，則在包含 中 中所有邊的生成樹(shù)中，必存在含 et=(vi,vj)的最小生成樹(shù)。 求一個(gè)連通圖 G的生成樹(shù)的主要方法有： 避回路法 ： 任取圖 G的一條邊 e1，再取一條邊 e2 ， e2和 e1不構(gòu)成回路；然后再取一條邊 e3 ， e3和 e1 e2不構(gòu)成回路。 圖論基礎(chǔ)（ 6） 二、樹(shù) 基本概念 樹(shù) :一個(gè)連通的無(wú)回路的圖。用Ｃ n記由一條有n個(gè)頂點(diǎn)的回路構(gòu)成的一個(gè)圖。 圖論基礎(chǔ)（ 3） 頂點(diǎn)的度 :G的頂點(diǎn) v的度 d(v)是指 G中與 v關(guān)聯(lián)的邊的數(shù)目，每個(gè)環(huán)算作兩條邊。 圖論基礎(chǔ)（ 1） 一、圖 圖的概念 圖 :一個(gè)圖 G是指一個(gè)有序三元組（ V（ G）， E（ G）， Ψ G），其中 V（ G）是非空的頂點(diǎn)集， E（ G）是邊集， Ψ G是關(guān)連函數(shù)，它使 G的每條邊對(duì)應(yīng)于 G的無(wú)序頂點(diǎn)對(duì)（不必相異）。 邊 :E中的每個(gè)頂點(diǎn)對(duì)（ u,v）稱為 G的邊，記為 e =（ u,v）或簡(jiǎn)記為 e = uv，稱 u，v是邊 e的 端點(diǎn) ，且稱 u和 v是 鄰接的頂點(diǎn) 。 設(shè) G是一個(gè)（ p,q）圖，那么 G的各個(gè)頂點(diǎn)度的和是邊數(shù)的二倍，即 正則圖 ：如果圖 G的所有頂點(diǎn)的度均相等，則稱為正則的。若 n為奇數(shù)，則Ｃ n稱為奇回路，若 n為偶數(shù)，則Ｃ n稱為偶回路。 林 :每個(gè)支都是樹(shù)的分離圖稱為林。如此下去，最后得到的不含回路的連通生成子圖就是 G的一棵生成樹(shù)。 ? ? ? ?? ?0,},{ ??? lll ewEeewW其中，? ? ? ? min?? ?? Tt Ee tewTW?kjjET1??167。 入度 :有向圖 D中從頂點(diǎn) v為終點(diǎn)的弧的數(shù)目叫做 v的入度，記作 。 網(wǎng)絡(luò)分析的主要研究?jī)?nèi)容 ：最短路徑分析、資源分配、連通分析、流分析等。 中心 ：網(wǎng)絡(luò)中具有一定的容量，能夠從鏈上獲取資源的結(jié)點(diǎn)所在地。 設(shè) P為 G中兩點(diǎn)間的一條有向路徑，定義 P的權(quán)值 則 G中兩點(diǎn)間權(quán)最小的有向路徑稱為這 兩點(diǎn)的最佳路徑 。將起源點(diǎn) s標(biāo)號(hào)，記 k=s，其他點(diǎn)尚未處理； （ 2）距離計(jì)算。 反向追蹤，可得 v0到 vi的最短路徑。 （ 1）設(shè)置初值； （ 2）從 T中選出具有最小 f*值的結(jié)點(diǎn) v，即令v=min{fu*}。對(duì)于任何 e＝(vi,vj)∈E ， cij為邊 (vi,vj)的容量。 tij和 dij分別是供應(yīng)點(diǎn) Qj對(duì)需求點(diǎn) Pi提供的供應(yīng)量和兩點(diǎn)間的距離。 167。 流分析（ 3） 二、最大流解法 —— 標(biāo)號(hào)法 標(biāo)號(hào)法的基本思想 ：給初始可行流 f取零流，表示網(wǎng)絡(luò)開(kāi)始不運(yùn)輸任何資源；然后在滿足條件的情況下，逐漸增加流量，直到無(wú)法增加流量為止，這時(shí)的可行流便是最大流。 流分析（ 7） 檢查 V1，在?。?v1， v3）上， X13=0， C13=4， X13C13，給 v3標(biāo)號(hào) (1， δ 3），其中， δ 3= min{C13X13,δ 1}= min{4, 3}=3 檢查 V2，同理，給 v4標(biāo)號(hào) (2， δ 4）， 其中， δ 4= min{C24X24,δ 2}= min{2,5}=2 167。 流分析（ 13） 去掉各點(diǎn)標(biāo)號(hào)，從 vs開(kāi)始，重新標(biāo)號(hào)。 。即為最大流。 167。 前向弧 ：鏈上與鏈方向相同的弧。 （ 4） 重復(fù)第 2步和第 3步直到兩步都無(wú)新的替換為止 。,2,1, jkmkddbt ikijiij?????其他情況供給受,0,1 jiijQPX167。 例： 如圖表示從 V1到 V2的兩條路徑，每條邊上的數(shù)字表示容量。 （ 4）根據(jù)回溯的方法輸出起始結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的最優(yōu)路徑，以及最短距離 gv。 Floyd算法 Floyd算法是一個(gè) 求圖中所有結(jié)點(diǎn)間 最短路徑的算法 ，可解決權(quán)值為負(fù)的情況。從上述結(jié)點(diǎn)集中，選取 dj最小所對(duì)應(yīng)的點(diǎn)為最短路徑中的