西安理工大學工商管理學院,運籌學OperationsResearch,運籌學OperationsResearch,Chapter8圖與網(wǎng)絡(luò)分析GraphandNetwork,1.圖與網(wǎng)絡(luò)的基本知識樹3.最短路問題4.最大流問題,C,B,A,引例：哥尼斯堡七橋問題,您能從A、B、C或D任意一點出發(fā)走遍7座橋并且每座橋只走一次最后回到原出發(fā)點嗎？,D,E.Euler提出(1736年）：,中國郵路問題：管梅谷（1962年）提出一個郵遞員，負責某一地區(qū)的信件投遞。他每天要從郵局出發(fā)，走遍該地區(qū)所有街道再返回郵局，問應(yīng)如何安排送信的路線可以使所走的總路程最短？,我們在實際生活、生產(chǎn)和科研活動中經(jīng)?？吹皆S多的網(wǎng)絡(luò)，如互聯(lián)網(wǎng)、通信網(wǎng)、公路網(wǎng)、管道網(wǎng)、銷售網(wǎng)等。對網(wǎng)絡(luò)進行研究是希望解決其中的一些優(yōu)化問題，網(wǎng)絡(luò)最優(yōu)化能為人們管理和控制這些網(wǎng)絡(luò)系統(tǒng)提供一套有效的方法。,例某家電配送中心需要為多個銷售點送貨，配送中心與銷售點以及銷售點之間的相對位置和運輸情況可以用圖來表示。其中，點v1，v2，v7代表銷售點，邊表示運輸路線。若已知每條路線行走所需的時間，請幫助配送中心管理人員設(shè)計一條送貨路線，使送貨車輛用最短的時間送完貨物，并回到配送中心。,基本的網(wǎng)絡(luò)最優(yōu)化問題有4個，即最小樹問題，最短路問題、最大流問題、最小費用最大流問題。這些問題的數(shù)學模型實際上大都是線性規(guī)劃問題，但使用線性規(guī)劃的單純形法去求解，過程非常繁瑣，本章介紹的網(wǎng)絡(luò)分析方法能有效的解決這些問題。,圖可定義為點和邊的集合，記作,式中是點的集合，是邊的集合。注意上面定義的圖區(qū)別于幾何學中的圖。在幾何學中，圖中點的位置、線的長度和斜率等都十分重要，而這里只關(guān)心圖中有多少點以及哪些點之間有線相連，如果給圖中的點和邊賦以具體的含義和權(quán)數(shù)，如距離、費用、容量等，把這樣的圖稱為網(wǎng)絡(luò)圖，記作。圖和網(wǎng)絡(luò)分析的方法已廣泛應(yīng)用于物理、化學、控制論、信息論、計算機科學和經(jīng)濟管理等各個領(lǐng)域。,8.1圖與網(wǎng)絡(luò)的基本知識,如圖8-1,定義1端點，關(guān)聯(lián)邊，相鄰若有邊e可表示為e=vi,vj,稱vi和vj是邊e的端點，反之稱邊e為點vi或vj的關(guān)聯(lián)邊。若點vi、vj與同一邊關(guān)聯(lián)，稱點vi和vj相鄰；若邊ei和ej具有公共的端點，稱邊ei和ej相鄰。,例如圖81，,v2和v4是邊e6的端點，反之邊e6是點v2、v4的關(guān)聯(lián)邊。點v2、v4相鄰；邊e6與e5、e4相鄰。,圖81,e2可記作：,一、圖與網(wǎng)絡(luò)的基本概念,定義2環(huán)，多重邊，簡單圖如果邊e的兩個端點相重，稱該邊為環(huán)。如圖8中邊e1為環(huán)。如果兩個點之間的邊多于一條，稱為多重邊，如圖8中的e4和e5，對無環(huán)、無多重邊的圖稱作簡單圖。,定義3次，奇點，偶點，孤立點與某一個點vi相關(guān)聯(lián)的邊的數(shù)目稱為點vi的次（也叫做度），記作d(vi)。圖中d(v1),d(v3)=5,d(v5)=1。次為奇數(shù)的點稱作奇點，次為偶數(shù)的點稱作偶點，次為0的點稱作孤立點。,定理1任何圖中，頂點次數(shù)的總和等于邊數(shù)的2倍。,定理2任何圖中，次為奇數(shù)的頂點必為偶數(shù)個。,定義4有向圖：如果圖的每條邊都有一個方向則稱為有向圖,定義5混合圖：如何圖G中部分邊有方向則稱為混合圖,有向圖,定義6有向圖中，以Vi為起始點的邊數(shù)稱為點Vi的出次，用表示；有向圖中，以Vi為終點的邊數(shù)稱為點Vi的入次，用表示。,結(jié)論1：Vi點的出次與入次之和就是該點的次。,結(jié)論2：有向圖中，所有頂點的入次之和等于所有頂點的出次之和。,定義7：子圖、生成子圖（支撐子圖）,圖G1=V1、E1和圖G2=V2，E2如果稱G1是G2的一個子圖。若有則稱G1是G2的一個支撐子圖（部分圖）。圖8-2（a）是圖6-1的一個子圖，圖8-2（b）是圖8-1的支撐子圖，注意支撐子圖也是子圖,子圖不一定是支撐子圖。,定義8網(wǎng)絡(luò)（賦權(quán)圖）：,設(shè)圖G（V，E），對G的每一條邊(vi,vj)相應(yīng)的有一條數(shù)w(vi,vj)(或記為wij)，wij稱為邊(vi,vj)的權(quán),賦有權(quán)的圖G稱為網(wǎng)絡(luò)（賦權(quán)圖）。,這里的權(quán)數(shù)可以是時間、費用、距離等，視不同背景代表不同的含義。,賦權(quán)圖,定義9鏈、路、回路（圈）無向圖中有些點和邊的交替序列對任意vi,t1和vit(2tk)均相鄰，稱從v0到vk的鏈。,圖81中，1=v5,e8,v3,e3,v1,e2,v2,e4,v3,e7,v5是一條鏈，1中因頂點v3重復(fù)出現(xiàn)，不能稱作路。,二、連通圖,如果鏈中所有的頂點v0，v1，vk也不相同，這樣的鏈稱初等鏈（或路）。,如果鏈中各邊e1,e2,ek互不相同稱為簡單鏈。,當v0與vk重合時稱為回路（或圈），如果邊不重復(fù)稱為簡單回路，如果邊不重復(fù)點也不重復(fù)則稱為初等回路。,是一條鏈也是一條路。是一條回路并且是簡單回路。,定義10連通圖,若在一個圖中，如果每一對頂點之間至少存在一條鏈，稱這樣的圖為連通圖，否則稱該圖是不連通的。圖81是連通圖。,3=v4,e7,v3,e3,v1,e2,v2,e6,v4,歐拉回路,定義11連通圖G中，若存在一條回路，經(jīng)過每邊一次且僅一次，則稱這條回路為歐拉回路。具有歐拉回路的圖稱為歐拉圖（E圖）。,哥尼斯堡七橋問題：尋找一條歐拉回路,定理3無向連通圖G是歐拉圖，當且僅當G中無奇點。,七橋問題：d(A)=3,d(B)=3,d(C)=5,d(D)=3有四個奇點，故不是歐拉圖,定理4有向連通圖G是歐拉圖，當且僅當G中每個頂點的出次等于入次。,中國郵路問題,討論：奇偶點圖上作業(yè)法,v1,v2,v3,v4,v5,v6,v7,v8,v9,8.2樹,樹的概念,樹是圖論中結(jié)構(gòu)最簡單但又十分重要的圖，在許多領(lǐng)域都有應(yīng)用。如：運動員抽簽結(jié)構(gòu)圖,定義樹、生成樹：,無圈的連通圖稱為樹；若G1是G2的一個支撐子圖并且是一棵樹，則稱G1是G2的一棵生成樹。,圖83(a)是一棵樹，圖83(b)是圖81的一棵生成樹。,v1,v1,圖81,圖83(a),圖83(b),定理：圖G=（V，E）有生成樹的充分必要條件為G是連通圖。,生成樹的尋求方法,在圖中，每步選出一條邊使它與已選邊不構(gòu)成圈，直到選夠n-1條邊為止。,（）深探法步驟：任取一點v，給v以標號；若某點u已得標號i，檢查其端點w是否已標號；若端點w未標號，則給w以標號i+1;重復(fù)若端點均已標號，則退到標號i1的點，重復(fù)。,(2)廣探法,任取一點v，給v以標號；檢查其所有端點wi是否已標號；若端點w未標號，則給所有wi以標號i+1;對標號i+1的點重復(fù)。,（3）破圈法在圖中任意取一個圈，從圈上任意舍棄一條邊，將這個圈破掉；重復(fù)上述步驟，直到圖中沒有圈為止。,例：某鄉(xiāng)有9個自然村，其鄉(xiāng)間道路如下圖，要求：以v0村為中心沿道路架設(shè)有線廣播網(wǎng)絡(luò)，應(yīng)如何架設(shè)？,最小生成樹,定義：設(shè)GV,E是一個連通圖，每一條邊eiE具有長度C(ei)0,G的任意生成樹T各條邊的長度之和稱為樹T的長度，記為C（T）。長度最小的生成樹稱為最小樹。,最小樹的應(yīng)用：電信網(wǎng)絡(luò)（計算機網(wǎng)絡(luò)、電話專用線網(wǎng)絡(luò)、有線電視網(wǎng)絡(luò)等等）的設(shè)計低負荷運輸網(wǎng)絡(luò)的設(shè)計，使得網(wǎng)絡(luò)中提供鏈接的部分（如鐵路、公路等等）的總成本最小高壓輸電線路網(wǎng)絡(luò)的設(shè)計電器設(shè)備線路網(wǎng)絡(luò)（如數(shù)字計算機系統(tǒng)）的設(shè)計，使得線路總長度最短連接多個場所的管道網(wǎng)絡(luò)設(shè)計,求最小樹是在一個無向連通圖G中求一棵最小生成樹。,避圈法（加邊法）：去掉G中所有邊，得到n個孤立點；然后加邊；,加邊的原則：從最短邊開始添加，加邊的過程中不能形成圈，直到連通（n1條邊）。,v1,v2,v3,v4,v5,v6,4,3,5,2,1,MinC(T)=15,求最小樹的方法：避圈法和破圈法,破圈法：任取一圈，去掉圈中最長邊，直到無圈。,v1,v2,v3,v4,v5,v6,4,3,5,2,1,得到最小樹：,MinC(T)=15,根樹及其應(yīng)用,定義有向樹：若一個有向圖是一棵樹，則稱這個有向圖為有向樹。,定義若有向樹T恰有一個結(jié)點的入次為0，其余各點入次均為1，則稱T為根樹。,入次為0的點，稱為根,出次為0的點，稱為葉,其它頂點，稱為分枝點,根到某頂點vi的道路長度，稱為vi點的層次。,定義在根樹T中，若每個頂點的出次小于或等于m，則稱T為m叉樹。若每個頂點的出次恰好等于m或零，則稱T為完全m叉樹。,當m=2時，稱為二叉樹、完全二叉樹。,記二叉樹各葉子的權(quán)為pi，根到各葉子的距離（層次）為li二叉樹的總權(quán)數(shù)：,最優(yōu)二叉樹：滿足總權(quán)最小的二叉樹稱為最優(yōu)二叉樹?；舴蚵―AHuffman)給出了一個求最優(yōu)二叉樹的算法，又稱霍夫曼樹。,例：最優(yōu)檢索問題用計算機進行圖書分類?，F(xiàn)有五類圖書共100萬冊，其中有A類50萬冊，有B類20萬冊，C類5萬冊，D類10萬冊，E類15萬冊。問如何安排分檢過程，可使總的運算次數(shù)最??？,算法步驟：1.將s個葉子按權(quán)由小至大排序；2.將二個具有最小權(quán)的葉子合并成一個分枝點，其權(quán)為p1+p2；將新的分枝點作為一個葉子，合并，,解：構(gòu)造一棵具有5個葉子的最優(yōu)二叉樹，其葉子的權(quán)分別為50，20，5，10，15.步驟如下：1.將5個葉子按權(quán)由小到大排序：5，10，15，20，502.找出二個最小權(quán)的葉子，合并成一個分枝點，其權(quán)為15；,依次，繼續(xù)。,總權(quán)為：,分檢過程是：先把A類50萬冊從總數(shù)中分檢出來，其次將B類20萬冊分檢出來，然后再將E類15萬冊分檢出來，最后再將D、C分檢出來。,8.3最短路問題,有些問題，如選址、管道鋪設(shè)時的選線、設(shè)備更新、投資、某些整數(shù)規(guī)劃和動態(tài)規(guī)劃的問題，也可以歸結(jié)為求最短路的問題。因此這類問題在生產(chǎn)實際中得到廣泛應(yīng)用。,求最短路有兩種算法，一是求從某一點至其它各點之間最短離的狄克斯屈拉(Dijkstra)算法；另一種是求網(wǎng)圖上任意兩點之間最短的矩陣算法。,最短路問題，就是從給定的網(wǎng)絡(luò)圖中找出一點到各點或任意兩點之間距離最短的一條路.,渡河問題,一老漢帶了一只狼、一只羊、一棵白菜想要從南岸過河到北岸，河上只有一條獨木舟，每次除了人以外，只能帶一樣東西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，問應(yīng)該怎樣安排渡河，才能做到既把所有東西都運過河去，并且在河上來回次數(shù)最少？這個問題就可以用求最短路方法解決。,設(shè)：M人W狼S羊V白菜,渡河方案共有10種，構(gòu)造如下一個圖，每條邊的距離為1，問題變?yōu)榍笠粭l從MWSV到的最短路。,北岸,南岸,狄克斯屈拉(Dijkstra)標號算法,點標號：b(j)起點vs到點vj的最短路長；,邊標號：k(i，j)=b(i)+dij，,步驟：1.令起點的標號；b(s)0。,先求有向圖的最短路，設(shè)網(wǎng)絡(luò)圖的起點是vs,終點是vt,以vi為起點vj為終點的弧記為（i，j）,距離為dij,2.找出所有vi已標號vj未標號的弧集合B=（i，j）如果這樣的弧不存在或vt已標號則計算結(jié)束；,3.計算集合B中弧k(i，j)=b(i)+dij的標號,4.選一個點標號返回到第2步。,【例】求下圖v1到v7的最短路長及最短路線,0,8,6,2,2,5,4,4,11,14,7,5,10,7,12,11,v7已標號，計算結(jié)束。從v1到v7的最短路長是11,最短路線是：v1v4v6v7,無向圖最短路的求法,無向圖最短路的求法只將上述步驟2改動一下即可。,點標號：b(i)起點vs到點vj的最短路長；,邊標號：k(i，j)=b(i)+dij，,步驟：1.令起點的標號；b(s)0。,3.計算集合B中邊標號：ki，j=b(i)+dij,4.選一個點標號:返回到第2步。,2.找出所有一端vi已標號另一端vj未標號的邊集合B=i，j如果這樣的邊不存在或vt已標號則計算結(jié)束；,【例】求下圖v1到各點的最短路及最短距離,0,4,5,2,2,3,10,3,9,6,12,6,4,11,6,6,18,8,12,24,8,24,18,所有點都已標號，點上的標號就是v1到該點的最短距離，最短路線就是紅色的鏈。,有負權(quán)的最短路算法,假設(shè)圖中沒有負回路。如下圖是一條負回路，最短路權(quán)無下界。,當vi到vj之間沒有弧連接時，令lij,列表迭代計算：,設(shè)vs到vj經(jīng)過vi到達vj，則vs到vj的最短距離為：,迭代：,【例】求下圖v1到v8的最短路長及最短路線,2,0,3,6,11,0,2,0,3,6,6,15,0,2,0,3,3,6,14,10,(表中空格為),020-336910,采用”反向追蹤”的方法找出從v1到v8的最短路.,已知:P(v1,v8)=10，而P(v1,v8)=minP(v1,vi)+li8,尋找：P(v1,v6）+l68=6+4=10,記下：v6v8,再檢查：P(v1,v6）=6,尋找：P(v1,v3）+l36=0+6=6,記下：v3v6v8,v1v2v3v6v8,再檢查：P(v1,v3）=0,尋找：P(v1,v2）+l23=2+(-2)=0,記下：v2v3v6v8,8.4最大流問題,許多系統(tǒng)中都涉及到流量問題，例如網(wǎng)絡(luò)系統(tǒng)中有信息流、公路系統(tǒng)中有車輛流、金融系統(tǒng)中有現(xiàn)金流等等。對于這些包含了流量問題的系統(tǒng)，我們往往需要求出其系統(tǒng)的最大流量。例如，某公路系統(tǒng)的容許通過的最大車輛數(shù)，某網(wǎng)絡(luò)系統(tǒng)的最大信息流量等，以便于對某個系統(tǒng)加以認識并進行管理。,例某石油公司建有一個可以把石油從采地輸送到不同銷售點的管道網(wǎng)絡(luò)，如下圖。由于管道的直徑變化，使得各段管道（vi,vj）的最大通過能力（容量）cij也是不一樣的，cij的單位為萬加侖/小時。要求我們制定一個輸送方案，將石油從v1輸送到v6，使得輸送的石油達到最大,基本概念,容量：在某時期內(nèi)弧(i，j)上的最大通過能力。記為C(i，j)或Cij在上圖中，C12=4，C138，C234等，怎樣安排運輸方案，才能使在某一時期內(nèi)從v1運到v6的物資最多，這樣的問題就是最大流問題，,網(wǎng)絡(luò)中所有流起源于一個叫做發(fā)點的節(jié)點（源）,所有的流終止于一個叫做收點的節(jié)點,其余所有的節(jié)點叫做中間點（轉(zhuǎn)運點）,通過每一條弧的流只允許沿著弧的箭頭方向流動,目標是使得從發(fā)點到收點的總流量最大,8.4最大流問題,流量：弧(i，j)的實際通過量，記為f(i，j)或fij,可行流：如果fij滿足：1.對于所有弧(i，j)有0fijCij,則稱流量集合fij為網(wǎng)絡(luò)的一個可行流，簡記為f。,以下假設(shè)網(wǎng)絡(luò)是一個簡單連通圖。,2.對于中間點點vm有：,鏈：從發(fā)點到收點的一條路線（弧的方向不一定都同向）稱為鏈。從發(fā)點到收點的方向規(guī)定為鏈的方向。,前向?。号c連的方向相同的弧稱為前向弧。,后向?。号c連的方向相反的弧稱為后向弧。,增廣鏈設(shè)f是一個可行流，如果存在一條從vs到vt的鏈，滿足：,1.所有前向弧上fij0,則該鏈稱為增廣鏈,容量,流量,【定理】設(shè)網(wǎng)絡(luò)G的一個可行流f，如果存在一條從vs到vt的增廣鏈，那么就可改進一個值更大的可行流f1，并且valf1>valf,【證】設(shè)valfv,對改進的可行流f1：,最大流的標號算法,步驟1.找出第一個可行流，例如所有弧的流量fij=0,2.用標號的方法找一條增廣鏈A：發(fā)點標號（，），,B：選一個已標號的點vi，對于vi的所有未給標號的鄰接點，按下列規(guī)則處理：如果是前向弧并且有fij<Cij，令j=minCijfij,i，則vj標號（+vi，j)如果是后向弧vi并且有fj0，令j=minfij,i，則vj標號（-vi，j),當收點不能得到標號時，說明不存在增廣鏈，計算結(jié)束。,當收點已得到標號時，說明已找到增廣鏈。,【定理】可行流是最大流當且僅當不存在發(fā)點到收點的增廣鏈,4.調(diào)整流量,得到新的可行流，去掉所有標號，從發(fā)點重新標號尋找增廣鏈，直到收點不能標號為止。,3.依據(jù)vi的第一個標號反向跟蹤得到一條增廣鏈；依據(jù)vi的第二個標號求最小值得到調(diào)整量,（，+）,4,2,2,0,2,2,2,2,0,4,（+v1,6）,【例】求下圖v1到v6的最大流及最大流量,【解】1.通過觀察得到初始可行流,2.標號,3.得到增廣鏈,(+v2,2),(+v2,1),(+v5,1),(+v1,2),（，）,5,2,2,1,2,2,2,3,0,4,得到增廣鏈,4.求調(diào)整量,5.調(diào)整可行流,去掉所有標號，重新標號,(+v1,1),（+v1,6）,(+v2,1),(-v4,0),(+v4,1),求調(diào)整量,調(diào)整可行流,去掉所有標號，重新標號,（，）,（+v1,6）,(-v3,2),(+v2,1),(-v4,0),(+v4,1),求調(diào)整量,調(diào)整可行流,去掉所有標號，重新標號,標號不能繼續(xù)進行，說明不存在從發(fā)點到收點的增廣鏈，得到最大流.,最大流量v=6+3=9,（，）,（+v1,5）,(-v3,1),截集將圖G（V，E）的點集分割成兩部分,稱為一個截集，截集中所有弧的容量之和稱為截集的截量。,下圖所示的截集為,又如下圖所示的截集為,上圖所示的截集為,所有截量中此截量最小且等于最大流量，此截集稱為最小截集。,【定理】最大流量等于最小截集的截量。,TheEndofChapter6,作業(yè):教材P285T10.1110.1210.14,Exit,1.基本概念容量、流量、可行流、前向弧、后向弧、增廣鏈、最大流、最大流量、割集、割量、最大流量最小割量定理2.如何用標號方法求增廣鏈3.怎樣求調(diào)整量、如何調(diào)整流量4.用QSB軟件求最大流問題,