853-Chapter 11 图形结构（Graphs）.ppt

Chapter 11 圖形結構(Graphs) (1) 尤拉迴路 (Euler Circuit) (2) 漢米爾頓迴圈 (Hamiltonian Cycle) (3) 旅行銷售員問題 (Traveling Salesperson Problem) 旅行銷售員為推銷公司的商品，希望自公司出發走訪所有指定的城市，且不重複，並回到公司；而走過路徑的總距離（或總花費）要最短（或最小）。這個問題有城市間實際距離（或旅行花費）的考量。 (4) 頂點覆蓋(Vertex Cover)問題 將博物館的展示空間用圖形來表示，擺放藝術品 的直線走道是邊，頂點是邊與邊交界處。 基於安全的考量，館方將設置最少的警衛希望能 監看所有的展示走道。 這就是典型的頂點覆蓋問題：在圖形中，挑最小 的頂點集合，使得任何一邊的兩個頂點中，至少有一頂點在所挑的集合中，（所挑的點集合可覆蓋所有的點）。 所挑出的頂點，其分支出的邊，即稱其能覆蓋 (cover) 的邊。 圖形結構 名詞解釋 — 圖(b) 圓圈為「頂點」(vertex) 連線為「分支度」(degree)；Ex：節點c的分支度為5 假使尤拉問題要能成立的話，必須每個頂點具備偶數的分支度方可，此稱為尤拉循環(Eulerian cycle) 圖形的一些專有名詞 頂點(vertex)：上圖的圓圈稱之。 邊(edge)：上圖每個頂點之間的連線稱之。 圖形(graph)：是由所有頂點和所有邊組合而成的，以G=(V, E)表示。而V(G3) = {1,2,3}, E(G3) = {1,2,2,3,3,2} 圖形的一些專有名詞 無方向圖形(undirected graph)在邊上沒有箭頭者稱之，如: G1, G2 有方向圖形(directed graph)：在邊上有箭頭者稱之，如: G3 圖形的一些專有名詞 多重圖形（mutigraph）：假使兩個頂點間，有多條相同的邊此稱之為多重圖形，而不是圖形。如:G4 完整圖形（complete graph）：邊的個數最大者。在n個頂點的無方向圖形中，會有 n(n-1)/2個邊。如:G1。有方向圖形則有 n(n-1)個邊。如右圖 圖形的一些專有名詞 相鄰(adjacent)：在圖形的某一邊 (V1, V2) 中，我們稱頂點V1與頂點V2是相鄰的。有方向圖形中，如:G3的 1, 2故V2 adjacent from V1 而 adjacent to V1 附著(incident)：我們稱頂點V1和頂點V2是相鄰，而邊 (V1, V2) 是附著在頂點V1與V2頂點上。 圖形的一些專有名詞 子圖(subgraph)：假使V(G’)是V(G)的部份集合及E(G’)是E(G)的部份集合，我們稱G是G的子圖。 圖形的一些專有名詞 路徑(path)：在圖形G中，從頂Vp到頂點Vq的路徑是指一系列的頂點Vp, Vi1, Vi2,....., Vin, Vq，其中 (Vp,Vi1),(Vi1,Vi2),....., (Vin,Vq)是E(G)上的邊。 長度(length)：一條路徑上的長度是指該路徑上所有邊的數目。 圖形的一些專有名詞 簡單路徑(simple path)：在一路徑上除了頭尾頂點之外，其餘的頂點皆是不相同的。 如: G1的路徑1,2,2,4,4,3是簡單路徑而1,2, 2,4, 4,2則不是。 循環(cycle)：是指一條簡單路徑上，頭尾頂點皆相同者稱之。 G1的路徑 1,2, 2,4, 4,1 圖形的一些專有名詞 連通(connected)：在一個圖形G中，如果有一條路徑從V1到V2，那麼我們說V1與V2是連通的。若圖形中每一對的頂點均可找到一條路徑那該圖形為連通的。 圖G5不是連通的(因為g1與g2無法連接起來)。圖12-3 G1和 G2是連通的 圖形的一些專有名詞 連通單元(connected component)：或稱單元(component)是指該圖形中最大的連通子圖(maximum connected subgraph)如圖G5有兩個單元g1和g2。 圖形的一些專有名詞 緊密連通(strongly connected)：在一有方向圖形中如果V(G)中的每一對不同頂點Vi, Vj 各有一條從Vi到Vj及從Vj到Vi的有方向路徑者稱之。 右圖G3不是緊密連通，因為G3沒有V2到V1的路徑。 圖形的一些專有名詞 緊密連通單元(strongly connected component）：是指一個緊密連通最大子圖。如圖12-3 G3有兩個緊密連通單元。 分支度(degree)：附著在頂點的邊數。 內分支度(in-degree)：頂點V的內分支度是指以V為終點(即箭頭指向V)的邊數。 圖形的一些專有名詞 外分支度(out-degr