院校資料系統(tǒng)工程ch3PPT學(xué)習(xí)教案

1、會計學(xué)121 圖的基本概念一、圖、連通圖、賦權(quán)圖1 圖的基本概念一、圖、連通圖、賦權(quán)圖二、一筆畫問題三、中國郵路問題四、子圖和樹第1頁/共77頁31 圖的基本概念概述蘭德公司簡介概述（1）由來生產(chǎn)實際中的許多問題雖然多屬于不同領(lǐng)域，但其中相當一部分問題都可以用圖與網(wǎng)絡(luò)的形式進行描述 （2）意義不僅本身具有重要的理論意義，更重要的是作為其它學(xué)科的公共基礎(chǔ)而被廣泛應(yīng)用 （3）應(yīng)用物理學(xué)、控制論、信息論、交通運輸、經(jīng)濟管理、計算機科學(xué)等 （4）用例項目管理、通信線路的架設(shè)、輸油管道的鋪設(shè)、公路或鐵路交通網(wǎng)絡(luò)的合理布局等 第2頁/共77頁41 圖的基本概念一、圖、連通圖、賦權(quán)圖 1. 圖圖論中的圖與幾

2、何圖形的區(qū)別一、圖、連通圖、賦權(quán)圖1. 圖與以前在數(shù)學(xué)中學(xué)的幾何圖形不完全相同哥尼斯堡七橋問題：ABCD示意圖圖論中的圖BDCe2e1e6e5e7e4e3A歐拉將此問題歸結(jié)為一個 “一筆畫”問題，并證明了是不可能的，因為圖中的每個點都與奇數(shù)條邊相關(guān)聯(lián)，不可能將這個圖不重復(fù)地一筆畫成，這是古典圖論中一個著名問題。 第3頁/共77頁51 圖的基本概念一、圖、連通圖、賦權(quán)圖 1. 圖圖的基本概念圖論中的圖與幾何圖形的區(qū)別幾何圖形：強調(diào)幾何要素（如長度、角度、面積、形狀等）的準確性（如橋的準確位置、長度、島的面積大小 ）兩個圖在圖論中完全相同圖論中的圖：不關(guān)注幾何要素的準確性，強調(diào)點的數(shù)量及點之間關(guān)系

3、的準確性（如有幾個島、島之間是否有橋、島與岸之間是否有橋以及有幾座橋） BDCe2e1e6e5e7e4e3AABCD第4頁/共77頁61 圖的基本概念一、圖、連通圖、賦權(quán)圖 1. 圖圖的基本概念（續(xù)）圖的基本概念頂點：定義3-1：ADBCe2e1e4e3e5e6端點：關(guān)聯(lián)邊：相鄰點：相鄰邊：環(huán)：通常用點表示具體的或抽象的事物，而用邊表示事物之間的某種聯(lián)系。 第5頁/共77頁71 圖的基本概念一、圖、連通圖、賦權(quán)圖 1. 圖圖的基本概念（續(xù)）圖的基本概念（續(xù)）多重圖：多重邊：ADBCe2e1e4e3e5e6簡單圖：圖的階：頂點的度：偶點：奇點：含有多重邊的圖稱為多重圖。 無環(huán)無多重邊的圖稱為簡單

4、圖。 圖中頂點的個數(shù)稱為圖的階。以v為端點的邊的條數(shù)稱為點v的度，記作 deg(v)或d(v)度為偶數(shù)的點稱為偶點。 度為奇數(shù)的點稱為奇點。 規(guī)定環(huán)計算兩次 第6頁/共77頁81 圖的基本概念一、圖、連通圖、賦權(quán)圖 1. 圖2. 連通圖圖的基本概念（續(xù)）懸掛點：孤立點：ADBCe2e1e4e3e5e6懸掛邊：度為1的點稱為懸掛點。 與懸掛點關(guān)聯(lián)的邊稱為懸掛邊。 EF度為零的點稱為孤立點。 所謂連通圖，即圖中任意兩點都能通過一系列順序相連邊通達，這一系列順序相連的邊稱為鏈。 第7頁/共77頁91 圖的基本概念一、圖、連通圖、賦權(quán)圖 2.聯(lián)通 圖3. 賦權(quán)圖2. 連通圖定義3-3（鏈、圈）：簡單鏈

5、：所有邊不重復(fù)的鏈（即各邊互不重復(fù)）。 v1v2v3v4v5v6v7即各邊順序相連以下概念也適用于圈初等鏈：所有點不重復(fù)的簡單鏈（即點邊均不重復(fù)）。 連通圖：若圖中任意兩點之間至少存在一條鏈，則圖稱為連通圖，否則稱為不連通圖。 第8頁/共77頁101 圖的基本概念一、圖、連通圖、賦權(quán)圖 3. 賦權(quán)圖二、一筆畫問題3. 賦權(quán)圖定義3-4（賦權(quán)圖）：在實際問題中，常常遇到每條邊對應(yīng)一個數(shù)量指標的情況。例如，若用邊表示線路（電線、公路、鐵路、管道等），則往往要考慮它們的長度，或相應(yīng)的運輸價格等，這時，我們需為圖的各邊給出相應(yīng)的數(shù)量指標，并稱之為“權(quán)”。 相對于非賦權(quán)圖，賦權(quán)圖在圖論的理論和應(yīng)用方面有

6、著重要的地位，賦權(quán)圖中的邊不僅表示圖中各點之間的關(guān)聯(lián)關(guān)系，而且同時表示出了各點之間的數(shù)量關(guān)系，所以賦權(quán)圖被廣泛應(yīng)用于各領(lǐng)域的最優(yōu)化問題。 定義3-5（圖的權(quán)）：圖中各條邊權(quán)的和稱為圖的權(quán)，記作 GvvijjiwGW，第9頁/共77頁111 圖的基本概念二、一筆畫問題1 圖的基本概念一、圖、連通圖、賦權(quán)圖二、一筆畫問題三、中國郵路問題四、子圖和樹第10頁/共77頁12歐拉不僅證明了哥尼斯堡問題是不可能一筆畫回到原出發(fā)點的，而且還證明了哥尼斯堡問題甚至不是可一筆畫的。為了了解歐拉的結(jié)論，我們給出下列定義及定理。 1 圖的基本概念二、一筆畫問題定義：歐拉鏈定義（可一筆畫的圖）：我們可以筆不離紙地連續(xù)

7、畫出該圖，并且各邊沒有重復(fù)，即可以“一筆畫”畫出該圖，我們稱這種圖為可一筆畫的。 如果連通圖有一條包括所有頂點，但各邊只出現(xiàn)一次的路線，則稱這個連通圖為可一筆畫的圖。 v3v4v1v2v5v3v4v1v2v5第11頁/共77頁131 圖的基本概念二、一筆畫問題哈密爾頓圖定義3-7（歐拉鏈）：經(jīng)過且僅經(jīng)過圖中每條邊一次的鏈稱為歐拉鏈。 定義3-8（歐拉圈）：經(jīng)過且僅經(jīng)過圖中每條邊一次的圈稱為歐拉圈。 定理3-1（歐拉鏈的充要條件）：連通圖含有歐拉鏈的充分必要條件是圖中奇點的個數(shù)為0或2。 定理3-2（歐拉圈的充要條件）：連通圖含有歐拉圈的充分必要條件是圖中不存在奇點。 定義3-8（歐拉圖）：含有

8、歐拉圈的圖稱為歐拉圖。 1857年，英國數(shù)學(xué)家哈密爾頓提出了一個與上述問題密切相關(guān)的問題，即一個圖是否存在這樣一條路線，該路線經(jīng)過所有頂點，且每個頂點只經(jīng)過一次？可以證明，這樣的路線必定是一個圈，稱為哈密爾頓圈。含有哈密爾頓圈的圖稱為哈密爾頓圖。 哥尼斯堡人想走過七座橋，且每座橋只能走過一次，最后回到出發(fā)點，這樣的想法是不可能實現(xiàn)的。 歐拉鏈的特點是經(jīng)過圖的所有邊，且每條邊只經(jīng)過一次，但對是否經(jīng)過所有頂點及通過各頂點的次數(shù)沒有限制。 第12頁/共77頁141 圖的基本概念二、一筆畫問題三、中國郵路問題 (1)(2)(6)(4)(3)(5)哈密爾頓圖，非歐拉圖（有奇點） 歐拉圖，非哈密爾頓圖（無

9、奇點） 既是歐拉圖又是哈密爾頓圖的圖是存在的 需要指出，我們已經(jīng)知道歐拉圖的判斷準則，即所有頂點均為偶點（或不存在奇點），但是尚沒有一個哈密爾頓圖的判斷準則。然而，哈密爾頓圖是有一定實用價值的，如與其有密切關(guān)系的“巡回售貨員問題”，即找出一條包含所有頂點的最短閉合路線（這里，城市為頂點，城市之間的距離為邊的長度）。 參考消息2010.10.26：瞬間解出“巡回售貨員問題，蜜蜂大腦擊敗電腦” 英國衛(wèi)報網(wǎng)站10.24報道。倫敦大學(xué)皇家霍洛維學(xué)院的研究小組利用電腦控制的人造花朵測試蜜蜂的行為，發(fā)現(xiàn)大腦小如草籽的蜜蜂很快能夠確定最短路線。目前電腦是通過窮比法來求解的。該問題對于依賴于交通流、互聯(lián)網(wǎng)、供

10、應(yīng)鏈的現(xiàn)代生活不無意義。第13頁/共77頁151 圖的基本概念1 圖的基本概念一、圖、連通圖、賦權(quán)圖二、一筆畫問題三、中國郵路問題四、子圖和樹三、中國郵路問題 第14頁/共77頁161 圖的基本概念三、中國郵路問題 1. 問題描述 二、 中國郵路問題郵遞員在投送報刊信件時，從郵局出發(fā)，一般每次都要走遍他所負責的全部街道，任務(wù)完成后返回郵局。那么郵遞員應(yīng)該選擇一條什么樣的路線才能以盡可能少的路程走完所有的街道呢？這個問題是我國著名運籌學(xué)家管梅谷教授于1962年首先提出的，并給出了它的解法，因此國際上稱為中國郵路問題。 在一個賦權(quán)圖上，求一個圈，該圈經(jīng)過圖中每條邊至少一次，并使圈中各邊權(quán)值的總和為

11、最小。稱經(jīng)過每條邊至少一次的圈為郵遞員路線。中國郵路問題就是求最優(yōu)的郵遞員路線。 2. 定理1. 問題描述如何理解最優(yōu)郵遞員路線？歐拉圖： 以郵局為始終點的一個歐拉圈就是最優(yōu)郵遞員路線。非歐拉圖：郵路中的某些邊必須重復(fù)，帶有重復(fù)邊且總權(quán)值最小的圈為最優(yōu)郵遞員路線。 能形成圈的重復(fù)邊方案不止一個，這時的問題是重復(fù)哪些邊最好。第15頁/共77頁171 圖的基本概念三、中國郵路問題 2. 定理 定理 3-42. 定理 因為每條邊與兩個端點相關(guān)聯(lián)，所以計算頂點的度時，每條邊均使用了兩次，所以全部頂點度的和等于邊數(shù)的兩倍。 定理3-3（頂點度之和與邊數(shù)的關(guān)系）：說明：第16頁/共77頁181 圖的基本概

12、念三、中國郵路問題 2. 定理 3中國郵路問題的求解思路 定理3-4（奇點個數(shù)奇偶性）：證明：對于任一個圖G，奇點的個數(shù)必為偶數(shù)。（偶點個數(shù)更是偶數(shù)？） （1）點集分解： 偶點集合奇點集合：21VVV（度之和為奇數(shù)？偶數(shù)？當然偶數(shù)）（度之和為奇數(shù)？偶數(shù)？取決于奇點個數(shù)的奇偶性）（2）由定理3-3： qvdvdvdVvVvVv221 212VvVvvdqvd偶數(shù) 偶數(shù)（3）由于奇點集合中所有奇點的度之和為偶數(shù)， 所以奇點集合中所有奇點的個數(shù)必為偶數(shù)。第17頁/共77頁191 圖的基本概念三、中國郵路問題 3中國郵路問題的求解思路 4中國郵路問題的求解方法 3.中國郵路問題的求解思路 兩種情況：（

13、1）不存在奇點： 為歐拉圖，以郵局為始終點的歐拉圈即為所求（2）存在奇點： 為非歐拉圖，為形成圈，必須在某些邊上重復(fù)一次或多次。此時，為了減少重復(fù)路線的長度，則需要考慮圖中各邊的權(quán)值。 ?消除奇點方法1 消除奇點方法2 重復(fù)邊 消除奇點方法3 能消除奇點的方案很多，何為最佳？求解思路：在含有奇點的賦權(quán)連通圖中，增加一些邊，使得在新得到的圖中不含奇點，并且使得增加邊的權(quán)值總和最小。 第18頁/共77頁201 圖的基本概念三、中國郵路問題 4中國郵路問題的求解方法 （1）增加邊的確定方法 4.中國郵路問題的求解方法奇偶點作業(yè)法 關(guān)鍵步驟：（1）如何增加邊，使圖不含奇點？（2）如何判斷增加邊的總權(quán)值

14、最小？第19頁/共77頁211 圖的基本概念三、中國郵路問題 4中國郵路問題的求解方法 （2）最小權(quán)值增加邊的確定方法 （1）增加邊的確定方法 （i）增加邊必須是重復(fù)邊（ii）增加邊必須能消除奇點由于是連通圖，奇點之間必存在鏈奇點之間的鏈不止一條在鏈上增加重復(fù)邊，可滿足要求既無引入新邊，也不影響原來的偶點。方案當然不止一個將奇點兩兩相連，必能消除奇點因為奇點的個數(shù)為偶數(shù)增加邊方法一增加邊方法二但不能直接相連方法一的重復(fù)邊長度不一定最短（邊權(quán)以標示為準）第20頁/共77頁221 圖的基本概念三、中國郵路問題 4中國郵路問題的求解方法 圈條件圖示 （2）最小權(quán)值增加邊的確定方法 定理3-5（最小權(quán)

15、值增加邊的充要條件）設(shè)M是使圖G不含奇點的所有增加邊集合，則M中所有增加邊權(quán)值總和為最小的充分必要條件為：（i）圖G的每條邊上最多增加一條邊；（ii）在圖G的每個圈上，增加邊的總權(quán)值不超過該圈 原總權(quán)值的一半。（邊條件）（圈條件）定理說明：（i）顯然成立（ii）如果在圖中某個圈上增加邊的總權(quán)值超過該圈原總權(quán)值的一半，則去掉該圈的增加邊，同時給該圈的其余邊加上增加邊。這樣，圖中仍不會出現(xiàn)奇點，但可使增加邊的總權(quán)值減少到不超過該圈原總權(quán)值的一半。 第21頁/共77頁231 圖的基本概念三、中國郵路問題 4中國郵路問題的求解方法 5奇偶點圖上作業(yè)法的步驟 圈條件圖示說明： w2w1，21121www

16、若21221www則必有第22頁/共77頁241 圖的基本概念三、中國郵路問題 5奇偶點圖上作業(yè)法的步驟 例 3-3 5奇偶點圖上作業(yè)法的步驟 ： （1）找奇點，確定初始增加邊。在每兩個奇點間找一條鏈，在鏈經(jīng)過的所有邊上都增加一條邊。 （2）檢驗定理3-5的兩個條件是否滿足，若滿足則停止求解過程，否則轉(zhuǎn)入第3步。 （3）調(diào)整增加邊。 若某邊不滿足邊條件 ：則從該條邊上去掉偶數(shù)條增加邊，以保證圖中頂點仍全部是偶點； 若某圈不滿足圈條件 ：則將這個圈上的增加邊去掉，將該圈的其余邊上增加邊，并轉(zhuǎn)回到第2步。 第23頁/共77頁251 圖的基本概念三、中國郵路問題 例 33 四、子圖和樹 例3-3 求

17、圖3-7（a）的最優(yōu)郵遞員路線。 v1v6v7v8v9v2v3v4v5494642553443解：不滿足不滿足（4）再檢驗點擊，再選一個圈點擊，顯示“不滿足”（5）再調(diào)整增加邊點擊，顯示新增加邊，點擊，刪除舊增加邊（6）再檢驗全部13個圈均滿足圈條件。最優(yōu)路線總權(quán)值53+15686.討論（1）難點（圈檢驗）（2）找最優(yōu)路線（1）找奇點初始增加邊總權(quán)值：21點擊，顯示奇點點擊，顯示增加邊確定初始增加邊（2）檢驗邊條件圈條件滿足先選擇一個圈，點擊（3）調(diào)整增加邊調(diào)整后的增加邊總權(quán)值：17，有所改善（點擊）（4）再檢驗（5）再調(diào)整增加邊（6）再檢驗（1）找奇點，確定初始增加邊（2）檢驗邊條件圈條件（

18、3）調(diào)整增加邊7.啟發(fā)（1）不同要求選用不同最短路線方法（2）邊權(quán)如為時間、成本等，則（3）研究思路很重要第24頁/共77頁261 圖的基本概念1 圖的基本概念一、圖、連通圖、賦權(quán)圖二、一筆畫問題三、中國郵路問題四、子圖和樹四、子圖和樹第25頁/共77頁271 圖的基本概念四、子圖和樹 子圖圖示 4. 子圖和樹 1. 子圖（1）定義3-9（子圖）當尋找一個圖中的一部分符合某些條件時，即涉及到子圖最簡單的圖為樹，既連通，邊數(shù)也最少即子圖的全部或部分頂點和邊都被原圖包含（2）兩種重要的子圖（i）部分圖全部頂點，部分邊（ii）真子圖部分頂點，部分邊第26頁/共77頁281 圖的基本概念四、子圖和樹

19、2. 樹 v4v1v2v3v5(a) 圖Gv4v1v2v3v5v4v1v2v5(b) 圖G一個部分圖一個部分圖(c) 圖G的一個真子圖的一個真子圖第27頁/共77頁291 圖的基本概念四、子圖和樹 2. 樹 樹的定義 2. 樹例3-4分析：（1）必須是連通圖因要求任意兩個城市之間均能互相通話如含圈，則從圈上去掉一條邊，仍連通在6個城市v1， v2， v6之間架設(shè)電話線，要求任意兩個城市之間均能互相通話，試說明對代表這個電話網(wǎng)的圖有什么要求。 （2）必須不含圈滿足例3-4要求的圖v1v2v3v4v5v6特點：不含圈的連通圖第28頁/共77頁301 圖的基本概念四、子圖和樹 2. 樹 關(guān)于樹的定理

20、 （1） 樹的定義定義3-10（樹）一個無圈的連通圖稱為樹，記作T （2） 樹的性質(zhì)性質(zhì)1樹中任意兩點之間，有且僅有一條鏈。 因為樹是連通的，所以任意兩點之間必存在鏈。 又，如果兩點之間有兩條不同的鏈，則必有圈，這與樹的定義相矛盾。 性質(zhì)2若樹中去掉任意一條邊，則樹成為不連通圖。 由性質(zhì)1, 樹中任一條邊是連接該邊兩個端點的唯一的一條鏈，所以去掉這條邊后，其兩個端點不再連通， 由該性質(zhì), 樹中任一條邊是連接該邊兩個端點的唯一的一條鏈， 該性質(zhì)說明，在點集合相同的圖中，樹是邊數(shù)最少的連通圖。 第29頁/共77頁311 圖的基本概念四、子圖和樹 2. 樹 關(guān)于樹的定理 關(guān)于樹的定理定理3-6（頂點

21、數(shù)與邊數(shù)的關(guān)系）證明：該性質(zhì)說明，在點集合相同的圖中，樹是邊數(shù)最少的連通圖。 設(shè)樹T的頂點數(shù)為P，則其邊數(shù)為P-1。使用歸納法證明。（1）對于P2，定理顯然成立。（1）設(shè)Pk時定理為真（即邊數(shù)為k-1 ），證明Pk 1時定理成立第30頁/共77頁321 圖的基本概念四、子圖和樹 2. 樹 3圖的部分樹 v1v2v3v4v5v6Pk 1，邊數(shù)？v1v2v3v4v5v6去掉一條邊（邊數(shù)？）端點重合Pk，邊數(shù)？（由假設(shè)，k-1） 邊數(shù)k-1+1k 新圖：原圖：第31頁/共77頁331 圖的基本概念四、子圖和樹 3圖的部分樹 （2）求連通圖部分樹的方法 3. 圖的部分樹例3-5圖中所示頂點 v1， v

22、2， v9代表9個城市，頂點之間的連線表示電話線架設(shè)的允許路線。要求任何兩個城市之間都可以彼此通話（允許通過其它城市），并且電話線的根數(shù)最少，問滿足要求的應(yīng)是什么圖？ （1）定義部分樹的用途很廣，因為它是包含圖的所有頂點，但邊數(shù)最少的連通圖。 v1v6v7v8v9v2v3v4v5分析：（1）必須是原圖的部分圖（2）必須是連通圖（3）必須無圈（如有圈，則有多余的邊）（4）結(jié)果：必須是原圖的部分樹第32頁/共77頁341 圖的基本概念四、子圖和樹 3圖的部分樹 （2）求連通圖部分樹的方法 例3-6 求部分樹（避圈法） （2）求連通圖部分樹的方法 （i）避圈法先去掉圖G的所有邊，只留下點，然后每次任

23、意放回一條邊，但應(yīng)使其與已經(jīng)放回的邊不構(gòu)成圈（避圈），反復(fù)進行，直到進行不下去為止（即繼續(xù)放回任何邊，都將構(gòu)成圈）。 （ii）破圈法在圖G中任取一個圈，去掉圈上任意一條邊（破圈）。然后再取另一個圈，并破圈，直到圖中沒有圈為止。 第33頁/共77頁351 圖的基本概念四、子圖和樹 3圖的部分樹 （2）求連通圖部分樹的方法 例3-6 求部分樹（破圈法） 例3-6 解：用避圈法求圖3-12的一個部分樹。 v1v6v7v8v9v2v3v4v5v1v6v7v8v9v2v3v4v5（1）按原圖位置標出所有點（2）任意放一條邊（3）依次放入其他邊，注意避免形成圈問題：避圈法求得的圖的部分樹唯一？第34頁/共

24、77頁36v1v6v7v8v9v2v3v4v51 圖的基本概念四、子圖和樹 3圖的部分樹 （2）求連通圖部分樹的方法 4. 最小部分樹 例3-7 解：用破圈法求圖3-12的一個部分樹。 v1v6v7v8v9v2v3v4v5v1v6v7v8v9v2v3v4v5（1）任意選一個圈（2）任意去一條邊（3）依次選其他圈，并破圈，直至無圈可破問題：破圈法求得的圖的部分樹唯一？有時只考慮邊數(shù)最少還不夠，還需要考慮總權(quán)值最小，這時應(yīng)求最小部分樹 第35頁/共77頁371 圖的基本概念四、子圖和樹 4最小部分樹(2) 求賦權(quán)連通圖的最小部分樹的方法 4. 最小部分樹（1）最小部分樹的定義定義3-12對于賦權(quán)連

25、通圖G，其所有部分樹中總權(quán)值最小的部分樹，稱為圖G的最小部分樹（或稱最小樹），記作T*，即 TWminTW*第36頁/共77頁381 圖的基本概念四、子圖和樹 4最小部分樹 (2) 求賦權(quán)連通圖的最小部分樹的方法 2 有向圖（2） 求賦權(quán)連通圖的最小部分樹的方法（i）避圈法先去掉圖G的所有邊，只留下點，然后每次放回一條與已經(jīng)放回的邊不構(gòu)成圈（避圈）且權(quán)值最小的邊，反復(fù)進行，直到進行不下去為止（即繼續(xù)放回任何邊，都將構(gòu)成圈）。 （ii）破圈法在圖G中任取一個圈，去掉圈上權(quán)值最大的一條邊（破圈）。然后再取另一個圈，并破圈，直到圖中沒有圈為止。 請參考教材例3-8在一個賦權(quán)連通圖中，可能存在權(quán)值相等

26、且最小的若干部分樹，所以最小部分樹可能不是唯一的。 第37頁/共77頁39主要內(nèi)容2 有向圖第三章 圖與網(wǎng)絡(luò)分析1 圖的基本概念一、圖、連通圖、賦權(quán)圖二、一筆畫問題三、中國郵路問題四、子圖和樹2 有向圖4 最短路問題3 圖的矩陣表示第38頁/共77頁402 有向圖有向圖的定義、基礎(chǔ)圖有向圖的環(huán)、鏈、路2 有向圖在前面討論的圖及賦權(quán)圖中，涉及到的邊都是無方向性的，即u，v=v，u，這種圖稱為無向圖及賦權(quán)無向圖。但在圖論的應(yīng)用中，經(jīng)常遇到的情況是，不僅需要畫出描述問題的圖，而且需要指出圖中每一條邊的方向。這是因為，在有些問題中，一對頂點之間的關(guān)系往往不是對稱的。例如，城市道路系統(tǒng)中的單行道、直流電

27、路等；另一方面，有些關(guān)系僅用無方向性的邊是反映不出來的，例如，一項工程中各工序之間的先后關(guān)系、競賽中的勝負關(guān)系等。 我們將點與點之間有方向的邊稱為弧，在圖上用前頭標明方向。 定義3-13基礎(chǔ)圖第39頁/共77頁412 有向圖有向圖的環(huán)、鏈、路鏈、路圖示環(huán)鏈路注意鏈與路的區(qū)別。對于一條鏈，其各弧的方向與鏈的方向不一定一致；而對于路，其各弧的方向與路的方向一定是一致的。 回路始點與終點相同的路稱為回路。 第40頁/共77頁422 有向圖有向圖的環(huán)、鏈、路3 圖的矩陣表示v1v2v3v4v5a1a2a3a4a6a7a5鏈？ 路？鏈？ 路？鏈、路圖示圖的矩陣表示的用途（1）對于復(fù)雜的圖，用矩陣描述簡單

28、；（2）將優(yōu)化算法在計算機上實現(xiàn)時，必須將圖用矩陣來表示（如前述中國郵路問題）。第41頁/共77頁43主要內(nèi)容3 圖的矩陣表示第三章 圖與網(wǎng)絡(luò)分析1 圖的基本概念一、圖、連通圖、賦權(quán)圖二、一筆畫問題三、中國郵路問題四、子圖和樹2 有向圖4 最短路問題3 圖的矩陣表示第42頁/共77頁443 圖的矩陣表示一、邊矩陣二、鄰接矩陣 一、邊矩陣（弧矩陣） 3 圖的矩陣表示定義3-14（邊矩陣、弧矩陣） 設(shè)矩陣的行數(shù)為圖的邊（?。?shù)，列數(shù)為2，每行對應(yīng)于圖的一條邊（?。?，每行的兩個元素為邊（弧）的端點編號（對于有向圖對于有向圖，規(guī)定第一列元素為弧的始點編號，第二列元素為弧的終點編號），這樣的矩陣稱為圖的

29、邊（弧）矩陣。 v1v2v3v4a1a2a3a4a6a5324212143431Ba1a2a3a4a5a6始點終點鄰接矩陣：最基本矩陣表示，可表示頂點之間的連通關(guān)系。本章求含負權(quán)弧網(wǎng)絡(luò)最短路時須使用（弧矩陣） 第43頁/共77頁453 圖的矩陣表示二、鄰接矩陣 定義（續(xù)） 二、鄰接矩陣定義3-15（鄰接矩陣） 行、列數(shù)均等于圖的頂點數(shù)，且矩陣元素aij符合下列規(guī)定的矩陣稱為圖的鄰接矩陣： （1）對于有向圖D： （2）對于無向圖G： 的一條弧不是若的一條弧是若Dv，vDv，vajijiij01的一條邊不是若的一條邊是若Dv，vDv，vajijiij01第44頁/共77頁463 圖的矩陣表示二、鄰

30、接矩陣 鄰接矩陣（例） （3）對于賦權(quán)有向圖D ：（4）對于賦權(quán)無向圖G： 的一條弧不是若的一條弧，且權(quán)值為是若Dv，vwDv，vwajiijjiijij的一條邊不是若的一條邊，且權(quán)值為是若Dv，vwDv，vwajiijjiijij第45頁/共77頁473 圖的矩陣表示二、鄰接矩陣 三、關(guān)聯(lián)矩陣 有向圖D v1v2v3v4a1a2a3a4a6a5的一條弧不是若的一條弧是若Dv，vDv，vajijiij01010100001101010043214321vvvvAvvvv關(guān)聯(lián)矩陣，也稱連接矩陣，用來表示頂點與邊的連接關(guān)系。 鄰接矩陣第46頁/共77頁483 圖的矩陣表示三、關(guān)聯(lián)矩陣 關(guān)聯(lián)矩陣（例

31、）三、關(guān)聯(lián)矩陣定義3-16（關(guān)聯(lián)矩陣） （1）對于有向圖D： （2）對于無向圖G： 的端點不是其它情況流入的矢量向頂點若弧流出的矢量從頂點若弧jiijijijavvavas011不關(guān)聯(lián)與邊若頂點關(guān)聯(lián)與邊若頂點jijiijevevs01第47頁/共77頁493 圖的矩陣表示三、關(guān)聯(lián)矩陣 關(guān)聯(lián)矩陣（無向圖 例）有向圖 的端點不是其它情況流入的矢量向頂點若弧流出的矢量從頂點若弧jiijijijavvavas011v1v2v3v4a1a2a3a4a6a50101101000111110000011014321654321vvvvSaaaaaa有向圖的關(guān)聯(lián)矩陣第48頁/共77頁503 圖的矩陣表示三、關(guān)

32、聯(lián)矩陣 4 最短路問題無向圖 v1v2v3v4e1e2e3e4e6e5無向圖的關(guān)聯(lián)矩陣不關(guān)聯(lián)與邊若頂點關(guān)聯(lián)與邊若頂點jijiijevevs010101101000111110000011014321654321vvvvSeeeeee顯然，圖的邊（?。┚仃囆问缴献詈唵?，但圖的鄰接矩陣和關(guān)聯(lián)矩陣在連通性判斷和某些優(yōu)化計算中更具實用價值。一般情況下，一個圖可由它的鄰接矩陣和關(guān)聯(lián)矩陣來完全決定。 第49頁/共77頁51主要內(nèi)容4 最短路問題第三章 圖與網(wǎng)絡(luò)分析1 圖的基本概念一、圖、連通圖、賦權(quán)圖二、一筆畫問題三、中國郵路問題四、子圖和樹2 有向圖4 最短路問題3 圖的矩陣表示第50頁/共77頁524

33、 最短路問題一、定義 定義4 最短路問題一、最短路問題的定義 v6v1v2v3v4v5v7v837761622143例3-13 從油田v1到煉油廠v8鋪設(shè)管道，管道路線限定范圍如圖3所示，弧的權(quán)代表路線長度，求使鋪設(shè)路線長度最短的方案。 分析： 顯然，在所給路線范圍之內(nèi)，從油田到煉油廠的鋪設(shè)方案不止一個，且鋪設(shè)路線長度不同，問題的要求是求鋪設(shè)路線長度最短的方案。 （對于某些經(jīng)過變形，可化為多階段決策問題的最短路問題，可用動態(tài)規(guī)劃方法求解） 第51頁/共77頁534 最短路問題一、定義 二、最短路算法定義3-17（最短路問題） n*nWminW11這種問題稱為最短路問題。 應(yīng)用舉例： 管道鋪設(shè)、

34、線路安排、廠區(qū)布局、設(shè)備更新等。 最短路問題不總是與距離有關(guān)的，也可以與時間、成本、流量、效率等有關(guān)，所以應(yīng)用十分廣泛。 第52頁/共77頁544 最短路問題二、最短路算法標號介紹二、最短路算法 兩種情況： 1. 所有弧權(quán)為正狄克斯特拉（Dijkstra）算法 2. 存在負弧權(quán)情況（自學(xué)）Dijkstra算法又稱標號法，由E. W. Dijkstra于1959年首先提出。目前公認，在所有弧的權(quán)值均為非負（即）的情況下，這個算法是尋求最短路的最好算法。這個算法不僅能給出從始點到終點的最短路，而且在求解過程中，實際還給出了從始點到圖中任意一點的最短路。 1. 所有弧權(quán)為正狄克斯特拉（Dijkstr

35、a）算法 （1） Dijkstra算法 概述從v1開始，給每一個頂點一個有值標號，標號分為T標號和P標號兩種。 第53頁/共77頁55其值表示從始點v1到vj的最短路的總權(quán)值，稱為固定標號。 4 最短路問題二、最短路算法 標號介紹算法依據(jù)圖示T標號T（vj）: P標號P（vj）: 其值表示從始點v1到vj的最短路總權(quán)值的上界，稱為臨時標號。 算法開始時，T(v1)=0, 其余T(vj)=+。 凡是得到P標號的頂點，說明已經(jīng)求出v1到該點的最短路及最短路權(quán)值，其標號不再改變 。算法目標: 逐步求出始點v1到各T標號頂點的最短路，并將其改為P標號。當所有頂點均為 P標號時，算法結(jié)束。算法依據(jù): 第

36、54頁/共77頁564 最短路問題二、最短路算法 算法依據(jù)圖示（2）Dijkstra算法的求解步驟 反證法: 說明: v6v1v2v3v4v5v7v837761622143(1)16第55頁/共77頁574 最短路問題二、最短路算法 （2）Dijkstra算法的求解步驟 最小T標號改P標號的解釋 （i） （2）Dijkstra算法的求解步驟 （ii） （iii） ijijjwvPvTminvT，舊新即現(xiàn)在vi到vj的最短路總權(quán)值上限有兩個，選小者，向最短路總權(quán)值逼近 ？（下張幻燈片解釋）如已無T標號，結(jié)束，否則轉(zhuǎn)（ii） 第56頁/共77頁584 最短路問題二、最短路算法 （2）Dijkstr

37、a算法的求解步驟 例 3-14為什么只能將最小T標號的頂點改為P標號？ 至于與P標號頂點不直接相鄰的其他頂點，其最短路更無法確定。而最小T標號頂點則一定與P標號頂點相鄰（？）。目前只能確定的最短路目前尚不能確定其最短路v1P(vi)v1vi的最短路(已求出？)vi-1viT新(vj0)（最小）T新(vj1)（次之）T新(vj2)（最大）T新T新改P？所有T標號中的最小標號第57頁/共77頁594 最短路問題二、最短路算法 例3-14例3-14 求右圖v1到v8之間的最短路 v6v1v2v3v4v5v7v837761622143解（1）列Dijkstra算法求解表。 單擊（2）填寫第一行。 單擊

38、例 3-14（續(xù)）表頭內(nèi)容為頂點名稱第58頁/共77頁60T=34 最短路問題二、最短路算法 例3-14（續(xù)）例3-14（續(xù)） v6v1v2v3v4v5v7v837761622143（3）修改v2，v4的T標號例 3-14（續(xù)） 33012122，舊新minwvPvTminvT 77014144，舊新minwvPvTminvT第59頁/共77頁614 最短路問題二、最短路算法 例3-14（續(xù)）例3-14（續(xù)） v6v1v2v3v4v5v7v837761622143（4）將v2改P標號并標路徑例 3-14（續(xù)）T=3分析：能否將v4標為P標號？ 33012122，舊新minwvPvTminvT第

39、60頁/共77頁62T=74 最短路問題二、最短路算法 例3-14（續(xù)）例3-14（續(xù)） v6v1v2v3v4v5v7v837761622143（5）例 3-14（續(xù)）修改v3，v5的T標號 107323233，舊新minwvPvTminvT 96325255，舊新minwvPvTminvT第61頁/共77頁634 最短路問題二、最短路算法 例3-14（續(xù)）例3-14（續(xù)） v6v1v2v3v4v5v7v837761622143（6）例 3-14（續(xù)）T=7分析：此次為何能將v4標為P標號？將v4改P標號并標路徑 77014144，舊新minwvPvTminvT第62頁/共77頁64 8179

40、45455minwvPvTminvT，舊新 114747477，舊新minwvPvTminvTT=84 最短路問題二、最短路算法 例3-14（續(xù)）例3-14（續(xù)） v6v1v2v3v4v5v7v837761622143（7）例 3-14（續(xù)）修改v5，v7的T標號第63頁/共77頁654 最短路問題二、最短路算法 例3-14（續(xù)）例3-14（續(xù)） v6v1v2v3v4v5v7v837761622143（8）例 3-14（續(xù)）T=8將v5改P標號并標路徑 817945455minwvPvTminvT，舊新第64頁/共77頁664 最短路問題二、最短路算法 例3-14（續(xù)）T=10例3-14（續(xù)） v6v1v2v3v4v5v7v837761622143（9）例 3-14（續(xù)）修改v6的T標號 113856566，舊新minwvPvTminvT第65頁/共77頁674 最短路問題二、最短路算法 例3-14（續(xù)）例3-14（續(xù)） v6v1v2v3v4v5v7v8