【正文】 學(xué)管理學(xué)院 ? 圖的基本概念 圖與網(wǎng)絡(luò)的基本概念 定義 8–5 設(shè) G = ( V , E ) ，對(duì)任意一條邊 e ∈ E ，如果相應(yīng)都有一個(gè)數(shù)值 w ( e )與之對(duì)應(yīng)，則稱(chēng) G 為 賦權(quán)圖 ， w ( e ) 稱(chēng)為邊 e 的 權(quán) 。 給定一個(gè)圖 G = ( V , E ) ，如果圖 G ＇ = ( V /, E ＇ ) ，使 V = V ＇及 E ＇ E? ，則稱(chēng) G ＇是 G 的一個(gè) 支撐子圖 。 若回路中的弧都互不相同，則稱(chēng)為 簡(jiǎn)單回路 ；若回路中除始點(diǎn)、終點(diǎn)外的頂點(diǎn)都互不相同，則稱(chēng)為 初等回路 。 給定一個(gè)有向圖 D = ( V , A ) ，如果 (2211 , iiii avav, ? , k1k1k , iii vav ??) 是 D中的一條鏈，并且對(duì) t = 1 , 2 , ? , k 1 ，均有 ),(1?? ttt iii vva，稱(chēng)之為從k1 ii vv 到的一條 路 。 山東理工大學(xué)管理學(xué)院 ? 圖的基本概念 圖與網(wǎng)絡(luò)的基本概念 定義 8–3 給定一個(gè)圖 G = ( V , E ) ，一個(gè)頂點(diǎn)、邊的交錯(cuò)序列 (2211 , iiii evev, ? , k1k1k , iii vev ??) ，如果滿(mǎn)足 ],[1?? ttt iii vve ( t = 1, 2, ? , k 1 ) ，則稱(chēng)為一條聯(lián)結(jié)1 , kiivv的 鏈 ，記為 (?? 21 , ii vv , ? , k1k , ii vv ? ) ； 稱(chēng)點(diǎn) 21 , ii vv , ? , 1k ?iv 為鏈的中間點(diǎn)。 如圖 山東理工大學(xué)管理學(xué)院 ? 圖的基本概念 圖與網(wǎng)絡(luò)的基本概念 定理 8–1 圖 G = ( V , E )中，所有頂點(diǎn)的次之和是邊數(shù)的兩倍。 以 iv 為端點(diǎn)的邊的條數(shù)稱(chēng)為頂點(diǎn) iv 的 次 （也叫做 度 ），記作 d ( iv ) 。 具有相同端點(diǎn)的邊稱(chēng)為 多重邊或平行邊 ；兩個(gè)端點(diǎn)落在一個(gè)頂點(diǎn)的邊稱(chēng)為 環(huán) 。 iv 稱(chēng)為 a 的始點(diǎn)，jv 稱(chēng)為 a 的終點(diǎn)。 一條連接點(diǎn) iv , jv ∈ V 的 邊 e 記為 e = [ iv , jv ] 或 e = [ jv , iv ] 。 有向圖 由點(diǎn)和弧所構(gòu)成的圖稱(chēng)為有向圖，記為 D = (V, A )， 其中V, A分別表示 D的頂點(diǎn)集合和弧集合。 v1 v4 v5 v3 v2 山東理工大學(xué)管理學(xué)院 ? 圖的基本概念 圖與網(wǎng)絡(luò)的基本概念 定義 8–1 圖 是由一些點(diǎn)及一些點(diǎn)之間的連線(xiàn)（不帶箭頭或帶箭頭）所組成。 可以用一條帶箭頭的連線(xiàn)表示。 在一般情況下，圖中點(diǎn)的相對(duì)位置如何，點(diǎn)與點(diǎn)之間連線(xiàn)的長(zhǎng)短曲直，對(duì)于反映對(duì)象之間的關(guān)系，并不是重要的。山東理工大學(xué)管理學(xué)院 圖與網(wǎng)絡(luò)的基本概念 ? 用圖來(lái)描述實(shí)際問(wèn)題 ? 圖的基本概念 ? 圖的矩陣表示 ? 小結(jié) 山東理工大學(xué)管理學(xué)院 ? 用圖來(lái)描述實(shí)際問(wèn)題 圖與網(wǎng)絡(luò)的基本概念 v 1 v 2 v 4 v 5 v 3 例 8–2 五個(gè)球隊(duì)的比賽情況： 用點(diǎn)1v,2v,3v,4v,5v分別代表這 5 個(gè)隊(duì)，某兩個(gè)隊(duì)之間比賽過(guò)，就在這兩個(gè)隊(duì)所相應(yīng)的點(diǎn)之間連一條線(xiàn)，這條線(xiàn)不 經(jīng) 過(guò)其它的點(diǎn)，如 右 圖所示。 山東理工大學(xué)管理學(xué)院 ? 用圖來(lái)描述實(shí)際問(wèn)題 圖與網(wǎng)絡(luò)的基本概念 圖是反映對(duì)象之間關(guān)系的一種工具。例如上面所說(shuō)的五個(gè)球隊(duì)的比賽情況也可以用下圖表示： 5 個(gè)球隊(duì)的比賽 山東理工大學(xué)管理學(xué)院 ? 用圖來(lái)描述實(shí)際問(wèn)題 圖與網(wǎng)絡(luò)的基本概念 如果人們關(guān)心的是 5個(gè)球隊(duì)比賽的勝負(fù)情況，那么上面的圖就表示不出來(lái)了。例如球隊(duì)1v勝了球隊(duì)2v，可以引一條帶箭頭的連線(xiàn) 1v → 2v 表示 。 無(wú)向圖 由點(diǎn)和邊所構(gòu)成的圖（也簡(jiǎn)稱(chēng)為圖），記為 G = (V, E )，其中V， E分別是 G的頂點(diǎn)集合和邊集合 。 我們把兩點(diǎn)之間的不帶箭頭的連線(xiàn)稱(chēng)為邊，帶箭頭的連線(xiàn)稱(chēng)為弧。 一條方向是從 iv 指向 jv 的 弧 a 記為 a = ( iv , jv ) 。 山東理工大學(xué)管理學(xué)院 ? 圖的基本概念 圖與網(wǎng)絡(luò)的基本概念 定義 8–2 頂點(diǎn)數(shù)和邊數(shù) 圖 G = (V, E ) 中， V中元素的個(gè)數(shù)稱(chēng)為圖 G的頂點(diǎn)數(shù)，記作 p (G )或簡(jiǎn)記為 p； E中元素的個(gè)數(shù)稱(chēng)為圖 G 的邊數(shù)，記作 q (G )，或簡(jiǎn)記為 q。 含有多重邊的圖稱(chēng)為 多重圖 ；無(wú)環(huán)也無(wú)多重邊的圖稱(chēng)為 簡(jiǎn)單圖。 山東理工大學(xué)管理學(xué)院 ? 圖的基本概念 圖與網(wǎng)絡(luò)的基本概念 v 3 e 4 v 1 v 2 v 5 v 4 v 6 e 1 e 2 e 3 e 5 e 6 e 7 e 8 p ( G ) = 6 ， q ( G ) = 8 ； e 3 = [ 4v , 3v ] ， 3v 與 4v 是 e 3 的端點(diǎn)，e 3 是點(diǎn) 3v 和 4v 的關(guān)聯(lián)邊； 2v 與 5v 是鄰點(diǎn)， e 3 與 e 2 是鄰邊；e 7 與 e 8 是多重邊， e 4 是一個(gè)環(huán) 。即 ???Vviiqvd 2)(定理 8–2 任一圖 G中，奇點(diǎn)的個(gè)數(shù)為偶數(shù)。 若鏈 ? 中，所含的邊互不相同，則稱(chēng) ? 為 簡(jiǎn)單鏈 ； 若鏈 ? 中，頂點(diǎn) 21 , ii vv , ? , k1k , ii vv ? 都不相同，則稱(chēng) ? 為 初等鏈 。若一條路的始點(diǎn)和終點(diǎn)相同，則稱(chēng)之為 回路 。 山東理工大學(xué)管理學(xué)院 ? 圖的基本概念 圖與網(wǎng)絡(luò)的基本概念 定義 8–4 一個(gè)圖 G的任意兩個(gè)頂點(diǎn)，如果至少有一條通路將它們連接起來(lái)，則這個(gè)圖 G就稱(chēng)為 連通圖 ，否則就稱(chēng)為 不連通圖 。 若 G是不連通圖，它的每個(gè)連通的部分稱(chēng)為 G的一個(gè) 連通分圖 (也簡(jiǎn)稱(chēng)分圖 )。 設(shè)在有向圖 D = ( V , A ) 中，對(duì)任意一條弧 a ∈ A ，如果相應(yīng)都有一個(gè)權(quán)值 w ( e ) 與之對(duì)應(yīng)，則稱(chēng) G 為 賦權(quán)有向圖 。 山東理工大學(xué)管理學(xué)院 ? 圖的矩陣表示 圖與網(wǎng)絡(luò)的基本概念 1．關(guān)聯(lián)矩陣 給定無(wú)向圖 G = （ V ， E ），其中 V = {1v，2v， ? ， v n } ， E = { e 1 ， e 2 ， ? ， e m } 。 關(guān)聯(lián)矩陣描述了無(wú)向圖 G的頂點(diǎn)與邊的關(guān)聯(lián)情況。 鄰接矩陣描述了圖的頂點(diǎn)與頂點(diǎn)之間的關(guān)系。 1. 樹(shù)的定義 2. 樹(shù)的性質(zhì) （ 1） 具有 n個(gè)頂點(diǎn)的樹(shù)，其邊數(shù)恰好為 n1條。 （ 3） 在樹(shù) T中去掉任一條邊，則 T成為不連通圖。進(jìn)一步地說(shuō)，如果再?gòu)倪@個(gè)圈上任意去掉一條邊，可以得到一個(gè)樹(shù)。 其支撐樹(shù)為 山東理工大學(xué)管理學(xué)院 ? 圖的支撐樹(shù) 最小支撐樹(shù)問(wèn)題 2. 判斷一個(gè)圖 G有支撐樹(shù)的充要條件 定理 圖 G有支撐樹(shù)的充分必要條件是圖 G是連通的。 如果 G1不含圈 ， 那么 G1 是 G的一個(gè)支撐樹(shù)；如果 G1仍含圈 ， 那么從 G1中任取一個(gè)圈 ， 從圈中再任意去掉一條邊 ， 得到圖 G的一個(gè)支撐子圖 G2 ， 如此重復(fù) ， 最終可以得到 G的一個(gè)支撐子圖 GK ， 它是連通的 ， 并且不含圈 ， 于是 GK是 G的一個(gè)支撐樹(shù) 。 證明 充分性 設(shè)圖 G是連通圖 山東理工大學(xué)管理學(xué)院 ? 圖的支撐樹(shù) 最小支撐樹(shù)問(wèn)題 3. 尋求連通圖的支撐樹(shù)的方法 （ 1）破圈法 就是在圖 G中任取一個(gè)圈，從圈中去掉一邊，對(duì)余下的圖重復(fù)這個(gè)步驟，直到不含圈時(shí)為止，即得到圖 G的 一個(gè)支撐樹(shù)。重復(fù)這個(gè)過(guò)程， 直到不能進(jìn)行為止，這時(shí)即得到一個(gè)支撐樹(shù)。 (2)最小支撐樹(shù) 如果支撐樹(shù) T*的權(quán)是 G的所有支撐樹(shù)的權(quán)中最小者 ， 則稱(chēng) T*是 G的最小支撐樹(shù) (簡(jiǎn)稱(chēng) 最小樹(shù) )。 山東理工大學(xué)管理學(xué)院 ? 最小支撐樹(shù)問(wèn)題 最小支撐樹(shù)問(wèn)題 (3)求最小支撐樹(shù)的方法 第一種方法 破圈法 在連通圖 G中 ， 任取一個(gè)圈 ， 從圈中去掉一條權(quán)最大的邊 (如果有兩條或兩條以上的邊都是權(quán)最大的邊 ， 則任意去掉其中一條 )。 v1 v2 v3 v4 v5 v6 6 5 1 5 7 2 3 4 4 W(T)=5+1+2+3+4=15 山東理工大學(xué)管理學(xué)院 ? 最小支撐樹(shù)問(wèn)題 最小支撐樹(shù)問(wèn)題 (3)求最小支撐樹(shù)的方法 第二種方法 避圈法 在連通圖 G中，開(kāi)始選一條最小權(quán)的邊，以后每一步中，總從未被選取的邊中選一條權(quán)最小的邊，并使之與已選取的邊不構(gòu)成圈 (每一步中，如果有兩條或兩條以上的邊都是權(quán)最小的邊，則從中任選一條 )。已選邊與頂點(diǎn)構(gòu)成的圖 T就是所求最小樹(shù)。 1. 引例 油田管道鋪設(shè)問(wèn)題 從圖中可以看出，可能的鋪設(shè)方案是很多的，如： 鋪設(shè) 路線(xiàn) 1 ： 1v → 2v → 4v → 7v → 9v ，管道總長(zhǎng)度為 1 6 鋪設(shè)路線(xiàn) 2 ： 1v → 3v → 5v → 8v → 9v ， 管道總長(zhǎng)度為 12 用圖論的語(yǔ)言來(lái)描述，一個(gè)方案對(duì)應(yīng)著一條從1v到9v的路，管道總長(zhǎng)為這條路線(xiàn)的總權(quán)，則上述問(wèn)題就是求一條從1v到9v的路線(xiàn)，使路線(xiàn)的權(quán)最小，這樣的路稱(chēng)為最短路。 設(shè) P是 D中從 vs到 vt的一條路， 路 P的權(quán) 是 P中所有弧的權(quán)之和。即 ???PvvijjiPW),()( ?)(m i n)( 0 PWPW P?山東理工大學(xué)管理學(xué)院 最短路問(wèn)題 ? 最短路問(wèn)題的算法 Dijkstra標(biāo)號(hào)算法 適用范圍 ： 0?ij?基本思路 :從起點(diǎn) vs出發(fā) ,逐步向外探尋，對(duì)于某一個(gè)結(jié)點(diǎn) vi標(biāo)號(hào)： 固定標(biāo)號(hào) P(vi) 或 臨時(shí)標(biāo)號(hào) T(vi) 主要步驟 ：開(kāi)始： P(vs)=0， T(vi)=+∞ Step1:修改臨時(shí)標(biāo)號(hào) Step2:變臨時(shí)標(biāo)號(hào)為固定標(biāo)號(hào) 山東理工大學(xué)管理學(xué)院 ? 最短路問(wèn)題的算法 1 2 3 4 5 6 1 2 2 2 3 3 3 4 4 最短路問(wèn)題 用 Dijkstra標(biāo)號(hào)算法求下列無(wú)向圖中頂點(diǎn)１到頂點(diǎn) 6的最短距離及其路線(xiàn)。 （ 1）與頂點(diǎn) 1直接相連又為臨時(shí)標(biāo)號(hào)的頂點(diǎn)是 2和 3，這兩個(gè)頂點(diǎn)的臨時(shí)標(biāo)號(hào)改為 Step1 T ( 2 ) = 4 T ( 3 ) = 3 山東理工大學(xué)管理學(xué)院 ? 最短路問(wèn)題的算法 最短路問(wèn)題 （ 2）在所有臨時(shí)標(biāo)號(hào)中，最小的為 T ( 3 ) ＝ 3，于是令 P ( 3 ) ＝ 3，即頂點(diǎn) 3獲得固定標(biāo)號(hào) 3。 山東理工大學(xué)管理學(xué)院 ? 最短路問(wèn)題的算法 最短路問(wèn)題 Step3 （ 1）對(duì)頂點(diǎn) 2有 T ( 4 ) = 7 T ( 5 ) = 5 （ 2）在所有臨時(shí)標(biāo)號(hào)中， T ( 5 ) ＝ 5最小，于是有 P (5 ) ＝ 5。 山東理工大學(xué)管理學(xué)院 ? 最短路問(wèn)題的算法 最短路問(wèn)題 Step5 （ 1）對(duì)頂點(diǎn) 4有 T ( 6 ) =9 （ 2）顯然有 P (6 ) ＝ 9。 頂點(diǎn) 1到頂點(diǎn) 6的最短距離為 9。 山東理工大學(xué)管理學(xué)院 最短路問(wèn)題 ? 最短路問(wèn)題應(yīng)用舉例 設(shè)備更新問(wèn)題 時(shí)間 第 1年 第 2年 第 3年 第 4年 第 5年 價(jià)格 11 11 12 12 13 維修費(fèi)用 5 6 8 11 18 如何制定使得總的支付費(fèi)用最少的設(shè)備更新計(jì)劃 ？ 可以把這個(gè)問(wèn)題化為最短路問(wèn)題 用點(diǎn) iv 代表“第 i 年年初購(gòu)進(jìn)一臺(tái)新設(shè)備”這種狀態(tài)（加設(shè)一點(diǎn) 6v ，可以理解為第 5 年年底決策的末狀態(tài)）。 現(xiàn)在計(jì)劃在這片區(qū)域內(nèi)建造一所醫(yī)院和一所小學(xué) ， 問(wèn)醫(yī)院應(yīng)建在哪個(gè)村莊才能使最遠(yuǎn)村莊到醫(yī)院看病所走的總路程最短 ?又問(wèn)小學(xué)建在哪個(gè)村莊才能使學(xué)生上學(xué)走的總路程最短 。 。 4 1 。 。( S ij 表示從 iv 出發(fā)到j(luò)v的最短路長(zhǎng) ) 。 山東理工大學(xué)管理學(xué)院 最短路問(wèn)題 設(shè)想小學(xué)建立在 jv ，則其它村莊的小學(xué)生們所走的總路程就是 50 S 1 j + 40 S 2 j + 60 S 3 j + 20