圖論 (Graph Theory) B 電機四 大鳥 B 電機四 酋長 B 電機四 炫大

Presentation on theme: "圖論 (Graph Theory) B 電機四 大鳥 B 電機四 酋長 B 電機四 炫大"— Presentation transcript:

1 圖論 (Graph Theory) B88901031 電機四 大鳥 B88901115 電機四 酋長 B88901118 電機四 炫大
2018/11/24 on the fly

2 大綱…圖論 源起 範例 廣泛的應用面 定義 實際網路應用 結論 2018/11/24 on the fly

3 什麼是圖論？ 圖論亦稱「拓樸學」 探討由「點」及「線」構成的結構 任何一條線 兩邊一定有點 2018/11/24 on the fly

4 圖論的起源 著名的柯尼斯堡七橋問題 圖論的分析模型 2018/11/24 on the fly

5 圖論可以為我們做什麼？ 交通路網 電信 都市系統結構 建物動線分析 2018/11/24 on the fly

6 小例子 老鼠走迷宮 (Depth First Search) 2018/11/24 on the fly

7 小例子2 電腦輔助軟體 Cadence Protel 2018/11/24 on the fly

8 圖的基本定義 G = (V, E) V是點(vertices, nodes, points)的集合
E是線(edges, arcs, lines) 的集合。 V = {1,2,3,4}, E = {a, b, c, d} = { (1,2), (1,3), (2,3), (3,4)} 2018/11/24 on the fly

9 加權圖 G = (V, E)是一加權圖(weighted graph) 每個邊均相對應於一個可正可負的數值
權重 weight ( cost ) 2018/11/24 on the fly

10 路徑的定義 G = (V, E), i,jV, 點i到j的路徑是一個點串列 相鄰之點相應一個邊 eE
第十組 路徑的定義 G = (V, E), i,jV, 點i到j的路徑是一個點串列 相鄰之點相應一個邊 eE (1,3,5,8), (1,2,6,8), (1,2,5,3,2,5,8)均是1到8的路徑 2018/11/24 on the fly

11 簡單路徑和迴路 簡單路徑(simple path)是一無重複之邊的路徑 迴路(cycle, loop)是一首尾相接的簡單路徑
第十組 簡單路徑和迴路 簡單路徑(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/11/24 on the fly

12 樹的基本定義 樹(tree)是一個沒有迴路的無向圖 任二點之間，僅有唯一的(簡單)路徑
廣度優先搜尋法 (Breadth First Search) 深度優先搜尋法 (Depth First Search ) 2018/11/24 on the fly

13 尤拉圖 尤拉圖 (Euler circuit) 定義 應用 範例 經過圖的每個頂點 經過圖的每個邊 layout 2018/11/24
on the fly

14 尤拉圖的應用 Layout 2018/11/24 on the fly

15 圖與矩陣的對應 以矩陣表示 範例 2018/11/24 on the fly

16 Isomorphism 艾索莫非韌 (Isomorphism) 圖甲和圖乙是艾索莫非克(isomorphic) 範例
f 是映射函數 (one-to-one and onto) 若在圖甲中，頂點 v 和 w 是相鄰的，則在圖乙中對應的 f(v) 和 f(w) 相鄰 f 是頂點集合的函數 範例 2018/11/24 on the fly

17 平面圖的定義 平面圖 (planar graph) 一個可由立體圖轉換的平面圖，則： ｜V｜─｜E｜┼｜F｜＝ 2
V: vertices (頂點) E: edges (邊) F: faces (面) 2018/11/24 on the fly

18 平面圖範例 8個頂點(V=8) 12個邊 (E=12) 6個面 (F=6) 8-12+6=2 2018/11/24 on the fly

19 其它平面圖的範例 2018/11/24 on the fly

20 圖論在網路上的應用 最短路徑法 廣度優先搜尋法 (BFS,Breadth First Search) Dijstra’s 演算法
Bellman & Ford 演算法 Floyd & Warshall 演算法 2018/11/24 on the fly

21 Dijstra’s 演算法 2018/11/24 on the fly

22 Dijstra’s 演算法 Used to establish routing table
notation: (x)0, label x with 0 Begin (s)  0; (v)  , vs; /*  代表無限大 */ T  V; P  ; u  s; Repeat for each vertex vT 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/11/24 on the fly

23 Dijstra’s 演算法 T P U (S) (1) (2) (3) (4) (5) 12345  S ∞
∞ 2018/11/24 on the fly

24 Dijstra’s 演算法 T P U (S) (1) (2) (3) (4) (5) 12345  s ∞ 1345 2 5
∞ 1345 2 5 1 135 s2 4 3 2018/11/24 on the fly

25 Dijstra’s 演算法 T P U (S) (1) (2) (3) (4) (5) 12345  s ∞ 1345 2 5
∞ 1345 2 5 1 135 s2 4 3 13 s24 s245 6 2018/11/24 on the fly

26 Dijstra’s 演算法 T P U (S) (1) (2) (3) (4) (5) 12345  s ∞ 1345 2 5
∞ 1345 2 5 1 135 s2 4 3 13 s24 s245 6 s2451 無由 Node 5 指向 T 內的點，跳出for loop 2018/11/24 on the fly

27 圖論之應用 2 網路流量問題 2018/11/24 on the fly

28 網路流量問題 圖論可以解決簡單的流量問題 對一網路而言，其最大的流量為一條切割上的最小容量 容量 = 流出量 – 流入量 流入量 流出量
2018/11/24 on the fly

29 Labeling 演算法 2018/11/24 on the fly Begin
f(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 do begin /*scanning i */ for each unlabeled j such that f(i,j) < c(i,j) do /* forward labeling from i */ j  c(i,j) – f(i,j); (j)  (i+,j); for each unlabeled j such that f(j,i)>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   min{j | jV(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/11/24 on the fly

30 Labeling 演算法 2018/11/24 on the fly

31 Labeling 演算法 2018/11/24 on the fly

32 Labeling 演算法 2018/11/24 on the fly

33 結論 圖論是一種工具，可利用來簡化問題，或是將在圖論的定理應用到我們日常生活中的情形 善用圖學上的理論來解決問題 無所不在的圖論
Visio不錯用  2018/11/24 on the fly

34 最後叮嚀 麥當勞近日來營運不佳，已經倒了15家，請大家多多支持 麥當勞歡聚歡笑每一刻 2018/11/24 on the fly

35 參考資料 http://www.utc.edu/~cpmawata/petersen/
Graph theory Ronald Gould 2018/11/24 on the fly