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

《運籌學課件ch10圖與網(wǎng)絡(luò)分析.ppt》由會員分享，可在線閱讀，更多相關(guān)《運籌學課件ch10圖與網(wǎng)絡(luò)分析.ppt（58頁珍藏版）》請在裝配圖網(wǎng)上搜索。

第十章,圖與網(wǎng)絡(luò)分析 Graph & Network Analysis,章節(jié)大綱,圖的基本概念 樹與最小支撐樹的應用 最短路問題 網(wǎng)絡(luò)最大流問題 最小費用最大流問題,1847年 物理學家克希荷夫發(fā)表了關(guān)于樹的第一篇論文,1857年 英國數(shù)學家凱萊利用樹的概念研究有機化合物的分子結(jié)構(gòu),1878年雪爾佛斯脫首次使用“圖”這個名詞,1936年匈牙利數(shù)學家哥尼格發(fā)表了第一本圖論專著有限圖與無限圖的理論,20世紀50年代 圖論形成了兩個本質(zhì)上不同的發(fā)展方向,圖論系統(tǒng)的理論研究,1736年 數(shù)學家歐拉發(fā)表了關(guān)于圖的第一篇論文,圖論的代數(shù)方向,圖論的最優(yōu)化方向,1736年 瑞士數(shù)學家 歐拉（E. Euler) 提出“七橋問題” 通過每座橋剛好一次又回到原地。,是否可以 一筆畫？,1859年 英國數(shù)學家 哈密爾頓(Hamiltonian),用一個規(guī)則的實心十二面體，它的20個頂點標出世界 著名的20個城市，要求游戲者找一條沿著各邊通過每 個頂點剛好一次的閉回路，即 “環(huán)球旅行” 。, 由于運籌學、計算機科學和編碼理論中的很多 問題都可以化為哈密頓問題，從而引起廣泛的注意和 研究。, 發(fā)明“環(huán)球旅行”游戲,用圖論的語言來說，游戲的目的是在十二面體的圖中 找出一個生成圈。這個問題后來就被稱為哈密頓問題。,1850年 英國人格思里提出了“四色猜想”,1976年，美國數(shù)學家阿佩爾與哈肯在美國伊利諾斯大學的兩臺不同的電子計算機上， 用了1200個小時，作了100億個判斷，終于完成了四色定理的證明。,任何一個平面圖，都可以用四種顏色來染色，使得任何兩個相鄰的區(qū)域有不同的顏色。, 世界近代三大數(shù)學難題之一,格思里和其弟弟格里斯,德摩爾根的好友、著名數(shù)學家哈密爾頓爵士,幾百年來，許多數(shù)學家致力于這項研究：,格思里弟弟的老師、著名數(shù)學家德摩爾根,英國最著名數(shù)學家凱利,18781880年兩年間，著名的律師兼數(shù)學家肯普和泰勒兩人分別提交了證明四 色猜想的論文，宣布證明了四色定理，大家都認為四色猜想從此也就解決了。,11年后，即1890年，數(shù)學家赫伍德以自己的精確計算指出肯普的證明是錯誤的。,不久，泰勒的證明也被人們否定了。,例 2 有A、B、C、D、E 五個球隊舉行比賽，已知A 隊與其它各隊都比賽過一 次；B 隊和A、C 隊比賽過；C 隊和A、B、D 隊賽過； D 隊和A、C、E 隊比賽過；E 隊和A、D 隊比賽過。,那么：這種比賽關(guān)系就可以用圖來表示,A,B,C,D,E,點：表示球隊,點與點之間的連線：表示兩球隊間比賽過,例3 五個球隊之間的比賽結(jié)果是：A隊勝了B、D、E隊； B隊勝了C隊； C隊 勝了A、D隊； D隊沒有勝過；E隊勝了D隊；, 用點與點之間帶箭頭的線描述“勝負關(guān)系”關(guān)系,從圖中可以看出各球隊之間比賽情況：,A,B,C,D,E,那么，這種勝負關(guān)系該如何用圖來描述呢？,10.1 圖的基本概念,定義 一個圖G是指一個二元組(V(G),E(G)，即圖是由點及點之間的聯(lián)線所組成。其中:,1）圖中的點稱為圖的頂點(vertex)，記為：v,2）圖中的連線稱為圖的邊(edge)，記為：e vi, vj，vi、vj是邊 e 的端點。,3）圖中帶箭頭的連線稱為圖的弧(arc)，記為：a (vi, vj)，vi、vj是弧 a 的 端點。, 要研究某些對象間的二元關(guān)系時，就可以借助于圖進行研究,分類 無向圖：點集V和邊集E構(gòu)成的圖稱為無向圖(undirected graph)，記為： G(V，E) 若這種二元關(guān)系是對稱的，則可以用無向圖進行研究 有向圖：點集V和弧集A構(gòu)成的圖稱為有向圖(directed graph) ，記為：D(V，A) 若這種二元關(guān)系是非對稱的，則可以用有向圖進行研究 有限圖: 若一個圖的頂點集和邊集都是有限集，則稱為有限圖.只有一個頂點的圖稱為平凡圖，其他的所有圖都稱為非平凡圖.,1 圖反映對象之間關(guān)系的一種工具，與幾何圖形不同。,2 圖中任何兩條邊只可能在頂點交叉，在別的地方是立體交叉，不是圖的頂點。,3 圖的連線不用按比例畫，線段不代表真正的長度，點和線的位置有任意性。,4 圖的表示不唯一。如：以下兩個圖都可以描述“七橋問題”。,圖的特點：,3 奇點：次為奇數(shù)的點。,4 偶點：次為偶數(shù)的點。,5 孤立點：次為零的點。,6 懸掛點：次為1的點。,1 端點：若e =u，v E，則稱u，v 是 e 的端點。,2 點的次：以點 v 為端點的邊的個數(shù)稱為點 v 的次，記為：d(v)。 在無向圖G中，與頂點v關(guān)聯(lián)的邊的數(shù)目(環(huán)算兩次),稱為頂點v的度或次數(shù)，記為d(v)或 dG(v). 在有向圖中，從頂點v引出的邊的數(shù)目稱為頂點v的出度，記為d+(v)，從頂點v引入的邊的數(shù)目稱為v的入度，記為d -(v). 稱d(v)= d+(v)+d -(v)為頂點v的度或次數(shù),點(vertex)的概念,例1 G =(V, E),Vv1, v2, v3, v4 , v5 , v6 , v7 ,Ee1, e2, e3, e4 , e5 , e6 , e7 , e8 ,奇點：v2，v3,偶點：v1，v4,懸掛點：v5，v6,孤立點：v7,如：e1、e2 是多重邊。,e8 是懸掛邊。,e7 是環(huán),圖 G 或 D 中點的個數(shù)記為 p(G) 或 p(D) ，簡記為 p,圖 G 或 D 中邊的個數(shù)記為 q(G) 或 q(D)，簡記為 q,點的個數(shù)p7,邊的個數(shù)q8,定理,推論 任何圖中奇點的個數(shù)為偶數(shù),3 初等鏈（圈）：若鏈（圈）中各點均不同，則稱為初等鏈（圈） 。,如：, v1, e1, v2, e3, v3 ,4 簡單鏈（圈） ：若鏈（圈）中各邊均不同，則稱為間單鏈（圈） 。,1 鏈：一個點、邊的交替的連續(xù)序列vi1, ei1, vi2, ei2, , vik, eik稱為鏈，記為。,2 圈(cycle)：若鏈的 vi1vik，即起點終點，則稱為圈。,鏈(chain)的概念, v1, e1, v3, e4, v4 ,：,鏈,初等鏈,簡單鏈,不是鏈, v1, e1, v2, e3, v3 , e6 , v1 ,圈,初等圈,間單圈,圈一定是鏈，鏈不一定是圈,路PATH,路(path)：頂點和邊均互不相同的一條途徑。 若在有向圖中的一個鏈中每條弧的方向一致，則稱為路。（無向圖中的路與鏈概念一致。） 回路(circuit)：若路的第一個點與最后一個點相同，則稱為回路。 連通性: 點i和j點是連通的：G中存在一條（i，j）路 G是連通的：G中任意兩點都是連通的, 路一定是鏈，但鏈不一定是路,例 在右邊的無向圖中：,途徑或鏈：,跡或簡單鏈：,路或路徑：,圈或回路：, v1, e1, v2, e3, v3 ,鏈,不是路, v1, e2, v2, e3, v3 ,鏈,且是路, v1, e2, v2, e1, v1 ,鏈,是回路, 注意區(qū)別：環(huán)、圈、回路的概念,在右邊的有向圖中：,連通圖(connected graph)：若圖中任何兩點間至少有一條鏈，則稱為連通圖 。否則， 為不連通圖。,簡單圖(simple graph)：一個無環(huán)、無多重邊的圖稱為間單圖。,多重圖(multiple graph)：一個無環(huán)，但有多重邊的圖稱為多重圖。,連通分圖：非連通圖的每個連通部分稱為該圖的連通分圖。,基礎(chǔ)圖：去掉有向圖中所有弧上的箭頭，得到的圖稱為原有向圖的基礎(chǔ)圖。,圖G(V, E)為不連通圖,但G(V, E)是G的連通分圖 其中：Vv1, v2, v3, v4 Ee1, e2, e3, e4, e5, e6, e7,圖G(V, E)是多重圖,連通圖,10.2 樹（tree）,一、樹的定義,樹：一個無圈的連通圖稱為樹。,例：紅樓夢中賈府人物之間的血統(tǒng)關(guān)系樹,賈演,賈源,賈代化,賈代善,賈放,賈敷,賈珍,賈蓉,賈赦,賈政,賈璉,賈寶玉,賈環(huán),賈珠,賈蘭,（寧國府）,（榮國府）,二、樹的性質(zhì),1 設(shè)圖G(V, E)是一個樹，點數(shù)P(G) 2，則 G 中至少有兩個懸掛點。,2 圖G(V，E)是一個樹G不含圈，且恰有p-1條邊（p是點數(shù)）。,3 圖G(V，E)一個樹 G 是連通圖，且q(G)p(G)1 （q是邊數(shù)）。,4 圖G(V，E)是樹 任意兩個頂點之間恰有一條鏈。,圖的支撐樹(spanning tree),1 支撐子圖：設(shè)圖G(V，E)，圖G(V，E)的VV，E E，則稱G是G的一個 支撐子圖。,2 支 撐 樹：設(shè)圖T(V，E)是圖G(V，E)的支撐子圖，如果T(V，E)是一個樹， 則稱 T 是 G 的一個支撐樹。,如何尋找 “支撐樹” 呢？, 圖G(V，E)的點集與圖G(V，E)的點集相同，VV，但圖G(V，E) 的邊集僅是圖G(V，E)的子集E E。,特點邊少、點不少。,1 最小樹定義,如果T(V，E)是 G 的一個支撐樹，稱 T 中所有邊的權(quán)之和為支撐樹T的權(quán)， 記為W（T），即：,若支撐樹T* 的權(quán)W（T*）是G的所有支撐樹的權(quán)中最小者， 則稱T* 是G 的最小 支撐樹（最小樹）， 即：W（T*） min W(T),最小樹(minimum spanning tree)問題,例8：,1） 破圈法：在圖G中任取一個圈，從圈中去掉權(quán)數(shù)最大的邊，對余下的圖重復這個 步驟， 直到G中不含圈為止，即可得到 G 的一個最小樹。,2 求最小樹的算法（minimum spanning tree algorithm）,且p5 q4,1）在圈 v1v2v3v1中去掉v1,v3,2）在圈 v2v4v3v2中去掉v2,v3,3）在圈 v2v4v5v2中去掉v2,v5,4）在圈 v3v4v5v3中去掉v3,v5,圖中已經(jīng)不含圈, 已經(jīng)求出了最小樹,W(T*)42129,避圈法是一種選邊的過程，其步驟如下：,1. 從網(wǎng)絡(luò)D中任選一點vi，找出與vi相關(guān)聯(lián)的 權(quán)最小的邊vi，vj，得第二個頂點vj；,2. 把頂點集V分為互補的兩部分V1, 1 ，其中,用避圈法解,最小部分樹如圖上紅線所示； 最小權(quán)和為14。,思考：破圈法與必避圈法各自的思路是怎樣做的呢？,見圈就破，去掉其中權(quán)最大的。 加邊取其中最小的。,例8 要在5個城市架設(shè)電話線，使城鎮(zhèn)之間能夠通話兩鎮(zhèn)直接連接，每兩個城鎮(zhèn)之 間的架設(shè)電話線的造價如下圖所示，各邊上的數(shù)字為造價（ 單位：萬元 ）。 問：應如何架線，可使總造價最小？,解：,1 破圈法：,2 避圈法：,總造價：W(T*)22112210 （萬元）,本節(jié)重點及難點,重點,難點,1 圖的概念及性質(zhì),4 樹的概念及性質(zhì),5 部分樹及最小樹,2 點的概念及性質(zhì),3 鏈的概念及性質(zhì),1 圖的概念及性質(zhì),4 部分樹及最小樹,2 點的概念及性質(zhì),3 鏈的概念及性質(zhì),10.3最短路問題,最短路問題是圖論應用的基本問題，很多實際,問題，如線路的布設(shè)、運輸安排、運輸網(wǎng)絡(luò)最小費,用流等問題,都可通過建立最短路問題模型來求解.,1) 求賦權(quán)圖中從給定點到其余頂點的最短路.,2) 求賦權(quán)圖中任意兩點間的最短路.,例 如下圖所示的單行線交通網(wǎng)，每個弧旁邊的數(shù)字表示這條單行線的長度?，F(xiàn)在有一個人要從v1出發(fā)，經(jīng)過這個交 通網(wǎng)到達v6， 要尋求總路 程最短的線 路。,最短路徑問題,2) 在賦權(quán)圖G中，從頂點u到頂點v的具有最小權(quán),定義 1) 若H是賦權(quán)圖G的一個子圖，則稱H的各,邊的權(quán)和 為H的權(quán). 類似地，若,稱為路P的權(quán),若P(u,v)是賦權(quán)圖G中從u到v的路,稱,的路P*(u,v)，稱為u到v的最短路,3) 把賦權(quán)圖G中一條路的權(quán)稱為它的長，把(u,v),路的最小權(quán)稱為u和v之間的距離，并記作 d(u,v).,給定一個賦權(quán)有向圖D ( V，A ) ,對每一條弧aijw (vi，vj)，相應地有權(quán)w (aij )= wij ，又有兩點vs、vt V,設(shè) p 是 D 中從vs 到vt 的一條路，路 p 的權(quán)是 p 中所有弧的權(quán)之和,記為w(p)最短路問題就是求從vs 到vt 的路中一條權(quán)最小的路 p*:,最短路徑問題,10.3 最短路徑問題,下面僅介紹在一個賦權(quán)有向圖中尋求最短路的方法雙標號法（Dijkstra算法），它是在1959年提出來的。目前公認，在所有的權(quán)wij 0時，這個算法是尋求最短路問題最好的算法。并且，這個算法實際上也給出了尋求從一個始定點vs到任意一個點vj的最短路。,二、最短路問題的算法,方法：標號法（Dijkstra，1959） 給每點vj標號dj，vi。 其中dj為v1至vj的最短距，vi為最短路上Vj的前一點。,標號法步驟：,例 求v1到v6的最短路。, 4，V2 5，V1, 5，V3, 3，V1, 7，V5 9，V2 8，V3, 10，V4 11，V5,（1）首先將v1賦給VS。給V1以P標號，d(v1)0，vs=V1 （2）考察V1的關(guān)聯(lián)邊，選最小權(quán)的邊的端點加以標號, 0,V1,10.3 最短路徑問題,用標號法解例3,0，v1,2，v1,3，v1,其中2=min0+2,0+5,0+3,4，v2,7，v3,8，v5,13，v6,最短距為13；,4，v4,最短路有2條為v1-v2-v3-v5-v6-v7 和v1-v4-v3-v5-v6-v7。,最短路問題的應用例子,某汽車公司正在制訂5年內(nèi)購買汽車的計劃。下面給出一輛新汽車的價格以及一輛汽車的使用維修費用(萬元)： 年號 1 2 3 4 5 價格 2 2.1 2.3 2.4 2.6 汽車使用年齡 01 12 23 34 45 維修費用 0.7 1.1 1.5 2 2.5 試用網(wǎng)絡(luò)分析中求最短路的方法確定公司可采用的最優(yōu)策略。,方法：以年號作頂點繪圖，連線表示連續(xù)使用期間，以 費用作路長。,1,3,4,5,6,2,2.7,3.8,5.3,7.3,9.8,2.8,7.4,3.9,5.4,3.1,3.3,4.2,3.0,4.1,5.6,2.7, 1,3.8, 1,7.9, 3,9.4, 3,5.3, 1,P284 10.4（a）10.7,作 業(yè),10.4 最大流問題,流量問題在實際中是一種常見的問題。如公路系統(tǒng)中有車輛流量問題，供電系統(tǒng)中有電流量問題等等。最大流問題是在單位時間內(nèi)安排一個運送方案，將發(fā)點的物質(zhì)沿著弧的方向運送到收點，使總運輸量最大。,網(wǎng)絡(luò)賦權(quán)圖，記D=（V，E，C），其中C=c1，cn， ci為邊ei上的權(quán)（設(shè)ci ）。 網(wǎng)絡(luò)分析主要內(nèi)容最小部分樹、最短路、最大流。,1. 問題 已知網(wǎng)絡(luò)D=（V，A，C），其中V為頂點 集，A為弧集，C=cij為容量集， cij 為?。╲i，vj ） 上的容量?，F(xiàn)D上要通過一個流f=fij，其中fij 為弧 （vi，vj ）上的流量。問應如何安排流量fij可使D上 通過的總流量v最大？,2. 數(shù)學模型,（容量約束） （平衡條件）,問題：最大流問題的決策變量、目標函數(shù)、約束條件各是什么？,3. 基本概念與定理,如：在前面例舉的網(wǎng)絡(luò)流問題中，若已給定一個可行流（如括號中后一個數(shù)字所示），請指出相應的弧的類型。,（2）可增值鏈（增廣鏈）,（3） 截集與截量,截量：截集上的容量和，記為 。,例4 對于下圖，若V1=vs，v1，請指出相應的截集與截量。,例4 對于下圖，若V1=vs，v1，請指出相應的截集與截量。,解：,（4） 流量與截量的關(guān)系,截集上的流量和,相應于截 集的反向 弧上流量和,最大流最小割定理：,4. 解法,（5） 最大流的判別條件,步驟：,例5 用標號法求下面網(wǎng)絡(luò)的最大流。,解：第一次標號及所得可增值鏈如圖，調(diào)量 =1，調(diào)后進行第二次標號如圖。第二次標號未進行到底，得最大流如圖，最大流量v=5，同時得最小截,最大流問題的應用例子（1）,汽車由A城通往B城的可能的路線如下圖所示。環(huán)境保護部門擬建立足夠數(shù)量的汽車尾氣檢查站，以便使每輛汽車至少必須經(jīng)過一個檢查站。建立檢查站的費用根據(jù)各路段的條件而有所不同(如圖上數(shù)字所示)。若求這個問題的最小費用解，可使用 模型。 a. 最短路模型； b.最大流模型； c.最小支撐樹模型,A,a,c,b,d,e,f,g,B,8,2,4,4,5,2,6,4,3,3,6,7,3,7,8,某汽車公司有兩家汽車配件制造廠A和B，負責向兩個服務(wù)配送中心C和D供應汽車配件。運送的道路網(wǎng)絡(luò)及各路段的允許通過容量如下圖所示。假設(shè)配件廠的供應量無限制。求向C、D的供應量最大的運送方案和相應的最大供應量。,求解：最大流模型,100,200,60,160,最大流問題的應用例子（2）,100,200,60,160,1。確定從s到t的可行流（觀測法）,60,160,70,80,10,20,40,30,30,60,60,30,40,70,30,30,20,40,80,140,2。確定從s到t的最小割（截集） 標號集s,A,B，2，4 未標號集1,3,5,6,7,c,D,t,割集: (a,1)(2,6)(b,3)(4,7) 割量：60+60+70+30=220,此時已找到最大流，即此可行流就是最佳的運送方案。C、D的供應量分別為60和160,P285 11.12,作 業(yè),某個城市的街道圖如下圖，圖上數(shù)字為道路的最大通行能力。求從S到T的最大流，如果要提高S到T的車流量，應首先改擴哪幾條道路？,Thank You !,