Lecture9

GraphandNetworkAnalysisSchoolofBusinessAdministrationHunanUniversityLecturer:E-mail:

LectureOutlineBasicConceptsofGraphTreesandMinimumSpanningTreeTheShortest-PathProblemTheMaximumFlowProblemTheMinimumCostFlowProblem哥尼斯堡七橋問題一筆畫問題歐拉

(E.Euler)0.IntroductionEADCB1.BasicConceptsofGraphGraphComponentandRepresentationAgraphismadeupof

vertices,

nodes,or

points

whichareconnectedby

edges,

arcs,orlines.v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10Forexample一個(gè)圖G是由點(diǎn)集V={vj}和V

中元素的無序?qū)Φ囊粋€(gè)集合E={ek}構(gòu)成的二元組，記為G

=(V,

E)，其中V中的元素vj

叫做頂點(diǎn),V

表示圖G

的點(diǎn)集合；E

中的ek

元素叫做邊，E

表示圖G

的邊集合。v4v6v1v2v3v5V={v1,v2,v3,v4,v5,v6}，A={(v1,v3),(v2,v1),(v2,v3),(v2,v5),(v3,v5),(v4,v5),(v5,v4),(v5,v6)}UndirectedandDirectedGraph無向圖:由頂點(diǎn)和邊所構(gòu)成，G=(V,E)有向圖:由頂點(diǎn)和弧所構(gòu)成，D=(V,A)SimpleGraph&CompleteGraph環(huán)(loop):若某條邊的兩個(gè)端點(diǎn)是相同。多重邊(multipleedges):若兩個(gè)端點(diǎn)之間有兩條以上的邊。簡單圖(simplegraph)：無環(huán)也無多重邊的圖。多重圖(multigraph):

一個(gè)無環(huán)但有多重邊的圖。完全圖(completegraph):每一對頂點(diǎn)間恰有一條邊相連的無向簡單圖。有向完全圖(directedcompletegraph):則是指任意兩個(gè)頂點(diǎn)之間有且僅有一條有向邊的簡單圖。v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10以點(diǎn)v為端點(diǎn)的邊的個(gè)數(shù)稱為點(diǎn)v

的度(次)，記作deg(v)或

d(v)度為零的點(diǎn)稱為孤立點(diǎn)，度為1的點(diǎn)稱為懸掛點(diǎn)。懸掛點(diǎn)的關(guān)聯(lián)邊稱為懸掛邊。度為奇數(shù)的點(diǎn)稱為奇點(diǎn)，度為偶數(shù)的點(diǎn)稱為偶點(diǎn)。v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10d(v1)=？d(v2)=？TheDegreeofaVertex43定理1

所有頂點(diǎn)度數(shù)之和等于所有邊數(shù)的2倍。所有頂點(diǎn)的入次之和等于所有頂點(diǎn)的出次之和。有向圖中,以vi為始點(diǎn)的邊數(shù)稱為點(diǎn)vi的出次,用d

+(vi)表示；以vi為終點(diǎn)的邊數(shù)稱為點(diǎn)vi的入次，用d

-(vi)表示；vi點(diǎn)的出次和入次之和就是該點(diǎn)的次。定理2

在任一圖中，奇點(diǎn)的個(gè)數(shù)必為偶數(shù)。TheRelationshipbetweenDegreesandEdges設(shè)G1=(V1,E1),G2=(V2,E2),若

V2

V1

,

E2

E1

,則稱G2

是G1的子圖；若V2=V1

,

E2

E1

則稱G2

是G1

的部分圖或支撐子圖。v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10e11(a)G1e5e7v1v2v5v6v7e1e6e8(b)子圖v1v2v3v4v5v6v7e1e6e7e9e10e11(c)支撐子圖SubgraphandSpanningsubgraphNetwork

給定一個(gè)圖G=(V,E)或有向圖D=(V,A),在V中指定兩個(gè)點(diǎn),一個(gè)稱為始點(diǎn)(或發(fā)點(diǎn)),記作vi,一個(gè)稱為終點(diǎn)(或收點(diǎn)),記作vn

,其余的點(diǎn)稱為中間點(diǎn)。對每一條(vi,vj)

A

或E

,對應(yīng)一個(gè)數(shù)wij

,稱為弧上的“權(quán)”。通常把這種賦權(quán)的圖稱為網(wǎng)絡(luò)。由兩兩相鄰的點(diǎn)及其相關(guān)聯(lián)的邊構(gòu)成的點(diǎn)邊序列稱為鏈。

如:v1,e1,v2,e4,v4,記作(v1,v2,v4)

Linke3v1v2v3v4v5v6e7e8e1e2e4e5e6e9e10e3v1v2v3v4v5v6e7e8e1e2e4e5e6e9e10CycleandConnectedGraph若鏈(v1,v2,…,vn)，有v1=vn，則稱之為圈若鏈中所含的點(diǎn)均不相同則稱為初等鏈若圖中任意兩點(diǎn)之間均至少有一條鏈，則稱此圖為連通圖，否則稱為不連通圖。v1v2v3v4v5v62.TreesandMinimumSpanningTree樹(Tree):一個(gè)連通的無圈的無向圖，T=(V,E)。樹中次為1的點(diǎn)稱為樹葉，次大于1的點(diǎn)稱為分支點(diǎn)。v1v2v3v4v5v6

TheCharacteristicsofaTreen

個(gè)頂點(diǎn)的樹必有n-1

條邊。樹中任意兩個(gè)頂點(diǎn)之間，恰有且僅有一條鏈（初等鏈）。樹連通，但去掉任一條邊，必變?yōu)椴贿B通。樹無回路（圈），但不相鄰的兩個(gè)點(diǎn)之間加一條邊，恰得到一個(gè)回路（圈）。v1v2v3v4v5v1v2v3v4v5設(shè)連通圖T=(V,E’)是圖G=(V,E)的一支撐子圖，如果圖T=(V,E’)是一個(gè)樹,那么稱T是G的一個(gè)生成樹(支撐樹)，或簡稱為圖G的樹。SpanningTree如果圖T=(V,E’)是圖G的一個(gè)生成樹，那么稱E’上所有邊的權(quán)的和為生成樹T的權(quán)，記作S(T)。如果圖G的生成樹T*的權(quán)S(T*)，在G的所有生成樹T中的權(quán)最小，即那么稱T*是G的最小生成樹。MinimumSpanningTreeTheApplicationofMST某六個(gè)城市之間的道路網(wǎng)如圖所示，要求沿著已知長度的道路聯(lián)結(jié)六個(gè)城市的電話線網(wǎng)，使電話線的總長度最短。v1v2v3v4v5v66515723445v1v2v3v4v5v612344AlgorithmfortheMinimumSpanningTreeProblem避圈法（Kruskal,1956)將所有邊按權(quán)值從小到大排序，每次從未選的邊中選一條權(quán)最小的，逐步銜接，但不接成圈破圈法（管梅谷,1975）任取一個(gè)圈，從中去掉權(quán)最大的邊。在余下的圖重復(fù)該步驟，直到不含圈為止例：避圈法v1v21v32v412v5v1v2v3v4v514231352例：破圈法最短路問題描述：設(shè)G=(V,E)為連通圖,圖中各邊(vi

,vj)的權(quán)為wij

(wij=+∞表示vi

,vj之間沒有邊),vs

,vt為圖中任意兩點(diǎn)，求一條路P0，使它為從vs到vt的所有路P中總權(quán)最小。3.TheShortest-PathProblem則稱P0為從vs到vt的最短路。實(shí)際應(yīng)用：管道鋪設(shè)、線路安排、廠區(qū)平面布局、設(shè)備更新等?；舅枷耄簭氖键c(diǎn)出發(fā)，逐步地向外探尋最短路。執(zhí)行過程中給每個(gè)點(diǎn)標(biāo)號，其中固定標(biāo)號P表示從始點(diǎn)到該點(diǎn)的最短通路長度，臨時(shí)標(biāo)號T表示從始點(diǎn)到該點(diǎn)的最短通路長度上界，方法的每一步都把某個(gè)點(diǎn)的T標(biāo)號修改為P標(biāo)號，這樣一旦終點(diǎn)得到P標(biāo)號，算法終止。狄杰斯特拉(Dijkstra)算法適用于不含負(fù)權(quán)的網(wǎng)絡(luò)。(1)

給始點(diǎn)vs以P標(biāo)號P(vs)=0,表示從vs到

vs的最短距離為0,其余節(jié)點(diǎn)均給T標(biāo)號,T(vi)=+∞(i=2,3,…,n)

;(2)

設(shè)節(jié)點(diǎn)vi

為剛得到P標(biāo)號的點(diǎn),考慮點(diǎn)vj，其中(vi,vj)

E,且vj為T標(biāo)號。對vj的T標(biāo)號進(jìn)行如下修改：T(vj)=min{T(vj),P(vi)+wij}(3)

比較所有具有T標(biāo)號的節(jié)點(diǎn),把最小者改為P標(biāo)號,即：

P(vk)=min{T(vi)}當(dāng)存在兩個(gè)以上最小者時(shí)，可同時(shí)改為P標(biāo)號。若全部節(jié)點(diǎn)均為P標(biāo)號，則停止，否則用vk代替vi，返回步驟(2)。狄杰斯特拉(Dijkstra)算法例、用Dijkstra算法求下圖從v1到v6的最短路。v1v2v3v4v6v5352242421

解（1）首先給v1以P標(biāo)號，給其余所有點(diǎn)T標(biāo)號。（2）（3）（4）v1v2v3v4v6v5352242421（5）（6）（7）（8）（9）（10）反向追蹤得v1到v6的最短路為：首先設(shè)任一點(diǎn)vi到任一點(diǎn)vj都有一條弧，該如果不在原網(wǎng)絡(luò)中,即(vi,vj)

A，則令wij=+∞)

。顯然，從v1到vj的最短路是從v1出發(fā)，沿著這條路到某個(gè)點(diǎn)vi再沿弧(vi,vj)到vj，則v1到vi的這條路必然也是v1到vi的所有路中的最短路。設(shè)P1j表示從v1到vj的最短路長，P1i表示從v1到vi的最短路長，必滿足下列方程：

Warshall-Floyd算法求解步驟第1步，令

即用v1到vj的直接距離做初始解。第2步，使用遞推公式：求，當(dāng)進(jìn)行到第t步，若出現(xiàn)停止計(jì)算，即為v1到各點(diǎn)的最短路長。第3步，逆向追蹤得到從v1到vj的最短路徑例

－18v1v2v3v4v5－26－3－5－1－3－521－1211v6v7v837求圖中v1到各點(diǎn)的最短路第1步，P11(1)=0,P12(1)=-1,P13(1)=-2,P14(1)=3,P15(1)=+∞,P16(1)=+∞,P17(1)=+∞,P18(1)=+∞;第2步，利用遞推公式P11(2)=min[0+0,-1+6,-2+∞,3+8,∞+∞,∞+∞,∞+∞,∞+∞]=0P12(2)=min[0+(-1),-1+0,-2+(-3),3+∞,∞-1,∞+∞,∞+∞,∞+∞]=-5P13(2)=min[0+(-2),-1+∞,-2+0,3+∞,∞+∞,∞+∞,∞+∞,∞+∞]=-2P14(2)=min[0+3,-1+∞,-2+(-5),3+0,∞+∞,∞+∞,∞-1,∞+∞]=-7P15(2)=min[0+∞,-1+2,-2+∞,3+∞,∞+0,∞+1,∞+∞,∞-3]=1

－18v1v2v3v4v5－26－3－5－1－3－521－1211v6v7v837v1v2v3v4v5v6v7v8P(1)P(2)P(3)P(4)v10-1-23

∞∞∞∞0000v260∞

∞

2∞∞∞-1-5-5-5v3∞

-30-5

∞1∞∞-2-2-2-2v48∞

∞0

∞∞2∞3-7-7-7v5∞

-1

∞∞

0∞∞

∞∞

1-3-3v6∞

∞

∞∞

1017∞

-1-1-1v7∞

∞

∞-1

∞∞0

∞∞

5-5-5v8∞

∞∞∞-3∞-50∞

∞

66第3步，逆向追蹤得從v1到v8的最短路是(v1,v3,v6,v8),長度為6。第2步遞推計(jì)算最短路問題的應(yīng)用案例設(shè)備更新問題

某企業(yè)使用一臺(tái)設(shè)備，在每年年初，企業(yè)領(lǐng)導(dǎo)部門就要決定是購置新的，還是繼續(xù)使用舊的。若購置新設(shè)備，就要支付一定的購置費(fèi)用；若繼續(xù)使用舊設(shè)備，則需支付一定的維修費(fèi)用?，F(xiàn)在的問題是如何制定一個(gè)五年之內(nèi)的設(shè)備更新計(jì)劃，使得總的支付費(fèi)用最少。若已知該種設(shè)備在各年年初的價(jià)格及其維修費(fèi)用如下。第i年度12345購置費(fèi)1111121213設(shè)備役齡0-11-22-33-44-5維修費(fèi)用5681118例求：5年內(nèi)，哪些年初購置新設(shè)備，使5年內(nèi)的總費(fèi)用最小。解：（1）分析：可行的購置方案（更新計(jì)劃）是很多的，如：1）每年購置一臺(tái)新的，則對應(yīng)的費(fèi)用為：

11+11+12+12+13+5+5+5+5+5=842)第一年購置新的，一直用到第五年年底，則總費(fèi)用為：11+5+6+8+11+18=59

顯然不同的方案對應(yīng)不同的費(fèi)用。第i年度12345購置費(fèi)1111121213設(shè)備役齡0-11-22-33-44-5維修費(fèi)用5681118（2）方法：將此問題用一個(gè)賦權(quán)有向圖來描述，然后求這個(gè)賦權(quán)有向圖的最短路。求解步驟：1）畫賦權(quán)有向圖：

設(shè)Vi

表示第i年初，(Vi,Vj

)表示第i

年初購買新設(shè)備用到第j年初（j-1年底），而Wij

表示相應(yīng)費(fèi)用，則5年的一個(gè)更新計(jì)劃相當(dāng)于從V1

到V6的一條路。2）求解（標(biāo)號法）W12=11+5=16W13=11+5+6=22W14=11+5+6+8=30W15=11+5+6+8+11=41W16=11+5+6++8+11+18=59W23=11+5=16W24=11+5+6=22W25=11+5+6+8=30W26=11+5+6+8+11=41W45=12+5=17W46=12+5+6=23W56=13+5=18W34=12+5=17W35=12+5+6=23W36=12+5+6+8=31某工廠使用一種設(shè)備，這種設(shè)備在一定的年限內(nèi)隨著時(shí)間的推移逐漸損壞。所以工廠在每年年初都要決定設(shè)備是否更新。若購置設(shè)備，每年需支付購置費(fèi)用；若繼續(xù)使用舊設(shè)備，需要支付維修與運(yùn)行費(fèi)用，而且隨著設(shè)備的老化會(huì)逐年增加。計(jì)劃期（五年）內(nèi)中每年的購置費(fèi)、維修費(fèi)與運(yùn)行費(fèi)如表所示，工廠要制定今后五年設(shè)備更新計(jì)劃，問采用何種方案才能使包括購置費(fèi)、維修費(fèi)與運(yùn)行費(fèi)在內(nèi)的總費(fèi)用最小。年份12345購置費(fèi)1820212324使用年數(shù)0~11~22~33~44~5維修費(fèi)57121825年份12345購置費(fèi)1820212324使用年數(shù)0~11~22~33~44~5維修費(fèi)5712182528v1v2v3v4v5v62325262930426085324462334530設(shè)一個(gè)賦權(quán)有向圖D=(V,A),在V中指定一個(gè)發(fā)點(diǎn)vs和一個(gè)收點(diǎn)vt

,其它的點(diǎn)叫做中間點(diǎn)。對于D中的每一個(gè)弧(vi

,vj)∈A,都有一個(gè)非負(fù)數(shù)cij,叫做弧的容量。通常將這樣的圖D叫做一個(gè)容量網(wǎng)絡(luò)，簡稱網(wǎng)絡(luò)，記做D=(V，A，C)。網(wǎng)絡(luò)D上的流，是指定義在弧集合A上的一個(gè)函數(shù)其中f(vi

,vj)=fij

叫做弧(vi，vj)上的流量。4.TheMaximumFlowProblem*稱滿足下列條件的流為可行流：（1）容量條件：對于每一個(gè)弧(vi,vj)∈A有0

fij

cij

（2）平衡條件： 對于發(fā)點(diǎn)vs，有 對于收點(diǎn)vt

，有 對于中間點(diǎn)，有可行流中fij＝cij

的弧叫做飽和弧，fij＜cij的弧叫做非飽和弧。fij＞0的弧為非零流弧，fij＝0的弧叫做零流弧?？尚辛髁髁?3(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)圖中為零流弧，其余為非飽和弧。例定理可行流f是最大流的充分必要條件是不存在從vs到vt

的關(guān)于f的一條可增廣鏈。增廣鏈13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)是一個(gè)增廣鏈顯然圖中增廣鏈不止一條例截集vsv1v2v4v3vt374556378S例13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)設(shè)，則截集為容量為2413(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)設(shè)，則截集為容量為20求最大流的標(biāo)號法調(diào)整過程設(shè)1．令2．去掉所有標(biāo)號，回到第一步，對可行流重新標(biāo)號。求下圖所示網(wǎng)絡(luò)中的最大流，弧旁數(shù)為(1,1)v2v1v4v3vsvt(3,3)(5,1)(1,1)(4,3)(2,2)(3,0)(5,3)(2,1)(1,1)v2v1v4v3vsvt(3,3)(5,1)(1,1)(4,3)(2,2)(3,0)(5,3)(2,1)（0，+∞）（-v1,1）（+vs,4）（-v2，1）（+v2，1）(+v3，1)例(1,0)v2v1v4v3vsvt(3,3)(5,2)(1,0)(4,3)(2,2)(3,0)(5,3)(2,2)(1,0)v2v1v4v3vsvt(3,3)(5,2)(1,0)(4,3)(2,2)(3,0)(5,3)(2,2)（0，+∞）（+vs,3）最小截集13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)13(11)9(9)4(0)5(5)6(6)5(5)5(4)5(4)4(4)4(3)9(9)10(7)截集1截集2最小截量為：9+6+5=2070（70）70（50）130（100）150（130）150（150）50（20）50（50）120（30）100（100）∞（120）∞（230）∞（150）∞（200）已知網(wǎng)絡(luò)G=（V，E，C，d），f是G上的一個(gè)可行流，為一條從vs到vt的增廣鏈，稱為鏈的費(fèi)用。

結(jié)論：如果可行流f在流量為W(f)的所有可行流中的費(fèi)用最小，并且*是關(guān)于f的所有增廣鏈中的費(fèi)用最小的增廣鏈，那么沿增廣鏈u*調(diào)整可行流f，得到的新可行流f*也是流量為W(f*)的所有可行流中的最小費(fèi)用流。當(dāng)f*

是最大流時(shí)，就是最小費(fèi)用最大流。若*是從vs到vt的增廣鏈中費(fèi)用最小的增廣鏈，則稱*是最小費(fèi)用增廣鏈。5.TheMinimumCostFlowProblem尋找關(guān)于f的最小費(fèi)用增廣鏈：構(gòu)造一個(gè)關(guān)于f的賦權(quán)有向圖L(f)，其頂點(diǎn)是原網(wǎng)絡(luò)G的頂點(diǎn)，而將G中的每一條弧(vi,vj

)變成兩個(gè)相反方向的?。╲i，vj）和(vj

,vi)，并且定義圖中弧的權(quán)l(xiāng)ij為：1.當(dāng)，令

2.當(dāng)（vj，vi）為原來網(wǎng)絡(luò)G中（vi，vj）的反向弧，令在網(wǎng)絡(luò)G中尋找關(guān)于f的最小費(fèi)用增廣鏈等價(jià)于在L(f)中尋求從vs

到vt

的最短路。步驟：（1）取零流為初始可行流，f(0)={0}。（2）一般地，如果在第k-1步得到最小費(fèi)用流f(k-1)，則構(gòu)造圖L(f(k-1)

)。（3）在L(f(k-1)

)中，尋求從vs到vt的最短路。若不存在最短路，則f(k-1)就是最小費(fèi)用最大流；否則轉(zhuǎn)(4)。（4）如果存在最短路，則在可行流f

(k－1)的圖中得到與此最短路相對應(yīng)的增廣鏈，在增廣鏈上，對f

(k－1)進(jìn)行調(diào)整，調(diào)整量為：令得到新可行流f

(k)。對f

(k)重復(fù)上面步驟，返回（2）。例

求網(wǎng)絡(luò)的最小費(fèi)用最大流，弧旁權(quán)是（bij,cij）(3,2)vsv2v1vtv3(1,4)(6,7)(4,8)(1,6)(2,5)(2,3)3vsv2v1vtv3164122(1)L(f(0))(3,2)vsv2v1vtv3(1,4)(6,7)(4,8)(1,6)(2,5)(2,3)0vsv2v1vtv3300333(2)f(1)

1=3W(f(1))=3－1(3)L(f(1))－23vsv2v1vtv316412－1－21vsv2v1vtv3400343(4

)f(2)

2=1W(f(2))=4(3,2)vsv2v1vtv3(1,4)(6,7)(4,8)(1,6)(2,5)(2,3)(5)L(f(2))－3vsv2v1vtv3－1412－2－23－1661vsv2v1vtv3401453(6

)f(3)

3=1W(f(3))=5(7)L(f(3))vsv2v1vtv3－3－1