數(shù)模-圖論及其算法(編輯修改稿)
2024-11-14 15:45 本頁面
【文章內(nèi)容簡介】 頂點（源）到其它各點之間的最短路。 )(m in),( PWvud P?4. 樹 A. 樹的定義：連通而不含回路的無向圖稱為無向樹，簡稱 樹 。連通分支數(shù)大于等于 2，且每個連通分支均是樹，這樣的圖稱為 森林 。 B. 樹的等價定理 設(shè) G=(V， E)， |V|=n， |E|=m，則下列各命題等價。 （ 1） G連通而不含回路； （ 2） G的每對頂點之間存在唯一的路徑； （ 3） G連通，且 n=m+1。 （ 4） G中無回路，且 n=m+1； （ 5） G中無回路，但在 G中任兩個不相鄰的頂點之間增加一條邊，就形成唯一的一條回路； （ 6） G是連通的，且每條邊都是橋； （ 7） G是連通的，但刪除任意一條邊后， G都不連通。 C. 生成樹的定義： G=(V， E)是無向連通圖， T是 G的生成子圖，并且 T是樹，則稱 T是 G的 生成樹 。對于賦權(quán)圖 G=(V,E,W)，如果生成樹 T滿足： 則稱為最小生成樹。 D. 最小生成樹的算法 算法 I（避圈法）： （ 1）在賦權(quán)圖 G=(V,E,W)中取權(quán)值最小的邊 e1，加入樹 T中； （ 2）假設(shè)已經(jīng)找到樹 T的邊集 E(T),在邊集 E\E(T) 中取最小權(quán)值的邊 ek，如果加入樹 T的邊集 E(T)后不構(gòu)成圈，則記樹 T的邊集為E(T)+{ek}；如果加入后構(gòu)成圈，則在邊集 EE(T){ek}中尋找最小權(quán)的邊，再加入樹 T中，直到不構(gòu)成圈。 （ 3）重復（ 2），直到 |E(T)|=n1. 算法 II(破圈法 )，此法與算法 I類似，只是每次在圖 G中任選一個圈，然后刪除圈上最大權(quán)重的邊，直到無圈為止。 ?????? ?? ??? EeGTewTWTW )()(m in)(七、 Dijkstra算法 給定賦權(quán)圖 G=(V， E， W)及其源 a0，點 a0到圖中其它各點最短路算法為： （ 1）把頂點集 V分成兩部分 S和 T， S為已標集合， T為剩余頂點集，令 S={a0}， T=VS。 （ 2）在 T中找出一點 u使得 d(a0,a1)=min w(x,a0)，其中 x為 T中任意結(jié)點。記S1=S?{a1}， T1=V S1 。并在點 a1處標記 [d(a0,a1)]。 （ 3）設(shè)已找到 Si={a0， a1， a2， … ai}，并且 d(a0,ak)（ k=1,2, … ,i）已知。在 Ti=VSi中找出點 ai+1，使得 d(a0,ai+1)=min{d(a0,ak)+ w(ak,u)， ak?Si， u ? Ti中的任意頂點 }。記 Si+1={a0， a1，a2， … ai+1}，并在點 ai+1處標記 [d(a0,ai+1)]， Ti+1=VSi+1 。 （ 4）如果 Ti+1=?，則停止。否則重復（ 3）。 范例 ：賦權(quán)圖如圖 5，最短路如圖 6。 a v1 v2 v3 v4 2 3 4 6 5 10 7 圖 5 1 2 a v1 v2 v3 v4 2 3 6 5 10 7 圖 6 1 2 [2] [3] [5] 4 [7] 4 八、 Euler圖 1. 定義：通過圖中每條邊一次且僅一次的路徑稱為 Euler路徑 ；如果是回路，則稱 Euler回路 ；具有 Euler回路的圖稱為 Euler圖 。 2. 判定 Euler圖的充要條件。 定理 5 簡單圖 G具有一條 Euler路徑的充要條件是 G具有零個或兩個奇數(shù)次的頂點。 推論： 無向簡單圖是 Euler圖，當且僅當圖中每個頂點的度數(shù)為偶數(shù)。 定理 6 有向圖 G=(V,E)具有 Euler回路，當且僅當任意 v?V有 。有向圖具有 Euler路徑，當且僅當可能除兩個頂點以外的所有頂點有 ，例外的兩個頂點中，引入次數(shù)與引出次數(shù)差 1。 應(yīng)用 ：回答哥尼斯堡七橋問題。 )(deg)(deg vv ?? ?)(deg)(deg vv ?? ?九、 Hamilton圖 給定無向圖 G=V,E，通過圖中每個結(jié)點一次且僅一次的路徑（回路）稱為 Hamilton路徑（回路、圈） 。具有哈密爾頓回路的圖稱為 哈密爾頓圖 。 定理 7 設(shè) G=V,E是 Hamilton圖，則對 V的每個非空真子集 S均成立 這里 |S|表示頂點集 S的點數(shù)， ?(GS)表示 G刪去點集 S后得到的圖的連通分圖個數(shù)。 定理 8 設(shè) G=V,E， |V|=n
教學課件相關(guān)推薦
鄂ICP備17016276號-1