計(jì)算機(jī)圖形學(xué)考核試題

圖論(GraphTheory)B88901031電機(jī)四大鳥B88901115電機(jī)四酋長B88901118電機(jī)四炫大11/7/20221大綱…圖論源起範(fàn)例廣泛的應(yīng)用面定義實(shí)際網(wǎng)路應(yīng)用結(jié)論11/7/20222什麼是圖論？圖論亦稱「拓樸學(xué)」探討由「點(diǎn)」及「線」構(gòu)成的結(jié)構(gòu)任何一條線兩邊一定有點(diǎn)11/7/20223圖論的起源著名的柯尼斯堡七橋問題圖論的分析模型11/7/20224圖論可以為我們做什麼？交通路網(wǎng)電信都市系統(tǒng)結(jié)構(gòu)建物動(dòng)線分析11/7/20225小例子老鼠走迷宮(DepthFirstSearch)11/7/20226小例子2電腦輔助軟體CadenceProtel11/7/20227圖的根本定義G=(V,E)V是點(diǎn)(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)}11/7/20228加權(quán)圖G=(V,E)是一加權(quán)圖(weightedgraph)每個(gè)邊均相對(duì)應(yīng)於一個(gè)可正可負(fù)的數(shù)值權(quán)重weight(cost)11/7/20229路徑的定義G=(V,E),i,jV,點(diǎn)i到j(luò)的路徑是一個(gè)點(diǎn)串列相鄰之點(diǎn)相應(yīng)一個(gè)邊eE(1,3,5,8),(1,2,6,8),(1,2,5,3,2,5,8)均是1到8的路徑11/7/202210簡單路徑和迴路簡單路徑(simplepath)是一無重複之邊的路徑(1,3,5,8)、(1,2,6,8)為簡單路徑(1,2,5,3,2,6,8)

不是簡單路徑迴路(cycle,loop)是一首尾相接的簡單路徑

(5,7,4,3,1,2,5)是一個(gè)迴路

11/7/202211樹的根本定義樹(tree)是一個(gè)沒有迴路的無向圖任二點(diǎn)之間，僅有唯一的(簡單)路徑廣度優(yōu)先搜尋法(BreadthFirstSearch)深度優(yōu)先搜尋法(DepthFirstSearch)11/7/202212尤拉圖尤拉圖(Eulercircuit)定義經(jīng)過圖的每個(gè)頂點(diǎn)經(jīng)過圖的每個(gè)邊應(yīng)用layout範(fàn)例11/7/202213尤拉圖的應(yīng)用Layout11/7/202214圖與矩陣的對(duì)應(yīng)以矩陣表示範(fàn)例11/7/202215Isomorphism艾索莫非韌(Isomorphism)圖甲和圖乙是艾索莫非克(isomorphic)f是映射函數(shù)(one-to-oneandonto)假設(shè)在圖甲中，頂點(diǎn)v和w是相鄰的，則在圖乙中對(duì)應(yīng)的f(v)和f(w)相鄰f是頂點(diǎn)集合的函數(shù)範(fàn)例11/7/202216平面圖的定義平面圖(planargraph)一個(gè)可由立體圖轉(zhuǎn)換的平面圖，則： ｜V｜─｜E｜┼｜F｜＝2V:vertices(頂點(diǎn))E:edges(邊)F:faces(面)11/7/202217平面圖範(fàn)例8個(gè)頂點(diǎn)(V=8)12個(gè)邊(E=12)6個(gè)面(F=6)8-12+6=211/7/202218其它平面圖的範(fàn)例11/7/202219圖論在網(wǎng)路上的應(yīng)用最短路徑法廣度優(yōu)先搜尋法(BFS,BreadthFirstSearch)Dijstra’s演算法Bellman&Ford演算法Floyd&Warshall演算法11/7/202220Dijstra’s演算法11/7/202221Dijstra’s演算法Usedtoestablishroutingtablenotation:(x)0,labelxwith0Begin

(s)0;(v)

,vs;/*代表無限大*/ TV; P

; us; Repeat foreachvertexvTadjacenttoudo(v)min{(v),(u)+w(u,v)}; TT–{u}; PP{u}; uanewvertexinTwithmin.(u); Untileither(T=)or((u)=);end11/7/202222Dijstra’s演算法TPU(S)(1)(2)(3)(4)(5)12345S0∞∞∞∞∞11/7/202223Dijstra’s演算法TPU(S)(1)(2)(3)(4)(5)12345s0∞∞∞∞∞1345s251∞∞∞135s244∞2311/7/202224Dijstra’s演算法TPU(S)(1)(2)(3)(4)(5)12345s0∞∞∞∞∞1345s251∞∞∞135s244∞2313s245∞3s2451611/7/202225Dijstra’s演算法無由Node5指向T內(nèi)的點(diǎn)，跳出forloopTPU(S)(1)(2)(3)(4)(5)12345s0∞∞∞∞∞1345s251∞∞∞135s244∞2313s245∞3s24516s24513611/7/202226圖論之應(yīng)用2網(wǎng)路流量問題11/7/202227網(wǎng)路流量問題圖論可以解決簡單的流量問題對(duì)一網(wǎng)路而言，其最大的流量為一條切割上的最小容量容量=流出量–流入量切割流出量流入量11/7/202228Labeling演算法Beginf(i,j)0,(i,j)E;/*anyfeasibleflow=0*/(s)(-,);/*assigntheinitiallabeltos,whererepresentsinfinity*/repeat/*searchforanaugmentingpath;initially,sistheonlyvertexthatislabeledbutunscanned.*/ whilethereisalabeledbutunscannednodeido begin/*scanningi*/ foreachunlabeledjsuchthatf(i,j)<c(i,j)do /*forwardlabelingfromi*/ jc(i,j)–f(i,j); (j)(i+,j); foreachunlabeledjsuchthatf(j,i)>0do /*reverselabelingfromi*/ jf(j,i); (j)(i-,j); marki“scanned〞; end_of_while; iftislabeledthendo/*flowaugmentation*/ begin min{j|jV(G)};increaseordecreaseaflowofunitsalongeacharcoftheaugmentingpathaccordingto+,-sign; eraseallscanningmark; erasealllabelsexcept(s); end;untilyouarenotabletolabelt;identifytheminimumcut;/*edgesfromlabelednodestounlabelednodes*/end.11/7/202229Labeling演算法11/7/202230Labeling演算法11/7/202231Labeling演算法11/7/202232結(jié)論圖論是一種工具，可利用來簡化問題，或是將在圖論的定理應(yīng)用到我們?nèi)粘?/p>