圖論講稿ppt課件

1、圖論在建模中的運用 1. 圖論的根本概念2. 最短路問題及算法 圖論模型根底知識3. 最小生成樹問題及算法 4. 哈密爾頓圖5. 歐拉圖1.圖論的根本概念1) 圖的概念2) 賦權(quán)圖與子圖3) 圖的矩陣表示4) 圖的頂點度5) 路和連通1) 圖的概念 定義 一個圖G是指一個二元組(V(G),E(G)，其中: 其中元素稱為圖G的頂點.組成的集合，即稱為邊集,其中元素稱為邊. 定義 圖G的階是指圖的頂點數(shù)|V(G)|, 用來表示；圖的邊的數(shù)目|E(G)|用來表示. 也用來表示邊是非空有限集，稱為頂點集，1)2) E(G)是頂點集V(G)中的無序或有序的元素對表示圖，簡記 用 定義 假設(shè)一個圖的頂點集

2、和邊集都是有限集，那么稱 其為有限圖. 只需一個頂點的圖稱為平凡圖，其他的 一切圖都稱為非平凡圖. 定義假設(shè)圖G中的邊均為有序偶對,稱G為有向邊 為無向邊，稱e銜接 和 ，頂點 和 稱圖. 稱邊為有向邊或弧,稱是從銜接，稱 為e的弧尾，稱 為e的弧頭. 假設(shè)圖G中的邊均為無序偶對 ，稱G為無向圖.稱為e的端點. 既有無向邊又有有向邊的圖稱為混合圖. 常用術(shù)語1) 邊和它的兩端點稱為相互關(guān)聯(lián).2)與同一條邊關(guān)聯(lián)的兩個端點稱為相鄰的頂點，與同一個頂點 點關(guān)聯(lián)的兩條邊稱為相鄰的邊. 3) 端點重合為一點的邊稱為環(huán)， 端點不一樣的邊稱為連桿.4) 假設(shè)一對頂點之間有兩條以上的邊結(jié)合，那么這些邊 稱為重

3、邊5) 既沒有環(huán)也沒有重邊的圖，稱為簡單圖 常用術(shù)語6) 恣意兩頂點都相鄰的簡單圖,稱為完全圖. 記為Kv. 7) 假設(shè) ， ，且X 中恣意兩頂點不， 相鄰，Y 中恣意兩頂點不相鄰，那么稱為二部圖或 偶圖；假設(shè)X中每一頂點皆與Y 中一切頂點相鄰,稱為完全二部圖或完全偶圖,記為 (m=|X|,n=|Y|)8) 圖 叫做星.二部圖2) 賦權(quán)圖與子圖 定義 假設(shè)圖 的每一條邊e 都賦以一個實數(shù)w(e)，稱w(e)為邊e的權(quán)，G 連同邊上的權(quán)稱為賦權(quán)圖. 定義 設(shè) 和 是兩個圖. 1) 假設(shè) ,稱 是 的一個子圖,記 2) 假設(shè) ， ，那么稱 是 的生成子圖. 3) 假設(shè) ，且 ，以 為頂點集，以兩端

4、點 均在 中的邊的全體為邊集的圖 的子圖，稱 4) 假設(shè) ，且 ，以 為邊集，以 的端點 集為頂點集的圖 的子圖，稱為 的由 導(dǎo)出的 邊導(dǎo)出的子圖，記為 . 為 的由 導(dǎo)出的子圖，記為 .3) 圖的矩陣表示 鄰接矩陣:1) 對無向圖 ，其鄰接矩陣 ，其中： (以下均假設(shè)圖為簡單圖).2) 對有向圖 ,其鄰接矩陣 ,其中： 其中：3) 對有向賦權(quán)圖 , 其鄰接矩陣 ,對于無向賦權(quán)圖的鄰接矩陣可類似定義. 關(guān)聯(lián)矩陣 1) 對無向圖 ，其關(guān)聯(lián)矩陣 ,其中：2) 對有向圖 ，其關(guān)聯(lián)矩陣 ,其中：4) 圖的頂點度定義 1) 在無向圖G中，與頂點v關(guān)聯(lián)的邊的數(shù)目(環(huán)算兩次),稱為頂點v的度或次數(shù)，記為d(

5、v)或 dG(v).稱度為奇數(shù)的頂點為奇點，度為偶數(shù)的頂點為偶點.2) 在有向圖中，從頂點v引出的邊的數(shù)目稱為頂點 v的出度，記為d+(v)，從頂點v引入的邊的數(shù)目稱為 v的入度，記為d -(v). 稱d(v)= d+(v)+d -(v)為頂點v的 度或次數(shù)定理的個數(shù)為偶數(shù)推論 任何圖中奇點5) 路和連通 定義1) 無向圖G的一條途徑或通道或鏈?zhǔn)侵敢粋€有限非空序列 ，它的項交替 地為頂點和邊，使得對 ， 的端點是 和 ,稱W是從 到 的一條途徑，或一條 途徑. 整數(shù)k稱為W的長. 頂點 和 分別稱為的起點和終點 ,而 稱為W的內(nèi)部頂點. 2) 假設(shè)途徑W的邊互不一樣但頂點可反復(fù)，那么稱W為跡或

6、簡單鏈. 3) 假設(shè)途徑W的頂點和邊均互不一樣，那么稱W為路或途徑. 一條起點為 ,終點為 的路稱為 路記為 定義 1) 途徑 中由相繼項構(gòu)成子序列 稱為途徑W的節(jié). 2) 起點與終點重合的途徑稱為閉途徑. 3) 起點與終點重合的的路稱為圈(或回路)，長為k的圈稱為k階圈，記為Ck. 4) 假設(shè)在圖G中存在(u,v)路，那么稱頂點u和v在圖G中連通. 5) 假設(shè)在圖G中頂點u和v是連通的，那么頂點u和v之之間的間隔d(u,v)是指圖G中最短(u,v)路的長；假設(shè)沒沒有路銜接u和v，那么定義為無窮大. 6) 圖G中恣意兩點皆連通的圖稱為連通圖 7) 對于有向圖G，假設(shè) ，且 有 類似地，可定義有

7、向跡，有向路和有向圈.頭 和尾 ，那么稱W為有向途徑. 例 在右圖中： 途徑或鏈： 跡或簡單鏈： 路或途徑： 圈或回路：2最短路問題及算法 最短路問題是圖論運用的根本問題，很多實踐問題，如線路的布設(shè)、運輸安排、運輸網(wǎng)絡(luò)最小費用流等問題,都可經(jīng)過建立最短路問題模型來求解.最短路的定義最短路問題的兩種方法：Dijkstra迪杰斯特拉和Floyd算法 .1) 求賦權(quán)圖中從給定點到其他頂點的最短路.2) 求賦權(quán)圖中恣意兩點間的最短路. 2) 在賦權(quán)圖G中，從頂點u到頂點v的具有最小權(quán)定義 1) 假設(shè)H是賦權(quán)圖G的一個子圖，那么稱H的各邊的權(quán)和 為H的權(quán). 類似地，假設(shè)稱為路P的權(quán)假設(shè)P(u,v)是賦權(quán)

8、圖G中從u到v的路,稱 的路P*(u,v)，稱為u到v的最短路 3) 把賦權(quán)圖G中一條路的權(quán)稱為它的長，把(u,v)路的最小權(quán)稱為u和v之間的間隔，并記作 d(u,v). 1) 賦權(quán)圖中從給定點到其他頂點的最短路 假設(shè)G為賦權(quán)有向圖或無向圖，G邊上的權(quán)均非負(fù)假設(shè) ，那么規(guī)定 最短路是一條路，且最短路的任一節(jié)也是最短路求下面賦權(quán)圖中頂點u0到其他頂點的最短路Dijkstra算法: 求G中從頂點u0到其他頂點的最短路. 1) 置 ，對 ， ， 且 . 2) 對每個 ，用替代 ，計算 ，并把到達(dá)這個最小值的一個頂點記為 ，置 3) 假設(shè) ，那么停頓；假設(shè) ，那么用 i+1 代替i，并轉(zhuǎn)2).Dijk

9、stra算法: 求G中從頂點u0到其他頂點的最短路. 1) 置 ，對 ， ， 且 . 2) 對每個 ，用替代 ，計算 ，并把到達(dá)這個最小值的一個頂點記為 ，置 3) 假設(shè) ，那么停頓；假設(shè) ，那么用 i+1 代替i，并轉(zhuǎn)2).Dijkstra算法: 求G中從頂點u0到其他頂點的最短路. 1) 置 ，對 ， ， 且 . 2) 對每個 ，用替代 ，計算 ，并把到達(dá)這個最小值的一個頂點記為 ，置 3) 假設(shè) ，那么停頓；假設(shè) ，那么用 i+1 代替i，并轉(zhuǎn)2).Dijkstra算法: 求G中從頂點u0到其他頂點的最短路. 1) 置 ，對 ， ， 且 . 2) 對每個 ，用替代 ，計算 ，并把到達(dá)這個

10、最小值的一個頂點記為 ，置 3) 假設(shè) ，那么停頓；假設(shè) ，那么用 i+1 代替i，并轉(zhuǎn)2).Dijkstra算法: 求G中從頂點u0到其他頂點的最短路. 1) 置 ，對 ， ， 且 . 2) 對每個 ，用替代 ，計算 ，并把到達(dá)這個最小值的一個頂點記為 ，置 3) 假設(shè) ，那么停頓；假設(shè) ，那么用 i+1 代替i，并轉(zhuǎn)2).Dijkstra算法: 求G中從頂點u0到其他頂點的最短路. 1) 置 ，對 ， ， 且 . 2) 對每個 ，用替代 ，計算 ，并把到達(dá)這個最小值的一個頂點記為 ，置 3) 假設(shè) ，那么停頓；假設(shè) ，那么用 i+1 代替i，并轉(zhuǎn)2).Dijkstra算法: 求G中從頂點u

11、0到其他頂點的最短路. 1) 置 ，對 ， ， 且 . 2) 對每個 ，用替代 ，計算 ，并把到達(dá)這個最小值的一個頂點記為 ，置 3) 假設(shè) ，那么停頓；假設(shè) ，那么用 i+1 代替i，并轉(zhuǎn)2).Dijkstra算法: 求G中從頂點u0到其他頂點的最短路. 1) 置 ，對 ， ， 且 . 2) 對每個 ，用替代 ，計算 ，并把到達(dá)這個最小值的一個頂點記為 ，置 3) 假設(shè) ，那么停頓；假設(shè) ，那么用 i+1 代替i，并轉(zhuǎn)2).Dijkstra算法: 求G中從頂點u0到其他頂點的最短路. 1) 置 ，對 ， ， 且 . 2) 對每個 ，用替代 ，計算 ，并把到達(dá)這個最小值的一個頂點記為 ，置 3

12、) 假設(shè) ，那么停頓；假設(shè) ，那么用 i+1 代替i，并轉(zhuǎn)2).Dijkstra算法: 求G中從頂點u0到其他頂點的最短路. 1) 置 ，對 ， ， 且 . 2) 對每個 ，用替代 ，計算 ，并把到達(dá)這個最小值的一個頂點記為 ，置 3) 假設(shè) ，那么停頓；假設(shè) ，那么用 i+1 代替i，并轉(zhuǎn)2).Dijkstra算法: 求G中從頂點u0到其他頂點的最短路. 1) 置 ，對 ， ， 且 . 2) 對每個 ，用替代 ，計算 ，并把到達(dá)這個最小值的一個頂點記為 ，置 3) 假設(shè) ，那么停頓；假設(shè) ，那么用 i+1 代替i，并轉(zhuǎn)2).Dijkstra算法: 求G中從頂點u0到其他頂點的最短路. 1)

13、置 ，對 ， ， 且 . 2) 對每個 ，用替代 ，計算 ，并把到達(dá)這個最小值的一個頂點記為 ，置 3) 假設(shè) ，那么停頓；假設(shè) ，那么用 i+1 代替i，并轉(zhuǎn)2).定義 根據(jù)頂點v的標(biāo)號l(v)的取值途徑，使 到v的最短路中與v相鄰的前一個頂點w，稱為v的先驅(qū)點，記為z(v), 即z(v)=w.先驅(qū)點可用于追蹤最短途徑. 例5的標(biāo)號過程也可按如下方式進展：首先寫出左圖帶權(quán)鄰接矩陣因G是無向圖，故W是對稱陣Dijkstra算法：求G中從頂點u0到其他頂點的最短路設(shè)G為賦權(quán)有向圖或無向圖，G邊上的權(quán)均均非負(fù). 對每個頂點，定義兩個標(biāo)志l(v)，z(v)，其中: l(v) ：表從頂點u0到v的一條

14、路的權(quán) z(v) ：v的先驅(qū)點，用以確定最短路的道路.l(v)為從頂點u0到v的最短路的權(quán)算法的過程就是在每一步改良這兩個標(biāo)志，使最終S：具有永久標(biāo)號的頂點集.輸入: G的帶權(quán)鄰接矩陣 w(u,v)備用-將求最短路與最短途徑結(jié)合起來:算法步驟：l(v)u0vl(u)uw(u,v)首先寫出帶權(quán)鄰接矩陣?yán)?求以下圖從頂點u0到其他頂點的最短路因G是無向圖，故W是對稱陣見Matlab程序-Dijkstra.doc2) 求賦權(quán)圖中恣意兩頂點間的最短路算法的根本思想 I求間隔矩陣的方法.II求途徑矩陣的方法.III查找最短路途徑的方法. Floyd算法：求恣意兩頂點間的最短路. 舉例闡明算法的根本思想I

15、求間隔矩陣的方法.II求途徑矩陣的方法.在建立間隔矩陣的同時可建立途徑矩陣R III查找最短路途徑的方法.然后用同樣的方法再分頭查找假設(shè)：IVFloyd算法：求恣意兩頂點間的最短路.例 求以下圖中加權(quán)圖的恣意兩點間的間隔與途徑. 插入點 v1，得：矩陣中帶“=的項為經(jīng)迭代比較以后有變化的元素.插入點 v2，得：矩陣中帶“=的項為經(jīng)迭代比較以后有變化的元素.插入點 v3，得：插入點 v4，得：插入點 v5，得：插入點 v6，得：故從v5到v2的最短路為8 由v6向v5追溯: 由v6向v2追溯: 所以從到的最短途徑為： 一、 可化為最短路問題的多階段決策問題二、 選 址 問 題1、 中心問題2、

16、重心問題可化為最短路問題的多階段決策問題 選址問題-中心問題S(v1)=10, S(v2)=7, S(v3)=6, S(v4)=8.5, S(v5)=7, S(v6)=7, S(v7)=8.5S(v3)=6,故應(yīng)將消防站設(shè)在v3處。 選址問題-重心問題3最小生成樹及算法1) 樹的定義與樹的特征定義 連通且不含圈的無向圖稱為樹常用T表示. 樹中的邊稱為樹枝. 樹中度為1的頂點稱為樹葉.孤立頂點稱為平凡樹.平凡樹定理2 設(shè)G是具有n個頂點的圖，那么下述命題等價：1) G是樹 G無圈且連通；2) G無圈，且有n-1條邊；3) G連通，且有n-1條邊；4) G無圈，但添加任一條新邊恰好產(chǎn)生一個圈; 5

17、) G連通，且刪去一條邊就不連通了即G為最最小連通圖；6) G中恣意兩頂點間有獨一一條路.2圖的生成樹定義 假設(shè)T是包含圖G的全部頂點的子圖,它又是樹,那么稱T是G的生成樹. 圖G中不在生成樹的邊叫做弦.定理3 圖G=(V,E)有生成樹的充要條件是圖G是連 通的.II找圖中生成樹的方法可分為兩種：避圈法和破圈法 A 避圈法 : 深探法和廣探法 B 破圈法 A 避圈法 定理3提供了一種構(gòu)造圖的生成樹的方法. 這種方法就是在已給的圖G中，每步選出一條邊使它與已選邊不構(gòu)成圈，直到選夠n-1條邊為止. 這種方法可稱為“避圈法或“加邊法 在避圈法中，按照邊的選法不同，找圖中生成樹的方法可分為兩種：深探法

18、和廣探法.B 破圈法 相對于避圈法，還有一種求生成樹的方法叫做“破圈法. 這種方法就是在圖G中任取一個圈，恣意舍棄一條邊，將這個圈破掉，反復(fù)這個步驟直到圖G中沒有圈為止.例 用破圈法求出以下圖的一棵生成樹.B 破圈法例 用破圈法求出以下圖的另一棵生成樹.不難發(fā)現(xiàn)，圖的生成樹不是獨一的 .3) 最小生成樹與算法 引見最小樹的兩種算法：Kruskal(克魯斯卡算法或避圈法和破圈法. A Kruskal算法或避圈法步驟如下： 1) 選擇邊e1，使得w(e1)盡能夠??；2) 假設(shè)已選定邊 ，那么從中選取 ，使得:i) 為無圈圖， ii) 是滿足i)的盡能夠小的權(quán)， 3) 當(dāng)?shù)?)步不能繼續(xù)執(zhí)行時，那么

19、停頓.定理4 由Kruskal算法構(gòu)作的任何生成樹都是最小樹.例10用Kruskal算法求以下圖的最小樹.在左圖中 權(quán)值最小的邊有 任取一條 在 中選取權(quán)值最小的邊 中權(quán)值最小邊有 , 從中選任取一條邊會與已選邊構(gòu)成圈,故停頓,得中選取在中選取 中選取 . 但 與 都B破圈法算法2 步驟如下： 1) 從圖G中任選一棵樹T1.2) 加上一條弦e1，T1+e1中 立刻生成一個圈. 去掉此 圈中最大權(quán)邊，得到新樹T2,以T2代T1,反復(fù)2)再檢查剩余的弦，直到全部弦檢查終了為止.例11用破圈法求以下圖的最小樹.先求出上圖的一棵生成樹. 加以弦 e2,得到的圈v1v3v2v1,去掉最大的權(quán)邊e2,得到一棵新樹仍是原來的樹； 再加上弦e7，得到圈 v4v5v2v4,去掉最大的權(quán)邊e6，得到一棵新樹；如此反復(fù)進展，直到全全部