计算机图形学考核试题

2018/1/19,on the fly,1,圖論 (Graph Theory),B88901031 電機四 大鳥B88901115 電機四 酋長B88901118 電機四 炫大,2018/1/19,on the fly,2,大綱圖論,源起範例廣泛的應用面定義實際網路應用結論,2018/1/19,on the fly,3,什麼是圖論？,圖論亦稱拓樸學探討由點及線構成的結構任何一條線兩邊一定有點,2018/1/19,on the fly,4,圖論的起源,著名的柯尼斯堡七橋問題 圖論的分析模型,2018/1/19,on the fly,5,圖論可以為我們做什麼？,交通路網電信都市系統結構建物動線分析,2018/1/19,on the fly,6,小例子,老鼠走迷宮 (Depth First Search),2018/1/19,on the fly,7,小例子2,電腦輔助軟體CadenceProtel,2018/1/19,on the fly,8,圖的基本定義,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),2018/1/19,on the fly,9,加權圖,G = (V, E)是一加權圖(weighted graph)每個邊均相對應於一個可正可負的數值權重 weight ( cost ),2018/1/19,on the fly,10,路徑的定義,G = (V, E), i,jV, 點i到j的路徑是一個點串列相鄰之點相應一個邊 eE(1,3,5,8), (1,2,6,8), (1,2,5,3,2,5,8)均是1到8的路徑,2018/1/19,on the fly,11,簡單路徑和迴路,簡單路徑(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)是一個迴路,2018/1/19,on the fly,12,樹的基本定義,樹(tree)是一個沒有迴路的無向圖任二點之間，僅有唯一的(簡單)路徑 廣度優先搜尋法 (Breadth First Search)深度優先搜尋法 (Depth First Search ),2018/1/19,on the fly,13,尤拉圖,尤拉圖 (Euler circuit)定義 經過圖的每個頂點 經過圖的每個邊應用layout範例,2018/1/19,on the fly,14,尤拉圖的應用,Layout,2018/1/19,on the fly,15,圖與矩陣的對應,以矩陣表示範例,2018/1/19,on the fly,16,Isomorphism,艾索莫非韌 (Isomorphism) 圖甲和圖乙是艾索莫非克(isomorphic)f 是映射函數 (one-to-one and onto) 若在圖甲中，頂點 v 和 w 是相鄰的，則在圖乙中對應的 f(v) 和 f(w) 相鄰f 是頂點集合的函數範例,2018/1/19,on the fly,17,平面圖的定義,平面圖 (planar graph) 一個可由立體圖轉換的平面圖，則：VEF 2V: vertices (頂點)E: edges (邊)F: faces (面),2018/1/19,on the fly,18,平面圖範例,8個頂點(V=8)12個邊 (E=12)6個面 (F=6)8-12+6=2,2018/1/19,on the fly,19,其它平面圖的範例,2018/1/19,on the fly,20,圖論在網路上的應用,最短路徑法廣度優先搜尋法 (BFS,Breadth First Search) Dijstras 演算法 Bellman & Ford 演算法Floyd & Warshall 演算法,2018/1/19,on the fly,21,Dijstras 演算法,2018/1/19,on the fly,22,Dijstras 演算法,Used to establish routing tablenotation: (x)0, label x with 0Begin(s) 0; (v) , vs; /* 代表無限大 */T V; P ;u s;Repeatfor each vertex vT 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,2018/1/19,on the fly,23,Dijstras 演算法,2018/1/19,on the fly,24,Dijstras 演算法,2018/1/19,on the fly,25,Dijstras 演算法,2018/1/19,on the fly,26,Dijstras 演算法,無由 Node 5 指向 T 內的點，跳出for loop,2018/1/19,on the fly,27,圖論之應用 2,網路流量問題,2018/1/19,on the fly,28,網路流量問題,圖論可以解決簡單的流量問題對一網路而言，其最大的流量為一條切割上的最小容量容量 = 流出量 流入量,切割,流出量,流入量,2018/1/19,on the fly,29,Labeling 演算法,Beginf(i,j) 0, (i,j) E; /*any feasible flow = 0 */(s) (-,); /* assign the initial label to s , where represents infinity*/repeat/* search for an augmenting path; initially, s is the only vertex that is labeled but unscanned. */while there is a labeled but unscanned node i dobegin /*scanning i */for each unlabeled j such that f(i,j) 0 do/* reverse labeling from i */j f(j,i);(j) (i-,j);mark i “scanned”;end_of_while;if t is labeled then do /* flow augmentation */ begin minj | jV(G) ;increase or decrease a flow of units along each arc of the augmenting path according to +, - sign;erase all scanning mark;erase all labels except (s);end;until you are not able to label t;identify the minimum cut; /* edges from labeled nodes to unlabeled nodes */end.,2018/1/19,on the fly,30,Labeling 演算法,2018/1/19,on the fly,31,Labeling 演算法,2018/1/19,on the fly,32,Labeling 演算法,2018/1/19,on the fly,33,結論,圖論是一種工具，可利用來簡化問題，或是將在圖論的定理應用到我們日常生活中的情形善用圖學上的理論來解決問題無所不在的圖論Visio不錯用 ,2018/1/