圖論的介紹 第二組 徐榮德 鄭又齊 陳俊嘉
大綱 圖論的基本介紹 我為什麼要介紹圖論？ 圖論的數學模型 實際生活中的圖論
圖論的基本介紹
什麼是圖？ 例一 例二 一堆頂點和邊的組合！
圖論的名詞 頂點 (Vertex) 邊 (Edge) 一個圖G = (V,E) V: 頂點的集合 E: 邊的集合 例：如右圖 V= {a,b,c,d,e} E= {(a,b),(a,c),(a,d), (b,e),(c,d),(c,e), (d,e)} 圖片來源：雷欽隆老師“資料結構”課投影片
再來一些名詞 連接圖 (connected graph) 子圖 (subgraph) 樹 (tree)沒有迴圈的連接圖 樹林 (forest) 一堆樹的群體 圖片來源：雷欽隆老師“資料結構”課投影片
有向圖(Digraph) 有向圖 (Digraph) 有向且無迴圈的圖 (directed acyclic graph) 圖片來源：雷欽隆老師“資料結構”課投影片
加權圖(Weighted Graph) 圖片來源：雷欽隆老師“資料結構”課投影片
生成樹(Spanning Tree) 包括圖中所有的頂點，並且是一顆樹 生成樹 圖片來源：雷欽隆老師“資料結構”課投影片
我為什麼要介紹圖論？
圖論在生活上有很多應用！ 電腦輔助設計電路 網路(道路, 航空,通信) 行程表 演算法 都市系統結構 建物動線分析
電路模擬 例：Pspice、Cadence、ADS….. Pspice Cadence 圖片來源：雷欽隆老師“資料結構”課投影片
網路 (道路, 航空,通信) 航空網路! 圖片來源：雷欽隆老師“資料結構”課投影片 捷運路線圖！
有向圖的應用！ 行程表！ 圖片來源：雷欽隆老師“資料結構”課投影片 有單行道的街道！
圖論的數學模型
圖的表示方法 邊串列 相鄰串列(第一種) 相鄰串列(第二種) 相鄰矩陣
“邊串列” 來表示圖 圖片來源：雷欽隆老師“資料結構”課投影片
相鄰串列 (第一種) 圖 串列 圖片來源：雷欽隆老師“資料結構”課投影片
相鄰串列 (第二種) 圖片來源：雷欽隆老師“資料結構”課投影片
“相鄰矩陣” 來表示圖
實際生活中的圖論
哥尼斯保七橋問題 (Bridges of Koenigsberg) 能不能走過每一個橋剛好一次並且回到原來的地方？ 圖片來源：雷欽隆老師“資料結構”課投影片
歐拉路徑解決哥尼斯保七橋問題 原來是一筆劃問題啊！ 圖片來源：雷欽隆老師“資料結構”課投影片
歐拉路徑 (Eular Path) 圖片來源：雷欽隆老師“資料結構”課投影片 一比畫問題=歐拉路徑走法！
哈密頓（Hamilton） 周遊世界問題 正十二面體有二十個頂點 表示世界上20個城市 各經每個城市一次 最後返回原地 投影至平面 哈密頓路徑至今尚無有效方法來解決！
最短路徑問題 (Shortest Path Problem) 最快的routing 最快航線 圖片來源：雷欽隆老師“資料結構”課投影片
最短路徑演算法Dijkstra演算法 可以求出從某一點到圖上其他任一點的最短路徑 圖片來源：雷欽隆老師“資料結構”課投影片
深度優先搜尋 (Depth-First Search) 一直往前走 碰壁就回頭換條路找 沿途要記錄下走過的路線 圖片來源：雷欽隆老師“資料結構”課投影片 老鼠走迷宮深度優先搜尋
使用歐拉路徑來畫Layout
參考資料 雷欽隆老師”資料結構”課程投影片 http://access.ee.ntu.edu.tw http://www.utc.edu/~cpmawata/petersen/ Paper: 沿著歐拉的足跡──圖論初探