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

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