【正文】 11 λ = v4 T =13 8 P = T =13 λ = v6 或 v7 167。 4 最短路問題 二、最短路算法 （ 2） Dijkstra算法的求解步驟 例 314 為什么只能將最小 T標(biāo)號的頂點改為 P標(biāo)號？ 至于與 P標(biāo)號頂點不直接相鄰的其他頂點 ， 其最短路更無法確定 。 4 最短路問題 二、最短路算法 （ 2） Dijkstra算法的求解步驟 最小 T標(biāo)號改 P標(biāo)號的解釋 （ i） （ 2） Dijkstra算法的求解步驟 為始點 1v 標(biāo) P 標(biāo)號 ? ? 01 ?vP ，其余頂點均標(biāo) T 標(biāo)號? ? ???jvT 。 v6 v1 v2 v3 v4 v5 v7 v8 3 7 7 6 1 6 2 2 1 4 3 (1)16?58 ? 以 ? 標(biāo)出從始點 1v 到0jv的最短路上與0jv相鄰的點，用于反求最短路線。 57 167。當(dāng)所有頂點均為 P標(biāo)號時，算法結(jié)束。 凡是得到 P標(biāo)號的頂點，說明已經(jīng)求出 v1到該點的最短路及最短路權(quán)值，其標(biāo)號不再改變 。 4 最短路問題 二、最短路算法 標(biāo)號介紹 算法依據(jù)圖示 T標(biāo)號 T（ vj） : P標(biāo)號 P（ vj） : 其值表示從始點 v1到 vj的最短路總權(quán)值的上界，稱為臨時標(biāo)號。 56 其值表示從始點 v1到 vj的最短路的總權(quán)值，稱為固定標(biāo)號。這個算法不僅能給出從始點到終點的最短路，而且在求解過程中，實際還給出了從始點到圖中任意一點的最短路。 4 最短路問題 二、最短路算法 標(biāo)號介紹 二、最短路算法 兩種情況： 1. 所有弧權(quán)為正－狄克斯特拉（ Dijkstra）算法 2. 存在負(fù)弧權(quán)情況（自學(xué)） Dijkstra算法又稱標(biāo)號法，由 E. W. Dijkstra于 1959年首先提出。 最短路問題不總是與距離有關(guān)的，也可以與時間、成本、流量、效率等有關(guān)，所以應(yīng)用十分廣泛。 4 最短路問題 一 、 定義 二、最短路算法 定義 317（最短路問題） 在賦權(quán)有向圖中，求兩個頂點 1v 到 nv 之間的一條路 *? ，使得這條路上各弧的權(quán)值總和在從1v到nv之間的所有路中是最小的，即： ? ? ? ?? ?n* n Wm i nW 11 ?? ?這種問題稱為最短路問題。 分析： 顯然，在所給路線范圍之內(nèi)，從油田到煉油廠的鋪設(shè)方案不止一個，且鋪設(shè)路線長度不同，問題的要求是求鋪設(shè)路線長度最短的方案。 4 最短路問題 一 、 定義 定義 167。 4 最短路問題 167。 1 圖的基本概念 一、圖、連通圖、賦權(quán)圖 二、一筆畫問題 三、中國郵路問題 四、子圖和樹 167。 52 主要內(nèi)容 167。 4 最短路問題 無向圖 v1 v2 v3 v4 e1 e2 e3 e4 e6 e5 無向圖的關(guān)聯(lián)矩陣 ????不關(guān)聯(lián)與邊若頂點關(guān)聯(lián)與邊若頂點jijiij evevs01?????????????0101101000111110000011014321654321vvvvSeeeeee顯然，圖的邊（?。┚仃囆问缴献詈唵危珗D的鄰接矩陣和關(guān)聯(lián)矩陣在連通性判斷和某些優(yōu)化計算中更具實用價值。 3 圖的矩陣表示 三、關(guān)聯(lián)矩陣 關(guān)聯(lián)矩陣（無向圖 例） 有向圖 ? ????????的端點不是其它情況流入的矢量向頂點若弧流出的矢量從頂點若弧jiijijijavvavas011v1 v2 v3 v4 a1 a2 a3 a4 a6 a5 ???????????????????0101101000111110000011014321654321vvvvSaaaaaa有向圖的關(guān)聯(lián)矩陣 51 167。 鄰接矩陣 49 167。 3 圖的矩陣表示 二、鄰接矩陣 鄰接矩陣（例） （ 3）對于賦權(quán)有向圖 D ： （ 4）對于賦權(quán)無向圖 G： ? ?? ?????? 的一條弧不是若的一條弧，且權(quán)值為是若Dv，vwDv，vwajiijjiijij? ?? ?????? 的一條邊不是若的一條邊，且權(quán)值為是若Dv，vwDv，vwajiijjiijij48 167。本章求含負(fù)權(quán)弧網(wǎng)絡(luò)最短路時須使用 （弧矩陣） 46 167。 3 圖的矩陣表示 定義 314（邊矩陣、弧矩陣） 設(shè)矩陣的行數(shù)為圖的邊（?。?shù)，列數(shù)為 2，每行對應(yīng)于圖的一條邊（弧），每行的兩個元素為邊（?。┑亩它c編號（對于有向圖 ，規(guī)定第一列元素為弧的始點編號，第二列元素為弧的終點編號），這樣的矩陣稱為圖的邊（?。┚仃嚒?3 圖的矩陣表示 45 167。 2 有向圖 167。 3 圖的矩陣表示 第三章 圖與網(wǎng)絡(luò)分析 167。 3 圖的矩陣表示 v1 v2 v3 v4 v5 a1 a2 a3 a4 a6 a7 a5 鏈？ 路？ √ 鏈？ 路？ √ 鏈、路圖示 圖的矩陣表示的用途 （ 1）對于復(fù)雜的圖， 用矩陣描述簡單；（ 2）將優(yōu)化算法在計算機(jī)上實現(xiàn)時，必須將圖用矩陣來表示（如前述中國郵路問題）。 43 167。對于一條鏈，其各弧的方向與鏈的方向不一定一致；而對于路，其各弧的方向與路的方向一定是一致的。 設(shè) ? ?12211 ??nnn iiiiiiivavavav ， ?? 為有向圖 D 的一條鏈，如果滿足 ? ?1??ttt iiivva ，則稱此鏈為從點1iv 到1?niv 的一條路。規(guī)定環(huán)不標(biāo)方向。 42 167。 定義 313 對于點集 V （非空）和弧集 A ，如果任一弧 Aa ? 對應(yīng)于一個 有序 點對 ? ?vu ， ， 其中 u 、 v 分別為弧 a 的始點和終點 ，則 點集 V 與弧集 A 的和集稱為有向圖，記作? ?AVD ，? 。例如，城市道路系統(tǒng)中的單行道、直流電路等；另一方面，有些關(guān)系僅用無方向性的邊是反映不出來的，例如，一項工程中各工序之間的先后關(guān)系、競賽中的勝負(fù)關(guān)系等。但在圖論的應(yīng)用中，經(jīng)常遇到的情況是，不僅需要畫出描述問題的圖，而且需要指出圖中每一條邊的方向。 2 有向圖 有向圖的定義、基礎(chǔ)圖 有向圖的環(huán)、鏈、路 167。 4 最短路問題 167。 1 圖的基本概念 一、圖、連通圖、賦權(quán)圖 二、一筆畫問題 三、中國郵路問題 四、子圖和樹 167。 40 主要內(nèi)容 167。然后再取另一個圈，并破圈，直到圖中沒有圈為止。 2 有向圖 （ 2） 求賦權(quán)連通圖的最小部分樹的方法 （ i）避圈法 先去掉圖 G的所有邊，只留下點，然后每次放回一條與已經(jīng)放回的邊不構(gòu)成圈（避圈）且權(quán)值最小的邊，反復(fù)進(jìn)行，直到進(jìn)行不下去為止（即繼續(xù)放回任何邊，都將構(gòu)成圈）。 1 圖的基本概念 四、子圖和樹 4．最小部分樹 (2) 求賦權(quán)連通圖的最小部分樹的方法 4. 最小部分樹 （ 1）最小部分樹的定義 定義 312 對于賦權(quán)連通圖 G，其所有部分樹中總權(quán)值最小的部分樹，稱為圖 G的最小部分樹（或稱最小樹），記作 T*，即 ? ? ? ?? ?TWm i nTW * ?39 167。 1 圖的基本概念 四、子圖和樹 3．圖的部分樹 （ 2）求連通圖部分樹的方法 4. 最小部分樹 例 37 解： 用破圈法求圖 312的一個部分樹。 1 圖的基本概念 四、子圖和樹 3．圖的部分樹 （ 2）求連通圖部分樹的方法 例 36 求部分樹（破圈法） 例 36 解： 用避圈法求圖 312的一個部分樹。然后再取另一個圈，并破圈，直到圖中沒有圈為止。 1 圖的基本概念 四、子圖和樹 3．圖的部分樹 （ 2）求連通圖部分樹的方法 例 36 求部分樹（避圈法） （ 2）求連通圖部分樹的方法 （ i）避圈法 先去掉圖 G的所有邊，只留下點，然后每次任意放回一條邊，但應(yīng)使其與已經(jīng)放回的邊不構(gòu)成圈（避圈），反復(fù)進(jìn)行，直到進(jìn)行不下去為止（即繼續(xù)放回任何邊，都將構(gòu)成圈）。 部分樹的用途很廣，因為它是包含圖的所有頂點，但邊數(shù)最少的連通圖。 1 圖的基本概念 四、子圖和樹 3．圖的部分樹 （ 2）求連通圖部分樹的方法 3. 圖的部分樹 例 35 圖中所示頂點 v1， v2， … ， v9代表 9個城市，頂點之間的連線表示電話線架設(shè)的允許路線。 （ 1） 設(shè) P＝ k時定理為真（即邊數(shù)為 k1 ），證明 P＝ k ＋ 1時定理成立 33 167。 使用歸納法證明。 1 圖的基本概念 四、子圖和樹 2. 樹 關(guān)于樹的定理 關(guān)于樹的定理 定理 36（頂點數(shù)與邊數(shù)的關(guān)系） 證明： 該性質(zhì)說明，在點集合相同的圖中，樹是邊數(shù)最少的連通圖。 由性質(zhì) 1, 樹中任一條邊是連接該邊兩個端點的唯一的一條鏈，所以去掉這條邊后，其兩個端點不再連通， 由該性質(zhì) , 樹中任一條邊是連接該邊兩個端點的唯一的一條鏈， 該性質(zhì)說明，在點集合相同的圖中，樹是邊數(shù)最少的連通圖。 又，如果兩點之間有兩條不同的鏈，則必有圈，這與樹的定義相矛盾。 1 圖的基本概念 四、子圖和樹 2. 樹 關(guān)于樹的定理 （ 1） 樹的定義 定義 310（樹） 一個無圈的連通圖稱為樹，記作 T （ 2） 樹的性質(zhì) 性質(zhì) 1 樹中任意兩點之間，有且僅有一條鏈。 1 圖的基本概念 四、子圖和樹 2. 樹 樹的定義 2. 樹 例 34 分析： （ 1）必須是連通圖 因要求任意兩個城市之間均能互相通話 如含圈，則從圈上去掉一條邊，仍連通 在 6個城市 v1， v2， … ， v6之間架設(shè)電話線，要求任意兩個城市之間均能互相通話，試說明對代表這個電話網(wǎng)的圖有什么要求。 部分頂點，部分邊 29 167。 即子圖的全部或部分頂點和邊都被原圖包含 （ 2）兩種重要的子圖 （ i）部分圖 對于兩個圖 ? ?EVG ，? 和 ? ?EVG ???? ，如果有VV ?? ， EE ?? ，則稱 G ? 是 G 的 部分 圖。 1 圖的基本概念 一、圖、連通圖、賦權(quán)圖 二、一筆畫問題 三、中國郵路問題 四、子圖和樹 四、子圖和樹 28 167。最優(yōu)路線總權(quán)值 53+15＝ 68 （ 1）難點（圈檢驗） （ 2）找最優(yōu)路線 （ 1）找奇點 初始增加邊總權(quán)值： 21 點擊，顯示奇點 點擊，顯示增加邊 確定初始增加邊 （ 2）檢驗 邊條件 圈條件 滿足 先選擇一個圈，點擊 （ 3）調(diào)整增加邊 調(diào)整后的增加邊總權(quán)值： 17，有所改善 （點擊） （ 4）再檢驗 （ 5）再調(diào)整增加邊 （ 6）再檢驗 （ 1）找奇點， 確定初始增加邊 （ 2）檢驗 邊條件 圈條件 （ 3）調(diào)整增加邊 （ 1）不同要求選用不同最短路線方法 （ 2）邊權(quán)如為時間、成本等，則 …… （ 3）研究思路很重要 27 167。 1 圖的基本概念 三、中國郵路問題 例 3－ 3 四、子圖和樹 例 33 求圖 37（ a）的最優(yōu)郵遞員路線。 若某邊不滿足邊條件 ： 則從該條邊上去掉偶數(shù)條增加邊，以保證圖中頂點仍全部是偶點； 若某圈不滿足圈條件 ： 則將這個圈上的增加邊去掉，將該圈的其余邊上增加邊，并轉(zhuǎn)回到第 2步。 （ 2） 檢驗定理 35的兩個條件是否滿足，若滿足則停止求解過程，否則轉(zhuǎn)入第 3步。 1 圖的基本概念 三、中國郵路問題 5．奇偶點圖上作業(yè)法的步驟 例 33 5．奇偶點圖上作業(yè)法的步驟 ： （ 1） 找奇點，確定初始增加邊。 24 167。 （邊條件） （圈條件） 定理說明： （