[ 資料結構 小學堂 ] 圖形結構 : 圖形介紹

前言 : 
圖形結構是一種探討兩個頂點間是否相連的一種關係圖, 在圖形中連接兩頂點的邊若填上加權值 (也可以稱為花費值), 這類圖形就稱為網路了. 圖形除了被活用在資料結構中最短途徑搜尋, 拓樸排序外, 還能應用在系統分析中以時間為評核標準的計畫評核術 (Performance Evaluation and Review Technique, PERT), 它是一種將系統作業流程依進行的優先順序繪製成網路, 來追蹤工作進度的評核工具. 

圖形的起源 : 
圖形理論起源於 1736 年, 一位瑞士數學家尤拉 (Euler) 為了解決 "肯尼亞茲堡橋樑" 問題, 所提出的一種資料結構理論. 下圖為 "肯尼亞茲堡橋樑" 問題的簡圖, 尤拉思考的問題是這樣的 : "如何在只經過每座橋樑一次的情況下, 把所有地方走過一次而且回到原點". 
 

尤拉環與尤拉鏈 : 
尤拉當時使用的方法就是以圖形結構進行分析. 他先以頂點表示土地, 以邊表示橋樑, 並定義連接每個頂點的邊樹稱為該頂點的分支度. 我們將以下面簡圖來表示 "肯尼亞茲堡橋樑" 問題 : 
 

最後尤拉找到一個結論 : "當所有頂點的分支度皆為偶數時, 才有可能從每一頂點出發, 經過每一邊一次, 並再次回到起點." 也就是說在上圖每個頂點都是奇數, 所以尤拉所思考的問題是不可能發生的, 這個理論就是有名的 "尤拉環" (Eulerian cycle) 理論. 
但如果條件改成從每頂點出發, 經過每一邊一次, 並不一定要回到起點, 亦即只允許其中兩個頂點的分支度是奇數, 其餘則必須全部為偶數, 符合這樣的結果就稱為尤拉鏈 (Eulerian chain) : 
 

圖形介紹 : 
圖形的種類有兩種 : 一種是無向圖形, 一是有向圖形. 無向圖形以 (V1,V2) 表示邊線, 有向圖形則以 表示邊線. 接下來會對圖形專有名詞進行介紹. 
圖形 (Graph) 是由頂點 (Vertice) 和邊 (Edge) 所組成, 以 G=(V,E) 來表示; 其中V 為所有頂點的集合, E為所有邊的集合. 如下圖 : 

V={A,B,C,D,E}
E={(A,B), (A,E), (B,C), (B,D), (C,D), (C,E), (D,E)}

 
上圖稱為 "無向圖形", 因為它的邊是沒有方向性的, 沒有方向性的邊以 () 表示; 另一種 "有向圖形" 它的每個邊都是有方向性的, 以 <>來表示, 如下圖 : 

V={A,B,C,D,E}
E={, , , , , }

 

專有名詞 : 
完整圖形 : 在無向圖形中, N 個頂點正好有 N(N-1)/2 條邊, 則稱為 "完整圖形", 但若在有向圖形中, 若要稱為"完整圖形", 則必須有 N(N-1) 個邊. 
 

子圖 : G 的子圖 A 與 B 包含於G, 參考下圖 : 
 

路徑 : 兩個不同頂點間所經過的邊稱為路徑, 如上圖G, A 到E的路徑有 {(A,B) , (B,E)} 及 {(A,B), (B,C), (C,D), (D,E)} 等. 
循環 : 起始頂點及終止頂點為同一個點的簡單路徑稱為循環. 如上圖G, {(A,B), (B,D), (D,E), (E,C), (C,A)} 起點及終點都是 A, 所以是一個循環路徑. 
相連 : 在無向圖形中, 若頂點V1 到頂點 V2間存在路徑, 則稱V1與 V2 是相連的. 
相連圖形 : 如果圖形中, 任兩頂點均為相連, 則稱此圖形為相連圖形, 否則稱為非相連圖形. (如上圖G) 
路徑長度 : 路徑上所包含邊的總數為路徑長度. 
相連單元 : 圖形中相連在一起的最大子圖總數. 
強相連 : 在有向圖形中, 若兩頂點有兩條方向相反的邊稱為強相連. 
分支度 : 在無向圖形中, 一個頂點所擁有邊的總數為分支度. 如上圖G, A頂點的分支度為4. 
入/出分支度 : 在有向圖形中, 以頂點V為箭頭終點的邊支個數為入分支支度, 反之由V出發的箭頭總數為出分支支度.