運籌學圖與網(wǎng)絡分析.ppt

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