運(yùn)籌學(xué)圖與網(wǎng)絡(luò)分析.ppt

圖與網(wǎng)絡(luò)分析 (Graph Theory and Network Analysis),圖與網(wǎng)絡(luò)的基本知識(shí),最短路問(wèn)題,樹(shù)及最小樹(shù)問(wèn)題,最大流問(wèn)題,哥尼斯堡七橋問(wèn)題,哥尼斯堡（現(xiàn)名加里寧格勒）是歐洲一個(gè)城市，Pregei河把該城分成兩部分，河中有兩個(gè)小島，十八世紀(jì)時(shí)，河兩邊及小島之間共有七座橋，當(dāng)時(shí)人們提出這樣的問(wèn)題：有沒(méi)有辦法從某處（如A）出發(fā)，經(jīng)過(guò)各橋一次且僅一次最后回到原地呢？,哥尼斯堡七空橋,一筆畫問(wèn)題,哈密爾頓（Hamilton）回路是十九世紀(jì)英國(guó)數(shù)學(xué)家哈密頓提出，給出一個(gè)正12面體圖形，共有20個(gè)頂點(diǎn)表示20個(gè)城市，要求從某個(gè)城市出發(fā)沿著棱線尋找一條經(jīng)過(guò)每個(gè)城市一次而且僅一次，最后回到原處的周游世界線路（并不要求經(jīng)過(guò)每條邊）。,有7個(gè)人圍桌而坐，如果要求每次相鄰的人都與以前完全不同，試問(wèn)不同的就座方案共有多少種？ 用頂點(diǎn)表示人，用邊表示兩者相鄰，因?yàn)樽畛跞魏蝺蓚€(gè)人都允許相鄰，所以任何兩點(diǎn)都可以有邊相連。,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,得到第一次就座方案是（1，2，3，4，5，6，7，1），繼續(xù)尋求第二次就座方案時(shí)就不允許這些頂點(diǎn)之間繼續(xù)相鄰，因此需要從圖中刪去這些邊。,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,得出第二次就座方案是（1，3，5，7，2，4，6，1），那么第三次就座方案就不允許這些頂點(diǎn)之間繼續(xù)相鄰，只能從圖中刪去這些邊。,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,得到第三次就座方案是（1，4，7，3，6，2，5，1），那么第四次就座方案就不允許這些頂點(diǎn)之間繼續(xù)相鄰，只能從圖中刪去這些邊，只留下7點(diǎn)孤立點(diǎn)，所以該問(wèn)題只有三個(gè)就座方案。,1,2,3,7,6,4,5,引論 圖的用處,某公司的 組織機(jī)構(gòu)設(shè)置圖,總公司,分公司,工廠或辦事處,一、 圖與網(wǎng)絡(luò)的基本知識(shí) （一）、圖與網(wǎng)絡(luò)的基本概念,1、一個(gè)圖是由點(diǎn)和連線組成。（連線可帶箭頭，也可不帶，前者叫弧，后者叫邊）,例,圖1,2、不帶箭頭的連線叫做邊。如果一個(gè)圖是由點(diǎn)和邊所構(gòu)成的，則稱其為無(wú)向圖，記作G = (V，E)，連接點(diǎn)的邊記作vi , vj，或者vj , vi。,3、若點(diǎn)與點(diǎn)之間的連線有方向，稱為弧。如果一個(gè)圖是由點(diǎn)和弧所構(gòu)成的，那么稱它為有向圖，記作D=(V, A)，其中V 表示有向圖D 的點(diǎn)集合，A 表示有向圖D 的弧集合。一條方向從vi指向vj 的弧，記作(vi , vj)。,圖2,4、一條邊的兩個(gè)端點(diǎn)是相同的,那么稱這條邊是環(huán)。 5、如果兩個(gè)端點(diǎn)之間有兩條以上的邊，那么稱它們?yōu)槎嘀剡叀?6、不含環(huán)和多重邊的圖稱為簡(jiǎn)單圖；有多重邊的圖稱為多重圖。,7、每一對(duì)頂點(diǎn)間都有邊相連的無(wú)向簡(jiǎn)單圖稱為完全圖。 有向完全圖則是指任意兩個(gè)頂點(diǎn)之間有且僅有一條有向邊的簡(jiǎn)單圖。,次為零的點(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)。,8、以點(diǎn)v為端點(diǎn)的邊的個(gè)數(shù)稱為點(diǎn)v 的次，記作 。,圖中 d(v1)= 4，d(v6)= 4（環(huán)計(jì)兩次）,定理1 所有頂點(diǎn)次數(shù)之和等于所有邊數(shù)的2倍。 定理2 在任一圖中，奇點(diǎn)的個(gè)數(shù)必為偶數(shù)。,所有頂點(diǎn)的入次之和等于所有頂點(diǎn)的出次之和。,有向圖中，以 vi 為始點(diǎn)的邊數(shù)稱為點(diǎn)vi的出次，用 表示 ；以 vi 為終點(diǎn)的邊數(shù)稱為點(diǎn)vi 的入次， 用 表示；vi 點(diǎn)的出次和入次之和就是該點(diǎn)的次。,9、設(shè)G=（V，E），G=（V,E）如果VV,EE，稱G是G的子圖；如果V=V,EE，稱G是G的生成子圖或支撐子圖。,在實(shí)際應(yīng)用中，給定圖中每條邊 ，對(duì)應(yīng)一個(gè)數(shù) ，稱之為 “權(quán)”。通常把這種賦權(quán)的圖稱為網(wǎng)絡(luò)。,10、由兩兩相鄰的點(diǎn)及其相關(guān)聯(lián)的邊構(gòu)成的點(diǎn)邊序列稱為鏈。 如:v0 ，e1，v1，e2，v2，e3 ，v3 ,vn-1 ,en ，vn，,11、圖中任意兩點(diǎn)之間均至少有一條鏈相連，則稱此圖為連通圖。,其鏈長(zhǎng)為 n ，其中 v0 ，vn 分別稱為鏈的起點(diǎn)和終點(diǎn) 。所含的點(diǎn)、邊均不相同的鏈稱為初等鏈。起點(diǎn)和終點(diǎn)是同一個(gè)點(diǎn)的鏈稱為圈。,（二）、 圖的矩陣表示 對(duì)于網(wǎng)絡(luò)（賦權(quán)圖）G=（V，E），其中邊 有權(quán) ，構(gòu)造矩陣 ，其中： 稱矩陣A為網(wǎng)絡(luò)G的權(quán)矩陣。,設(shè)圖G=（V，E）中頂點(diǎn)的個(gè)數(shù)為n，構(gòu)造一個(gè) 矩陣 ，其中： 稱矩陣A為網(wǎng)絡(luò)G的鄰接矩陣。,例,權(quán)矩陣為：,鄰接矩陣為：,二、 樹(shù)及最小樹(shù)問(wèn)題 已知有六個(gè)城市，它們之間 要架設(shè)電話線，要求任意兩個(gè)城市均可以互相通話，并且電話線的總長(zhǎng)度最短。,1、一個(gè)連通的無(wú)圈的無(wú)向圖叫做樹(shù)。 樹(shù)中次為1的點(diǎn)稱為樹(shù)葉，次大于1的點(diǎn)稱為分支點(diǎn)。,樹(shù) 的性質(zhì)： （1）數(shù)必連通，但無(wú)回路（圈）。 （2）n 個(gè)頂點(diǎn)的樹(shù)必有n-1 條邊。 （3）樹(shù) 中任意兩個(gè)頂點(diǎn)之間，恰有且僅有一條鏈（初等鏈）。 （4）樹(shù) 連通，但去掉任一條邊， 必變?yōu)椴贿B通。 （5）樹(shù) 無(wú)回路（圈），但不相鄰的兩個(gè)點(diǎn)之間加一條邊，恰得到一個(gè)回路（圈）。,2、 若圖G=(V , E )的生成子圖是一個(gè)樹(shù),那么稱該樹(shù) 是G 的一個(gè)生成樹(shù)（支撐樹(shù)），或簡(jiǎn)稱為圖G 的樹(shù)。圖G中屬于生成樹(shù)的邊稱為樹(shù)枝，不在生成樹(shù)中的邊稱為弦。,一個(gè)圖G 有生成樹(shù)的充要條件是G 是連通圖。,（一）破圈法：在圖中任選一個(gè)圈，從這個(gè)圈中去掉一條邊。在余下的圖中重復(fù)這個(gè)步驟，直到得到一不含圈的圖為止。,用破圈法求出下圖的一個(gè)生成樹(shù)。,（二）避圈法：開(kāi)始選一條邊，以后每一步中，總從未被選取的邊中選出一條與已選邊不構(gòu)成圈的邊，重復(fù)這個(gè)過(guò)程，直到不能進(jìn)行為止。,根據(jù)破圈法和避圈法兩種方式得到了圖的兩個(gè)不同的生成樹(shù)，由此可以看到連通圖的生成樹(shù)不是唯一的。,3、最小生成樹(shù)問(wèn)題,一棵生成樹(shù)所有樹(shù)枝上權(quán)的總和為這個(gè)生成樹(shù)的權(quán)。具有最小權(quán)的生成樹(shù)，稱為最小生成樹(shù)。 求賦權(quán)圖G的最小支撐樹(shù)的方法也有兩種，“破圈法”和“避圈法”。,破圈法：在原圖中，任選一個(gè)圈，從圈中去掉權(quán)最大的一條邊。在余下的圖中重復(fù)這個(gè)步驟，直到得到一不含圈的圖為止。,6,5,5,1,7,2,3,4,4,v1,v2,v3,v4,v5,v6,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,15,9,16,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,15,9,16,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,9,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,9,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,9,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,9,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,9,3,17,4,1,23,總造價(jià)=1+4+9+3+17+23=57,v1,v2,v3,v4,v5,1,4,2,3,1,3,5,2,避圈法：開(kāi)始選一條權(quán)最小的邊，以后每一步中，總從未被選取的邊中選一條權(quán)盡可能小，且與已選邊不構(gòu)成圈的邊。,某六個(gè)城市之間的道路網(wǎng)如圖 所示，要求沿著已知長(zhǎng)度的道路聯(lián)結(jié)六個(gè)城市的電話線網(wǎng)，使電話線的總長(zhǎng)度最短。,最短路的一般提法為：設(shè) 為連通圖，圖中各邊 有權(quán) （ 表示 之間沒(méi)有邊）， 為圖中任意兩點(diǎn)，求一條路 ，使它從 到 的所有路中總權(quán)最短。即： 最小。,(一)、狄克斯徹(Dijkstra)算法 適用于wij0，給出了從vs到任意一個(gè)點(diǎn)vj的最短路。,三 、最短路問(wèn)題,算法步驟： 1.給始點(diǎn)vs以P標(biāo)號(hào) ，這表示從vs到vs的最短距離為0，其余節(jié)點(diǎn)均給T標(biāo)號(hào)， 。 2.設(shè)節(jié)點(diǎn)vi為剛得到P標(biāo)號(hào)的點(diǎn)，考慮點(diǎn)vj，其中 ，且vj為T標(biāo)號(hào)。對(duì)vj的T標(biāo)號(hào)進(jìn)行如下修改： 3.比較所有具有T標(biāo)號(hào)的節(jié)點(diǎn)，把最小者改為P標(biāo)號(hào)，即： 當(dāng)存在兩個(gè)以上最小者時(shí)，可同時(shí)改為P標(biāo)號(hào)。若全部節(jié)點(diǎn)均為P標(biāo)號(hào)則停止，否則用 代替vi，返回步驟（2）。,例一：用Dijkstra算法求下圖從v1到v6的最短路。,解：（1）首先給v1以P標(biāo)號(hào)，給其余所有點(diǎn)T標(biāo)號(hào)。,（2）,（3）,（4）,（5）,（6）,（7）,（8）,（9）,（10）,反向追蹤得v1到v6的最短路為：,（二）、逐次逼近法 首先設(shè)任一點(diǎn)vi到任一點(diǎn)vj都有一條弧。 顯然，從v1到vj的最短路是從v1出發(fā)，沿著這條路到某個(gè)點(diǎn)vi再沿弧(vi,vj)到vj。則v1到vi的這條路必然也是v1到vi的所有路中的最短路。設(shè)P1j表示從v1到vj的最短路長(zhǎng)，P1i表示從v1到vi的最短路長(zhǎng)，則有下列方程： 開(kāi)始時(shí)，令 即用v1到vj的直接距離做初始解。,從第二步起，使用遞推公式： 求 ，當(dāng)進(jìn)行到第t步，若出現(xiàn) 則停止計(jì)算， 即為v1到各點(diǎn)的最短路長(zhǎng)。,例二、,6,6,0,-5,-3,v8,-5,-5,5,0,-1,v7,-1,-1,-1,7,1,0,1,v6,-3,-3,1,0,-1,v5,-7,-7,-7,3,2,0,8,v4,-2,-2,-2,-2,1,-5,0,-3,v3,-5,-5,-5,-1,2,0,6,v2,0,0,0,0,3,-2,-1,0,v1,P(4),P(3),P(2),P(1),v8,v7,v6,v5,v4,v3,v2,v1,求圖中v1到 各點(diǎn)的最短路,1,8,v1,v2,v3,v4,v5,2,6,3,5,1,3,5,2,1,1,2,1,1,v6,v7,v8,3,7,（0，0）,（ v3 ，-5）,（ v1 ，-2）,（ v3 ，-7）,（ v2 ，-3）,（ v4 ，-5）,（ v3 ，-1）,（ v6 ，6）,例、求：5年內(nèi)，哪些年初購(gòu)置新設(shè)備，使5年內(nèi)的總費(fèi)用最小。,解：（1）分析：可行的購(gòu)置方案（更新計(jì)劃）是很多的， 如： 1） 每年購(gòu)置一臺(tái)新的，則對(duì)應(yīng)的費(fèi)用為： 11+11+12+12+13 +5+5+5+5+5 = 84 2 )第一年購(gòu)置新的，一直用到第五年年底，則總費(fèi)用為： 11+5+6+8+11+18 = 59 顯然不同的方案對(duì)應(yīng)不同的費(fèi)用。,（2）方法：將此問(wèn)題用一個(gè)賦權(quán)有向圖來(lái)描述，然后求這個(gè)賦權(quán)有向圖的最短路。 求解步驟： 1）畫賦權(quán)有向圖： 設(shè) Vi 表示第i年初，(Vi ,Vj )表示第i 年初購(gòu)買新設(shè)備用到第j年初（j-1年底），而Wi j 表示相應(yīng)費(fèi)用，則5年的一個(gè)更新計(jì)劃相當(dāng)于從V1 到V6的一條路。 2）求解 （標(biāo)號(hào)法）,W12 =11+5=16 W13 =11+5+6=22 W14 =11+5+6+8=30 W15 =11+5+6+8+11=41 W16 =11+5+6+8+11+18=59,W23 =11+5=16 W24 =11+5+6=22 W25 =11+5+6+8=30 W26 =11+5+6+8+11=41,W45 =12+5=17 W46 =12+5+6=23 W56 =13+5=18,W34 =12+5=17 W35 =12+5+6=23 W36 =12+5+6+8=31,四、 最大流問(wèn)題 （一） 基本概念 1、設(shè)一個(gè)賦權(quán)有向圖G=（V, E）,在V中指定一個(gè)發(fā)點(diǎn)vs和一個(gè)收點(diǎn)vt ,其它的點(diǎn)叫做中間點(diǎn)。對(duì)于D中的每一個(gè)弧（vi , vj）E ,都有一個(gè)非負(fù)數(shù)cij,叫做弧的容量。我們把這樣的圖G叫做容量網(wǎng)絡(luò)，簡(jiǎn)稱網(wǎng)絡(luò)，記做 G=（V，E，C）。 網(wǎng)絡(luò)G上的流，是指定義在弧集合E上的一個(gè)函數(shù) 其中f(vi ,vj) =fij 叫做弧(vi，vj)上的流量。,2、稱滿足下列條件的流為可行流： （1）容量條件：對(duì)于每一個(gè)?。╲i ,vj）E 有 0 fij cij 。 （2）平衡條件： 對(duì)于發(fā)點(diǎn)vs，有 對(duì)于收點(diǎn)vt ，有 對(duì)于中間點(diǎn)，有,可行流中 fijcij 的弧叫做飽和弧，fijcij的弧叫做非飽和弧。,3、容量網(wǎng)絡(luò)G =（V，E，C），vs為始點(diǎn)，vt為終點(diǎn)。如果把V分成兩個(gè)非空集合 使 ，則所有一點(diǎn)屬于 ，而另一點(diǎn)屬于 的弧的集合，稱為由 決定的割集,記作 。割集 中所有始點(diǎn)在 ，終點(diǎn)在 的弧的容量之和，稱為這個(gè)割集的容量，記為 。,關(guān)于最大流問(wèn)題的定理： 最大流最小割定理：任一網(wǎng)絡(luò)中，最大流的流量等于最小割集的容量。,4、容量網(wǎng)絡(luò)G，若 為網(wǎng)絡(luò)中從vs到vt的一條鏈，給 定向?yàn)閺膙s到vt， 上的弧凡與 方向相同的稱為前向弧，凡與 方向相反的稱為后向弧，