计算机图形学考核试题.pptVIP

on the fly 第十組 圖論 (Graph Theory) 電機四 大鳥 電機四 酋長 電機四 炫大 大綱…圖論 源起 範例 廣泛的應用面 定義 實際網路應用 結論 什麼是圖論？ 圖論亦稱「拓樸學」 探討由「點」及「線」構成的結構 任何一條線 兩邊一定有點 圖論的起源 著名的柯尼斯堡七橋問題 圖論的分析模型 圖論可以為我們做什麼？ 交通路網 電信 都市系統結構 建物動線分析 小例子 老鼠走迷宮 (Depth First Search) 小例子2 電腦輔助軟體 Cadence Protel 圖的基本定義 G = (V, E) V是點(vertices, nodes, points)的集合 E是線(edges, arcs, lines) 的集合。 G = (V, E) V = {1,2,3,4}, E = {a, b, c, d} = { (1,2), (1,3), (2,3), (3,4)} 加權圖 G = (V, E)是一加權圖(weighted graph) 每個邊均相對應於一個可正可負的數值 權重 weight ( cost ) 路徑的定義 G = (V, E), i,j?V, 點i到j的路徑是一個點串列 相鄰之點相應一個邊 e?E (1,3,5,8), (1,2,6,8), (1,2,5,3,2,5,8)均是1到8的路徑 簡單路徑和迴路 簡單路徑(simple path)是一無重複之邊的路徑 (1,3,5,8) 、 (1,2,6,8) 為簡單路徑 (1,2,5,3,2,6,8) 不是簡單路徑 迴路(cycle, loop)是一首尾相接的簡單路徑 (5,7,4,3,1,2,5)是一個迴路 樹的基本定義 樹(tree)是一個沒有迴路的無向圖 任二點之間，僅有唯一的(簡單)路徑 廣度優先搜尋法 (Breadth First Search) 深度優先搜尋法 (Depth First Search ) 尤拉圖 尤拉圖 (Euler circuit) 定義 經過圖的每個頂點 經過圖的每個邊 應用 layout 範例 尤拉圖的應用 Layout 圖與矩陣的對應 以矩陣表示 範例 Isomorphism 艾索莫非韌 (Isomorphism) 圖甲和圖乙是艾索莫非克(isomorphic) f 是映射函數 (one-to-one and onto) 若在圖甲中，頂點 v 和 w 是相鄰的，則在圖乙中對應的 f(v) 和 f(w) 相鄰 f 是頂點集合的函數 範例 平面圖的定義 平面圖 (planar graph) 一個可由立體圖轉換的平面圖，則： ｜V｜─｜E｜┼｜F｜＝ 2 V: vertices (頂點) E: edges (邊) F: faces (面) 平面圖範例 8個頂點(V=8) 12個邊 (E=12) 6個面 (F=6) 8-12+6=2 其它平面圖的範例 圖論在網路上的應用 最短路徑法 廣度優先搜尋法 (BFS,Breadth First Search) Dijstra’s 演算法 Bellman Ford 演算法 Floyd Warshall 演算法 Dijstra’s 演算法 Dijstra’s 演算法 Used to establish routing table notation: ?(x)?0, label x with 0 Begin ?(s) ? 0; ?(v) ? ?, ?v?s; /* ? 代表無限大 */ T ? V; P ? ?; u ? s; Repeat for each vertex v?T adjacent to u do ?(v) ? min{?(v), ?(u)+w(u,v)}; T ? T – {u}; P ? P? {u}; u ? a new vertex in T with min. ?(u); Until either (T = ?) or (?(u)= ?); end Dijstra’s 演算法 Dijstra’s 演算法 Dijstra’s 演算法 Dijstra’s 演算法 無由 Node 5 指向 T 內的點，跳出for loop 圖論之應用 2 網路流量問題 網路流量問題 圖論可以解決簡單的流量問題 對一網路而言，其最大的流量為一條切割上的最小容量 容量 = 流出量 – 流入量 Labeling 演算法 Begin f(i,j) ? 0, ?(i,j) ?E; /*any feasible flow = 0 */