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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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