運籌學圖與網(wǎng)絡(luò)分析 課件

1、圖與網(wǎng)絡(luò)分析 (Graph Theory and Network Analysis)圖與網(wǎng)絡(luò)的基本知識最短路問題樹及最小樹問題最大流問題哥尼斯堡七橋問題哥尼斯堡（現(xiàn)名加里寧格勒）是歐洲一個城市，Pregei河把該城分成兩部分，河中有兩個小島，十八世紀時，河兩邊及小島之間共有七座橋，當時人們提出這樣的問題：有沒有辦法從某處（如A）出發(fā)，經(jīng)過各橋一次且僅一次最后回到原地呢？BDACABCD哥尼斯堡七空橋一筆畫問題哈密爾頓（Hamilton）回路是十九世紀英國數(shù)學家哈密頓提出，給出一個正12面體圖形，共有20個頂點表示20個城市，要求從某個城市出發(fā)沿著棱線尋找一條經(jīng)過每個城市一次而且僅一次，最后回到

2、原處的周游世界線路（并不要求經(jīng)過每條邊）。有7個人圍桌而坐，如果要求每次相鄰的人都與以前完全不同，試問不同的就座方案共有多少種？用頂點表示人，用邊表示兩者相鄰，因為最初任何兩個人都允許相鄰，所以任何兩點都可以有邊相連。12376451237645123764512376451237645123764512376451237645得到第一次就座方案是（1，2，3，4，5，6，7，1），繼續(xù)尋求第二次就座方案時就不允許這些頂點之間繼續(xù)相鄰，因此需要從圖中刪去這些邊。12376451237645123764512376451237645123764512376451237645得出第二次就座方案是（

3、1，3，5，7，2，4，6，1），那么第三次就座方案就不允許這些頂點之間繼續(xù)相鄰，只能從圖中刪去這些邊。12376451237645123764512376451237645123764512376451237645得到第三次就座方案是（1，4，7，3，6，2，5，1），那么第四次就座方案就不允許這些頂點之間繼續(xù)相鄰，只能從圖中刪去這些邊，只留下7點孤立點，所以該問題只有三個就座方案。1237645引論 圖的用處 某公司的 組織機構(gòu)設(shè)置圖總公司分公司工廠或辦事處一、 圖與網(wǎng)絡(luò)的基本知識（一）、圖與網(wǎng)絡(luò)的基本概念 EADCB 1、一個圖是由點和連線組成。（連線可帶箭頭，也可不帶，前者叫弧，后者叫

4、邊）v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10例圖1一個圖是由點集 和 中元素的無序?qū)Φ囊粋€集合 構(gòu)成的二元組，記為G =(V，E )，其中V中的元素 叫做頂點，V表示圖G 的點集合；E中的元素 叫做邊，E 表示圖G的邊集合。jvV= 2、不帶箭頭的連線叫做邊。如果一個圖是由點和邊所構(gòu)成的，則稱其為無向圖，記作G = (V，E)，連接點的邊記作vi , vj，或者vj , vi。 3、若點與點之間的連線有方向，稱為弧。如果一個圖是由點和弧所構(gòu)成的，那么稱它為有向圖，記作D=(V, A)，其中V 表示有向圖D 的點集合，A 表示有向圖D 的弧集合。一條方向從vi指向vj

5、的弧，記作(vi , vj)。v4v6v1v2v3v5V = v1 , v2 , v3 , v4 , v5 , v6 ，A = (v1 , v3 ) , (v2 , v1) , (v2 , v3 ) ,(v2 , v5 ) , (v3 , v5 ) , (v4 , v5 ) , (v5 , v4 ) , (v5 , v6 ) 圖2 4、一條邊的兩個端點是相同的,那么稱這條邊是環(huán)。 5、如果兩個端點之間有兩條以上的邊，那么稱它們?yōu)槎嘀剡叀?6、不含環(huán)和多重邊的圖稱為簡單圖；有多重邊的圖稱為多重圖。 7、每一對頂點間都有邊相連的無向簡單圖稱為完全圖。 有向完全圖則是指任意兩個頂點之間有且僅有一條有

6、向邊的簡單圖。v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10 次為零的點稱為弧立點，次為1的點稱為懸掛點。懸掛點的關(guān)聯(lián)邊稱為懸掛邊。次為奇數(shù)的點稱為奇點，次為偶數(shù)的點稱為偶點。 8、以點v為端點的邊的個數(shù)稱為點v 的次，記作 。圖中 d(v1)= 4，d(v6)= 4（環(huán)計兩次） 定理1 所有頂點次數(shù)之和等于所有邊數(shù)的2倍。 定理2 在任一圖中，奇點的個數(shù)必為偶數(shù)。 所有頂點的入次之和等于所有頂點的出次之和。 有向圖中，以 vi 為始點的邊數(shù)稱為點vi的出次，用 表示 ；以 vi 為終點的邊數(shù)稱為點vi 的入次，用 表示；vi 點的出次和入次之和就是該點的次。9、設(shè)G=（V

7、，E），G=（V,E）如果VV,EE，稱G是G的子圖；如果V=V,EE，稱G是G的生成子圖或支撐子圖。 v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10e11(a)e5e7v1v2v5v6v7e1e6e8(b)子圖v1v2v3v4v5v6v7e1e6e7e9e10e11(c)支撐子圖在實際應(yīng)用中，給定圖中每條邊 ，對應(yīng)一個數(shù) ，稱之為 “權(quán)”。通常把這種賦權(quán)的圖稱為網(wǎng)絡(luò)。 10、由兩兩相鄰的點及其相關(guān)聯(lián)的邊構(gòu)成的點邊序列稱為鏈。 如:v0 ，e1，v1，e2，v2，e3 ，v3 ,vn-1 ,en ，vn， e3v1v2v3v4v5v6e7e8e1e2e4e5e6e9e1

8、0 11、圖中任意兩點之間均至少有一條鏈相連，則稱此圖為連通圖。 其鏈長為 n ，其中 v0 ，vn 分別稱為鏈的起點和終點 。所含的點、邊均不相同的鏈稱為初等鏈。起點和終點是同一個點的鏈稱為圈。（二）、 圖的矩陣表示對于網(wǎng)絡(luò)（賦權(quán)圖）G=（V，E），其中邊有權(quán) ，構(gòu)造矩陣 ，其中：稱矩陣A為網(wǎng)絡(luò)G的權(quán)矩陣。 設(shè)圖G=（V，E）中頂點的個數(shù)為n，構(gòu)造一個矩陣 ，其中： 稱矩陣A為網(wǎng)絡(luò)G的鄰接矩陣。 例權(quán)矩陣為：鄰接矩陣為：v5v1v2v3v4v64332256437 二、 樹及最小樹問題 已知有六個城市，它們之間 要架設(shè)電話線，要求任意兩個城市均可以互相通話，并且電話線的總長度最短。 v1v2

9、v3v4v5v6 1、一個連通的無圈的無向圖叫做樹。 樹中次為1的點稱為樹葉，次大于1的點稱為分支點。 樹 的性質(zhì)： （1）數(shù)必連通，但無回路（圈）。 （2）n 個頂點的樹必有n-1 條邊。 （3）樹 中任意兩個頂點之間，恰有且僅有一條鏈（初等鏈）。 （4）樹 連通，但去掉任一條邊， 必變?yōu)椴贿B通。 （5）樹 無回路（圈），但不相鄰的兩個點之間加一條邊，恰得到一個回路（圈）。v1v2v3v4v5v6 2、 若圖G=(V , E )的生成子圖是一個樹,那么稱該樹 是G 的一個生成樹（支撐樹），或簡稱為圖G 的樹。圖G中屬于生成樹的邊稱為樹枝，不在生成樹中的邊稱為弦。一個圖G 有生成樹的充要條件是

10、G 是連通圖。 v1v2v3v4v5v1v2v3v4v5（一）破圈法：在圖中任選一個圈，從這個圈中去掉一條邊。在余下的圖中重復這個步驟，直到得到一不含圈的圖為止。用破圈法求出下圖的一個生成樹。 v1v2v3v4v5e1e2e3e4e5e6e7e8v1v2v3v4v5e2e4e6e8v1v2v3v4v5e1e2e3e4e5e6e7e8（二）避圈法：開始選一條邊，以后每一步中，總從未被選取的邊中選出一條與已選邊不構(gòu)成圈的邊，重復這個過程，直到不能進行為止。v1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v5根據(jù)破圈法和避圈法兩種方式得到了圖的兩個

11、不同的生成樹，由此可以看到連通圖的生成樹不是唯一的。3、最小生成樹問題 一棵生成樹所有樹枝上權(quán)的總和為這個生成樹的權(quán)。具有最小權(quán)的生成樹，稱為最小生成樹。求賦權(quán)圖G的最小支撐樹的方法也有兩種，“破圈法”和“避圈法”。 破圈法：在原圖中，任選一個圈，從圈中去掉權(quán)最大的一條邊。在余下的圖中重復這個步驟，直到得到一不含圈的圖為止。655172344v1v2v3v4v5v6v1v7v4v3v2v5v620159162532817412336v1v7v4v3v2v5v620159162532817412336v1v7v4v3v2v5v6201591625328174123v1v7v4v3v2v5v620

12、1591625328174123v1v7v4v3v2v5v61591625328174123v1v7v4v3v2v5v61591625328174123v1v7v4v3v2v5v6925328174123v1v7v4v3v2v5v6925328174123v1v7v4v3v2v5v69328174123v1v7v4v3v2v5v69328174123v1v7v4v3v2v5v693174123總造價=1+4+9+3+17+23=57v1v2v3v4v514231352 避圈法：開始選一條權(quán)最小的邊，以后每一步中，總從未被選取的邊中選一條權(quán)盡可能小，且與已選邊不構(gòu)成圈的邊。 某六個城市之間的道路

13、網(wǎng)如圖 所示，要求沿著已知長度的道路聯(lián)結(jié)六個城市的電話線網(wǎng)，使電話線的總長度最短。 v1v2v3v4v5v66515723445v1v2v3v4v5v61234最短路的一般提法為：設(shè) 為連通圖，圖中各邊 有權(quán) （ 表示 之間沒有邊）， 為圖中任意兩點，求一條路 ，使它從 到 的所有路中總權(quán)最短。即： 最小。(一)、狄克斯徹(Dijkstra)算法適用于wij0，給出了從vs到任意一個點vj的最短路。三 、最短路問題算法步驟：1.給始點vs以P標號 ，這表示從vs到vs的最短距離為0，其余節(jié)點均給T標號， 。2.設(shè)節(jié)點vi為剛得到P標號的點，考慮點vj，其中 ，且vj為T標號。對vj的T標號進行

14、如下修改：3.比較所有具有T標號的節(jié)點，把最小者改為P標號，即：當存在兩個以上最小者時，可同時改為P標號。若全部節(jié)點均為P標號則停止，否則用 代替vi，返回步驟（2）。例一：用Dijkstra算法求下圖從v1到v6的最短路。 v1v2v3v4v6v5352242421 解：（1）首先給v1以P標號，給其余所有點T標號。（2）（3）（4）（5）（6）（7）（8）（9）（10）反向追蹤得v1到v6的最短路為：v1v2v3v4v6v5352242421（二）、逐次逼近法首先設(shè)任一點vi到任一點vj都有一條弧。顯然，從v1到vj的最短路是從v1出發(fā)，沿著這條路到某個點vi再沿弧(vi,vj)到vj。則

15、v1到vi的這條路必然也是v1到vi的所有路中的最短路。設(shè)P1j表示從v1到vj的最短路長，P1i表示從v1到vi的最短路長，則有下列方程： 開始時，令 即用v1到vj的直接距離做初始解。從第二步起，使用遞推公式：求 ，當進行到第t步，若出現(xiàn)則停止計算， 即為v1到各點的最短路長。例二、18v1v2v3v4v52635135211211v6v7v837660-5-3v8-5-550-1v7-1-1-17101v6-3-310-1v5-7-7-73208v4-2-2-2-21-50-3v3-5-5-5-1206v200003-2-10v1P(4)P(3)P(2)P(1)v8v7v6v5v4v3v

16、2v1求圖中v1到各點的最短路18v1v2v3v4v52635135211211v6v7v837（0，0）（ v3 ，-5）（ v1 ，-2）（ v3 ，-7）（ v2 ，-3）（ v4 ，-5）（ v3 ，-1）（ v6 ，6）例、求：5年內(nèi)，哪些年初購置新設(shè)備，使5年內(nèi)的總費用最小。 第i年度 1 2 3 4 5購置費 11 11 12 12 13設(shè)備役齡0-1 1-2 2-3 3-4 4-5維修費用 5 6 8 11 18解：（1）分析：可行的購置方案（更新計劃）是很多的， 如： 1） 每年購置一臺新的，則對應(yīng)的費用為： 11+11+12+12+13 +5+5+5+5+5 = 84 2

17、)第一年購置新的，一直用到第五年年底，則總費用為： 11+5+6+8+11+18 = 59 顯然不同的方案對應(yīng)不同的費用。 （2）方法：將此問題用一個賦權(quán)有向圖來描述，然后求這個賦權(quán)有向圖的最短路。 求解步驟： 1）畫賦權(quán)有向圖： 設(shè) Vi 表示第i年初，(Vi ,Vj )表示第i 年初購買新設(shè)備用到第j年初（j-1年底），而Wi j 表示相應(yīng)費用，則5年的一個更新計劃相當于從V1 到V6的一條路。 2）求解 （標號法） 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=59 W23

18、 =11+5=16 W24 =11+5+6=22W25 =11+5+6+8=30 W26 =11+5+6+8+11=41 W45 =12+5=17 W46 =12+5+6=23W56 =13+5=18 W34 =12+5=17W35 =12+5+6=23W36 =12+5+6+8=31 v1 v2 v3 v4 v5 v6162218171716304159312341302223 v1 v2 v3 v4 v5 v6162218171716304159312341302223四、 最大流問題（一） 基本概念1、設(shè)一個賦權(quán)有向圖G=（V, E）,在V中指定一個發(fā)點vs和一個收點vt ,其它的點叫做

19、中間點。對于D中的每一個?。╲i , vj）E ,都有一個非負數(shù)cij,叫做弧的容量。我們把這樣的圖G叫做容量網(wǎng)絡(luò)，簡稱網(wǎng)絡(luò)，記做G=（V，E，C）。網(wǎng)絡(luò)G上的流，是指定義在弧集合E上的一個函數(shù)其中f(vi ,vj) =fij 叫做弧(vi，vj)上的流量。 2、稱滿足下列條件的流為可行流：（1）容量條件：對于每一個弧（vi ,vj）E有 0 fij cij 。 （2）平衡條件：對于發(fā)點vs，有對于收點vt ，有對于中間點，有可行流中 fijcij 的弧叫做飽和弧，fijcij的弧叫做非飽和弧。vsv1v2v4v3vt374556378S 3、容量網(wǎng)絡(luò)G =（V，E，C），vs為始點，vt為終點。如果把V分成兩個非空集合 使 ，則所有一點屬于 ，而另一點屬于 的弧的集合，稱為由 決定的割集,記作 。割集 中所有始點在 ，終點在 的弧的容量之和，稱為這個割集的容量，記為 。 關(guān)于最大流問題的定理：最大流最小割定理：任一網(wǎng)絡(luò)中，最大流的流量等于最小割集的容量。 4、容量網(wǎng)絡(luò)G，若 為網(wǎng)絡(luò)中從vs到vt的一條鏈，給 定向為從vs到vt， 上的弧凡與 方向相同的稱為前向弧，凡與 方向相反的稱為后向弧，其集合分別用 和 表示。f 是一個可行流，如果滿足