圖論初步講義-資料下載頁(yè)
2025-08-22 19:05本頁(yè)面
【導(dǎo)讀】V1為弧尾或始點(diǎn)，V3為弧頭或終點(diǎn)。在無(wú)向圖中，表示V1和V3之間的一條邊。交通圖中的有單行道雙行道，分別用無(wú)向邊、有向邊表示；假定沒有節(jié)點(diǎn)指向自身的邊。有n(n-1)條邊的有向圖稱為有向完全圖，k-1),v=v1,u=vk,則稱該序列是從頂點(diǎn)v到頂點(diǎn)。路徑上邊或弧的數(shù)目稱為該路徑的路徑長(zhǎng)度。線性表是一種特殊的樹。假定樹的最大度數(shù)為m，如果將其看成。具有n個(gè)頂點(diǎn)的連通圖，最少應(yīng)有多少。E，E1關(guān)聯(lián)的頂點(diǎn)都在V1中，則稱G1是G的子圖；回憶線性表，樹型結(jié)構(gòu)的表示，必須刻。鄰接矩陣表示法對(duì)求頂點(diǎn)的度很方便。無(wú)向圖的鄰接矩陣一定是一對(duì)稱矩陣，同一條。點(diǎn)之間是否有邊相連。頂點(diǎn)不變，在圖中增加、刪除邊：只需對(duì)矩陣。對(duì)應(yīng)分量賦1或清0。如果G是帶權(quán)的圖，wij是邊(vi,vj
【正文】 ,V6,V7,V8 （ 2） V1,V3,V2,V6,V7,V4,V5,V8 V8 V7 V6 V5 V4 V3 V2 V1 Houfeng Wang, ICL of PKU 43 廣度優(yōu)先方法需要隊(duì)列 Houfeng Wang, ICL of PKU 44 最小生成樹 問題： 假設(shè)要在 n個(gè)城市之間建立通訊聯(lián)絡(luò)網(wǎng)，則連通 n個(gè)城市只需要修建 n1條線路， 如何在最節(jié)省經(jīng)費(fèi)的前提下建立這個(gè)通訊網(wǎng)？ 該問題等價(jià)于：構(gòu)造網(wǎng)的一棵最小生成樹，即：在 e條帶權(quán)的邊中選取 n1條（不構(gòu)成回路），使“權(quán)值之和”為最小。 Houfeng Wang, ICL of PKU 45 Spanning Tree ? Subgraph that includes all vertices of the original graph. ? Subgraph is a tree. ? If original graph has n vertices, the spanning tree has n vertices and n1 edges. Houfeng Wang, ICL of PKU 46 2 3 8 10 1 4 5 9 11 6 7 4 8 6 6 7 5 2 4 4 5 3 8 2 Minimum Cost Spanning Tree Tree cost is sum of edge weights/costs. Houfeng Wang, ICL of PKU 47 A Spanning Tree 2 3 8 10 1 4 5 9 11 6 7 4 8 6 6 7 5 2 4 4 5 3 8 2 Spanning tree cost = 51. Houfeng Wang, ICL of PKU 48 Minimum Cost Spanning Tree 2 3 8 10 1 4 5 9 11 6 7 4 8 6 6 7 5 2 4 4 5 3 8 2 Spanning tree cost = 41. Houfeng Wang, ICL of PKU 49 深度優(yōu)先與廣度優(yōu)先 ? 對(duì)于一般圖：構(gòu)造生成樹的過(guò)程可以按深度優(yōu)先周游，也可以按廣度優(yōu)先周游，周游中記錄訪問的所有頂點(diǎn)以及經(jīng)過(guò)的邊，得到的是深度優(yōu)先生成樹或廣度優(yōu)先生成樹，簡(jiǎn)稱為 DFS生成樹 或BFS生成樹 。 ? 對(duì)于網(wǎng)絡(luò)，其生成樹中的邊也帶權(quán)，將生成樹各邊的權(quán)值總和稱為 生成樹的權(quán) ，并把權(quán)值最小的生成樹稱為 最小生成樹 (Minimum Spanning Tree)。 Houfeng Wang, ICL of PKU 50 MST性質(zhì) 設(shè) G=(V， E)是一個(gè)網(wǎng)絡(luò)， U是頂點(diǎn)集合 V的一個(gè)真子集。如果邊 (u,v)的頂點(diǎn) u∈ U，v∈ VU，且邊 (u,v)是圖 G中所有一個(gè)端點(diǎn)在 U里，另一端點(diǎn)在 VU里的邊中權(quán)值最小的邊，則一定存在 G的一棵最小生成樹包括此邊 (u,v)。 用反證法證明（見教材 ） Houfeng Wang, ICL of PKU 51 算法一 (Prim 算法 ) 可取圖中任意一個(gè)頂點(diǎn) v作為生成樹的根，之后若要往生成樹上添加頂點(diǎn) w，則在頂點(diǎn) v和頂點(diǎn) w之間必定存在一條邊，并且該邊的權(quán)值在所有連通頂點(diǎn) v和 w之間的邊中取值最小。 一般情況下，假設(shè) n個(gè)頂點(diǎn)分成兩個(gè)集合： U（包含已落在生成樹上的結(jié)點(diǎn)）和 VU（尚未落在生成樹上的頂點(diǎn)），則在所有連通 U中頂點(diǎn)和 VU中頂點(diǎn)的邊中選取權(quán)值最小的邊。 Houfeng Wang, ICL of PKU 52 Kruskal 算法 為使生成樹上邊的權(quán)值之和最小，顯然，其中每一條邊的權(quán)值應(yīng)該盡可能地小。 Kruskal算法的做法就是：先構(gòu)造一個(gè)只含 n個(gè)頂點(diǎn)的子圖 SG，然后從權(quán)值最小的邊開始，若它的添加不使 SG中產(chǎn)生回路，則在 SG上加上這條邊，如此重復(fù)，直至加上 n1條邊為止。
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1