圖論的介紹第二組徐榮德鄭又齊陳俊嘉.

圖論的介紹第二組徐榮德鄭又齊陳俊嘉

大綱圖論的基本介紹我為什麼要介紹圖論？圖論的數學模型實際生活中的圖論

圖論的基本介紹

什麼是圖？例一例二一堆頂點和邊的組合！

圖論的名詞頂點 (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
Paper: 沿著歐拉的足跡──圖論初探

Presentation on theme: "圖論的介紹第二組徐榮德鄭又齊陳俊嘉."— Presentation transcript: