【正文】 需要考慮圖中各邊的權(quán)值。 ? ? 消除奇點(diǎn)方法 1 消除奇點(diǎn)方法 2 重復(fù)邊 消除奇點(diǎn)方法 3 能消除奇點(diǎn)的方案很多，何為最佳？ 求解思路： 在含有奇點(diǎn)的賦權(quán)連通圖中，增加一些邊，使得在新得到的圖中不含奇點(diǎn)，并且使得增加邊的權(quán)值總和最小。 21 167。 1 圖的基本概念 三、中國(guó)郵路問(wèn)題 4．中國(guó)郵路問(wèn)題的求解方法 （ 1）增加邊的確定方法 －奇偶點(diǎn)作業(yè)法 關(guān)鍵步驟： （ 1） 如何增加邊，使圖不含奇點(diǎn)？ （ 2） 如何判斷增加邊的總權(quán)值最??？ 22 167。 1 圖的基本概念 三、中國(guó)郵路問(wèn)題 4．中國(guó)郵路問(wèn)題的求解方法 （ 2）最小權(quán)值增加邊的確定方法 （ 1）增加邊的確定方法 （ i） 增加邊必須是重復(fù)邊 （ ii） 增加邊必須能消除奇點(diǎn) 由于是連通圖，奇點(diǎn)之間必存在鏈 奇點(diǎn)之間的鏈不止一條 在鏈上增加重復(fù)邊，可滿(mǎn)足要求 既無(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)） 23 167。 1 圖的基本概念 三、中國(guó)郵路問(wèn)題 4．中國(guó)郵路問(wèn)題的求解方法 圈條件圖示 （ 2）最小權(quán)值增加邊的確定方法 定理 35（最小權(quán)值增加邊的充要條件） 設(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)值的一半。 24 167。 1 圖的基本概念 三、中國(guó)郵路問(wèn)題 4．中國(guó)郵路問(wèn)題的求解方法 5．奇偶點(diǎn)圖上作業(yè)法的步驟 圈條件圖示說(shuō)明： w2 w1 ? ?，211 21 ??若 ? ?212 21 ??則必有25 167。 1 圖的基本概念 三、中國(guó)郵路問(wèn)題 5．奇偶點(diǎn)圖上作業(yè)法的步驟 例 33 5．奇偶點(diǎn)圖上作業(yè)法的步驟 ： （ 1） 找奇點(diǎn)，確定初始增加邊。在每?jī)蓚€(gè)奇點(diǎn)間找一條鏈，在鏈經(jīng)過(guò)的所有邊上都增加一條邊。 （ 2） 檢驗(yàn)定理 35的兩個(gè)條件是否滿(mǎn)足，若滿(mǎn)足則停止求解過(guò)程，否則轉(zhuǎn)入第 3步。 （ 3） 調(diào)整增加邊。 若某邊不滿(mǎn)足邊條件 ： 則從該條邊上去掉偶數(shù)條增加邊，以保證圖中頂點(diǎn)仍全部是偶點(diǎn)； 若某圈不滿(mǎn)足圈條件 ： 則將這個(gè)圈上的增加邊去掉，將該圈的其余邊上增加邊，并轉(zhuǎn)回到第 2步。 26 167。 1 圖的基本概念 三、中國(guó)郵路問(wèn)題 例 3－ 3 四、子圖和樹(shù) 例 33 求圖 37（ a）的最優(yōu)郵遞員路線(xiàn)。 v1 v6 v7 v8 v9 v2 v3 v4 v5 4 9 4 6 4 2 5 5 3 4 4 3 解： 不滿(mǎn)足 不滿(mǎn)足 （ 4）再檢驗(yàn) 點(diǎn)擊，再選一個(gè)圈 點(diǎn)擊，顯示“不滿(mǎn)足” （ 5）再調(diào)整增加邊 點(diǎn)擊，顯示新增加邊，點(diǎn)擊，刪除舊增加邊 （ 6）再檢驗(yàn) 全部 13個(gè)圈均滿(mǎn)足圈條件。最優(yōu)路線(xiàn)總權(quán)值 53+15＝ 68 （ 1）難點(diǎn)（圈檢驗(yàn)） （ 2）找最優(yōu)路線(xiàn) （ 1）找奇點(diǎn) 初始增加邊總權(quán)值： 21 點(diǎn)擊，顯示奇點(diǎn) 點(diǎn)擊，顯示增加邊 確定初始增加邊 （ 2）檢驗(yàn) 邊條件 圈條件 滿(mǎ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) 邊條件 圈條件 （ 3）調(diào)整增加邊 （ 1）不同要求選用不同最短路線(xiàn)方法 （ 2）邊權(quán)如為時(shí)間、成本等，則 …… （ 3）研究思路很重要 27 167。 1 圖的基本概念 167。 1 圖的基本概念 一、圖、連通圖、賦權(quán)圖 二、一筆畫(huà)問(wèn)題 三、中國(guó)郵路問(wèn)題 四、子圖和樹(shù) 四、子圖和樹(shù) 28 167。 1 圖的基本概念 四、子圖和樹(shù) 子圖圖示 4. 子圖和樹(shù) 1. 子圖 （ 1）定義 39（子圖） 當(dāng)尋找一個(gè)圖中的一部分符合某些條件時(shí)，即涉及到子圖 最簡(jiǎn)單的圖為樹(shù)，既連通，邊數(shù)也最少 對(duì)于兩個(gè)圖 ? ?EVG ，? 和 ? ?EVG ???? ，如果有 VV ?? ，EE ?? ，則稱(chēng) G ? 是 G 的子圖。 即子圖的全部或部分頂點(diǎn)和邊都被原圖包含 （ 2）兩種重要的子圖 （ i）部分圖 對(duì)于兩個(gè)圖 ? ?EVG ，? 和 ? ?EVG ???? ，如果有VV ?? ， EE ?? ，則稱(chēng) G ? 是 G 的 部分 圖。 全部頂點(diǎn)，部分邊 （ ii）真子圖 對(duì)于兩個(gè)圖 ? ?EVG ，? 和 ? ?EVG ???? ，如果有VV ?? ， EE ?? ，則稱(chēng) G ? 是 G 的 真 子圖。 部分頂點(diǎn)，部分邊 29 167。 1 圖的基本概念 四、子圖和樹(shù) 2. 樹(shù) v4 v1 v2 v3 v5 (a) 圖 G v4 v1 v2 v3 v5 v4 v1 v2 v5 (b) 圖 G一個(gè)部分圖 (c) 圖 G的一個(gè)真子圖 30 167。 1 圖的基本概念 四、子圖和樹(shù) 2. 樹(shù) 樹(shù)的定義 2. 樹(shù) 例 34 分析： （ 1）必須是連通圖 因要求任意兩個(gè)城市之間均能互相通話(huà) 如含圈，則從圈上去掉一條邊，仍連通 在 6個(gè)城市 v1， v2， … ， v6之間架設(shè)電話(huà)線(xiàn)，要求任意兩個(gè)城市之間均能互相通話(huà)，試說(shuō)明對(duì)代表這個(gè)電話(huà)網(wǎng)的圖有什么要求。 （ 2）必須不含圈 滿(mǎn)足例 34要求的圖 v1 v2 v3 v4 v5 v6 特點(diǎn)： 不含圈的連通圖 31 167。 1 圖的基本概念 四、子圖和樹(shù) 2. 樹(shù) 關(guān)于樹(shù)的定理 （ 1） 樹(shù)的定義 定義 310（樹(shù)） 一個(gè)無(wú)圈的連通圖稱(chēng)為樹(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ù)最少的連通圖。 32 167。 1 圖的基本概念 四、子圖和樹(shù) 2. 樹(shù) 關(guān)于樹(shù)的定理 關(guān)于樹(shù)的定理 定理 36（頂點(diǎn)數(shù)與邊數(shù)的關(guān)系） 證明： 該性質(zhì)說(shuō)明，在點(diǎn)集合相同的圖中，樹(shù)是邊數(shù)最少的連通圖。 設(shè)樹(shù) T的頂點(diǎn)數(shù)為 P，則其邊數(shù)為 P1。 使用歸納法證明。 （ 1） 對(duì)于 P＝ 2，定理顯然成立。 （ 1） 設(shè) P＝ k時(shí)定理為真（即邊數(shù)為 k1 ），證明 P＝ k ＋ 1時(shí)定理成立 33 167。 1 圖的基本概念 四、子圖和樹(shù) 2. 樹(shù) 3． 圖的部分樹(shù) v1 v2 v3 v4 v5 v6 P＝ k ＋ 1，邊數(shù)？ v1 v2 v3 v4 v5 v6 去掉一條邊（邊數(shù)？） 端點(diǎn)重合 P＝ k， 邊數(shù)？ （由假設(shè)， k1） 邊數(shù) k1+1＝ k 新圖： 原圖： 34 167。 1 圖的基本概念 四、子圖和樹(shù) 3．圖的部分樹(shù) （ 2）求連通圖部分樹(shù)的方法 3. 圖的部分樹(shù) 例 35 圖中所示頂點(diǎn) v1， v2， … ， v9代表 9個(gè)城市，頂點(diǎn)之間的連線(xiàn)表示電話(huà)線(xiàn)架設(shè)的允許路線(xiàn)。要求任何兩個(gè)城市之間都可以彼此通話(huà)（允許通過(guò)其它城市），并且電話(huà)線(xiàn)的根數(shù)最少，問(wèn)滿(mǎn)足要求的應(yīng)是什么圖？ （ 1）定義 如果圖 ? ?EVG ，? 的部分圖 ? ?EVG ???? ，是樹(shù)，則 G ? 稱(chēng)為 G 的部分樹(shù)。 部分樹(shù)的用途很廣，因?yàn)樗前瑘D的所有頂點(diǎn)，但邊數(shù)最少的連通圖。 v1 v6 v7 v8 v9 v2 v3 v4 v5 分析： （ 1） 必須是原圖的部分圖 （ 2） 必須是連通圖 （ 3） 必須無(wú)圈（如有圈，則有多余的邊） （ 4） 結(jié)果：必須是原圖的部分樹(shù) 35 167。 1 圖的基本概念 四、子圖和樹(shù) 3．圖的部分樹(shù) （ 2）求連通圖部分樹(shù)的方法 例 36 求部分樹(shù)（避圈法） （ 2）求連通圖部分樹(shù)的方法 （ i）避圈法 先去掉圖 G的所有邊，只留下點(diǎn)，然后每次任意放回一條邊，但應(yīng)使其與已經(jīng)放回的邊不構(gòu)成圈（避圈），反復(fù)進(jìn)行，直到進(jìn)行不下去為止（即繼續(xù)放回任何邊，都將構(gòu)成圈）。 （ ii）破圈法 在圖 G中任取一個(gè)圈，去掉圈上任意一條邊（破圈）。然后再取另一個(gè)圈，并破圈，直到圖中沒(méi)有圈為止。 36 167。 1 圖的基本概念 四、子圖和樹(shù) 3．圖的部分樹(shù) （ 2）求連通圖部分樹(shù)的方法 例 36 求部分樹(shù)（破圈法） 例 36 解： 用避圈法求圖 312的一個(gè)部分樹(shù)。 v1 v6 v7 v8 v9 v2 v3 v4 v5 v1 v6 v7 v8 v9 v2 v3 v4 v5 （ 1） 按原圖位置標(biāo)出所有點(diǎn) （ 2） 任意放一條邊 （ 3） 依次放入其他邊，注意避免形成圈 問(wèn)題： 避圈法求得的圖的部分樹(shù)唯一？ 37 v1 v6 v7 v8 v9 v2 v3 v4 v5 167。 1 圖的基本概念 四、子圖和樹(shù) 3．圖的部分樹(shù) （ 2）求連通圖部分樹(shù)的方法 4. 最小部分樹(shù) 例 37 解： 用破圈法求圖 312的一個(gè)部分樹(shù)。 v1 v6 v7 v8 v9 v2 v3 v4 v5 （ 1） 任意選一個(gè)圈 （ 2） 任意去一條邊 （ 3） 依次選其他圈，并破圈，直至無(wú)圈可破 問(wèn)題： 破圈法求得的圖的部分樹(shù)唯一？ 有時(shí)只考慮邊數(shù)最少還不夠，還需要考慮總權(quán)值最小，這時(shí)應(yīng)求最小部分樹(shù) 38 167。 1 圖的基本概念 四、子圖和樹(shù) 4．最小部分樹(shù) (2) 求賦權(quán)連通圖的最小部分樹(shù)的方法 4. 最小部分樹(shù) （ 1）最小部分樹(shù)的定義 定義 312 對(duì)于賦權(quán)連通圖 G，其所有部分樹(shù)中總權(quán)值最小的部分樹(shù)，稱(chēng)為圖 G的最小部分樹(shù)（或稱(chēng)最小樹(shù)），記作 T*，即 ? ? ? ?? ?TWm i nTW * ?39 167。 1 圖的基本概念 四、子圖和樹(shù) 4．最小部分樹(shù) (2) 求賦權(quán)連通圖的最小部分樹(shù)的方法 167。 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)參考教材例 38 在一個(gè)賦權(quán)連通圖中，可能存在權(quán)值相等且最小的若干部分樹(shù)，所以最小部分樹(shù)可能不是唯一的。 40 主要內(nèi)容 167。 2 有向圖 第三章 圖與網(wǎng)絡(luò)分析 167。 1 圖的基本概念 一、圖、連通圖、賦權(quán)圖 二、一筆畫(huà)問(wèn)題 三、中國(guó)郵路問(wèn)題 四、子圖和樹(shù) 167。 2 有向圖 167。 4 最短路問(wèn)題 167。 3 圖的矩陣表示 41 167。 2 有向圖 有向圖的定義、基礎(chǔ)圖 有向圖的環(huán)、鏈、路 167。 2 有向圖 在前面討論的圖及賦權(quán)圖中，涉及到的邊都是無(wú)方向性的，即 [u，v]=[v， u]，這種圖稱(chēng)為無(wú)向圖及賦權(quán)無(wú)向圖。但在圖論的應(yīng)