【正文】 前向弧 ：鏈上與鏈方向相同的弧。 反向弧 ：鏈上與鏈方向相反的弧。 可增流鏈 ：若一條鏈中的每條前向?。?vi,vj）都有 xij cij,每條反向?。?vk,vl）都有 xkl0 ，則稱這樣的鏈為該可行流的可增流鏈。 167。 流分析（ 4） 標(biāo)號(hào)法求最大流的基本步驟 ： 第一步： 標(biāo)號(hào)與檢查 。 首先發(fā)點(diǎn)標(biāo)號(hào)（ 0， +∞ ），但未檢查，其余都是未標(biāo)號(hào)點(diǎn)。 （ 1）若所有已標(biāo)號(hào)點(diǎn)都已被檢查，而收點(diǎn)沒(méi)有得到標(biāo)號(hào)，則進(jìn)行第三步； （ 2）找一個(gè)標(biāo)號(hào)未檢查的頂點(diǎn) vi進(jìn)行檢查： 對(duì)?。?vi,vj） ,若 xij?c ij，且 vj未標(biāo)號(hào)，則給 vj一個(gè)標(biāo)號(hào)（ +vi,δ j),其中 δ j= min{cij – xij,δ i} 對(duì)?。?vj,vi） ,若 xji0，且 vj未標(biāo)號(hào)，則給 vj一個(gè)標(biāo)號(hào)（ vi,δ j), 其中 δ j= min{xji,δ i} （ 3）如果收點(diǎn)已得到標(biāo)號(hào)，則進(jìn)行第二步；否則返回（ 1）。 167。 流分析（ 5） 標(biāo)號(hào)法求最大流的基本步驟 ： 第二步： 增流 。 （ 1）此時(shí)，收點(diǎn) vt已得到標(biāo)號(hào)，從 vt逆向追蹤找出可增流鏈 P。 （ 2）按下述關(guān)系調(diào)整網(wǎng)絡(luò)中的可行流： （ 3）去掉圖中所有標(biāo)號(hào)，對(duì)可行流 {xij′ }重新進(jìn)行第一步。 第三步： 當(dāng)標(biāo)號(hào)無(wú)法進(jìn)行下去，收點(diǎn) vt無(wú)標(biāo)號(hào)時(shí)，這時(shí)的可行流已是最大流，最大值 ? ?? ??????????其他弧的反向弧是的前向弧是,,ijjitijjitijijxPvvxPvvxx ????jsjxH*167。 流分析（ 6） 例：求下圖所示網(wǎng)絡(luò)的最大流。 解： （一）標(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。 流分析（ 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。 流分析（ 8） 檢查 V4，在弧（ v4， vt）上， X4t=0， C4t=2， X4tC4t，給 vt標(biāo)號(hào) (4， δ t），其中， δ t= min{C4tX4t,δ 4}= min{2, 2}=2， vt得到標(biāo)號(hào)， 標(biāo)號(hào)過(guò)程結(jié)束。 167。 流分析（ 9） （二）調(diào)整過(guò)程 ： 從 vt開(kāi)始逆向跟蹤，找到可增流鏈（ vs,v2,v4,vt）。 根據(jù) δ t= 2調(diào)整可行流，得到新的可行流 f′ 如下圖。 167。 流分析（ 10） 去掉各點(diǎn)標(biāo)號(hào)，從 vs開(kāi)始，重新標(biāo)號(hào)。 167。 流分析（ 11） vt又得到標(biāo)號(hào)，標(biāo)號(hào)過(guò)程結(jié)束。從 vt開(kāi)始逆向跟蹤，找到可增流鏈（ vs,v1,v3,vt）。根據(jù) δ t= 3調(diào)整可行流，得到新的可行流 f′ 如下圖。 去掉各點(diǎn)標(biāo)號(hào)，從 vs開(kāi)始，重新標(biāo)號(hào)。 vt又得到標(biāo)號(hào)，標(biāo)號(hào)過(guò)程結(jié)束。從 vt開(kāi)始逆向跟蹤，找到可增流鏈（ vs,v2,v1,v3,vt）。根據(jù) δ t= 1調(diào)整可行流，得到新的可行流 f′ 如下圖。 167。 流分析（ 13） 去掉各點(diǎn)標(biāo)號(hào)，從 vs開(kāi)始，重新標(biāo)號(hào)。 標(biāo)號(hào)至點(diǎn) v2：標(biāo)號(hào)過(guò)程無(wú)法進(jìn)行，所以 f 39。即為最大流。 （三）最大值 ： 633* ???? ?jsjxH167。 流分析（ 14） 二、最小費(fèi)用最大流問(wèn)題 最小費(fèi)用最大流 ： 在最大流集合中尋找一個(gè)費(fèi)用最小的最大流。設(shè)一個(gè)網(wǎng)絡(luò) G（ V， E， C， A）， cij表示?。?vi,vj）上的容量， aij表示?。? vi,vj ）上的輸送單位流量所需的費(fèi)用。 最小費(fèi)用最大流問(wèn)題就是 其中， X*為 G的最大流的集合。 最小費(fèi)用最大流的基本思想 ： 從初始可行流（一般取零流）開(kāi)始，在每次迭代過(guò)程中對(duì)每條弧賦予與 cij， aij， xij有關(guān)的權(quán)構(gòu)成一個(gè)有向賦權(quán)圖，再用求最短路徑的方法確定費(fèi)用最小的可增流鏈，沿著該鏈增加流量得到相應(yīng)新的可行流，重復(fù)上述過(guò)程，直至求得最大流。 ? ? ? ?? ?? ? Evv ijijXx jiij xa,m in167。 流分析（ 15） 權(quán)數(shù)的構(gòu)造方法： 對(duì)任意?。?vi,vj）有流 {xij},弧上的流量可增加（ xijcij），也可能減少（ xji0），因此，每條邊賦予前向費(fèi)用權(quán)ω ij+與反向費(fèi)用權(quán) ω ij 這樣構(gòu)成了有向賦權(quán)圖 G（ V， E， W）。 每條弧 前向可增流量 及 反向可增流量 分別為 ???????????ijijijijijij cxcxa若若,? ????????????0,0,ijijijij xxa若若???????????ijijijijijijij cxcxxc若若,0,??????????0,00,ijijijij xxx若若?167。 流分析（ 16） 最小費(fèi)用最大流的算法步驟： （ 1）從零流開(kāi)始， {xij}={0}； （ 2）賦權(quán)； （ 3）確定 vs到 vt的最短路徑（可增流鏈） P（ vs,vt） = {(vs,vij),… ， (vjk,vt)} 若路長(zhǎng)為 +∞ ，結(jié)束，當(dāng)前流已是最小費(fèi)用最大流，否則轉(zhuǎn)（ 4）； （ 4）沿最短路徑確定最大可增流量 δ= min{δ si1,… ,δ sit} δ ij取 δ ij+還是 δ ij取決于（ vi,vj）在 P中是前向弧還是反向??； （ 5）調(diào)整 然后轉(zhuǎn)（ 2）。算法結(jié)束。 ? ?? ??????????其他弧的反向弧是的前向弧是,,ijjitijjitijijxPvvxPvvxx ??? 小結(jié)與習(xí)題 基本概念 ： 網(wǎng)絡(luò)，網(wǎng)絡(luò)分析，資源，資源需求量，阻礙強(qiáng)度，鏈，結(jié)點(diǎn)，站點(diǎn)，中心，障礙，拐角，權(quán)值，概念數(shù)據(jù)模型，邏輯數(shù)據(jù)模型，物理數(shù)據(jù)模型，路徑分析，最佳分析，最短路徑，資源定位，資源分配，流優(yōu)化 基本內(nèi)容 ： 圖論基礎(chǔ)，最短路徑分析，最佳路徑分析，資源分配，流分析 重點(diǎn)難點(diǎn) ： Dijkstra分析，標(biāo)號(hào)法 作業(yè) ： 地理網(wǎng)絡(luò)模型有哪幾種？分別簡(jiǎn)述其概念。 按照網(wǎng)絡(luò)特征，最短路徑是如何分類的？ Floyd算法的基本思想是什么？ 資源分配主要研究哪些問(wèn)題？ ? 小結(jié)與習(xí)題 按 Dijkstra算法求解右圖所示的最短路徑。 求下圖所示網(wǎng)絡(luò)的最大流。