Graph Theory 第四組 林宗翰 吳家豪

Outline 圖論的起源 圖論的一些名詞 圖論的應用

圖論的起源 Königsberg Bridges 如何才能不重複的 走完七座橋並且回 到原點

尤拉(Euler)解決了這個問題！ 將問題用「圖」表示 四塊被分開的區域作為點 連結他們的橋作為邊 原來是一筆畫問題！

什麼是圖 圖就是一堆點和邊的組合 一個圖可用G=(V,E)來表示 點(vertex)的集合V 邊(edge)的集合E 例；V={A,B,C,D,E} 邊(edge)的集合E 例；E={a,b,c,d,e,f,g} E e C c g a B b f A d D

如何表示一個圖呢─相鄰串列 A B C D E e B A C D C C A B E c g a D A B E B b f E C D

如何表示一個圖呢─相鄰矩陣 A B C D E A 0 1 1 1 0 B 1 0 1 1 0 C 1 1 0 0 1 g a B b f A d D

路徑(Path) 簡單路徑(Simple Path) 迴路(Cycle Loop) 無重複之邊的路徑 首尾相接的簡單路徑 例：A C B D E D B C C B A C B(重複了) 迴路(Cycle Loop) 首尾相接的簡單路徑 例：B D E C B E e C c g a B b f A d D

連通圖(Connected Graph) 圖中的任兩點，皆存在一連接的路徑 如果沒有 非連通圖 x y 連通圖 非連通圖

橋(Bridge) 若某兩點間所有路徑皆會經過某邊，則稱某邊為「橋」 若將橋拿掉，就會變成一非連通圖囉！ x y

有向圖(Digraph) 含有方向的圖就是有向圖啦！ 不含方向 無向圖

有向圖實例 ─ 道路圖

加權圖(Weighted Graph) 將每個邊賦予一實數值 山大大王 山小王 山大王 山大王 山小王 山小王 山小王 山小王 山大王

樹(Tree) 一個不含迴圈、 沒有方向、 且為連通的圖即為樹囉！ 若有n個點，則有n-1條邊 任兩點間僅有一簡單路徑

樹的實例 ─ 行政組織圖

生成樹(Spanning Tree) 可連接一個圖形所有點的『樹』，即為生成樹

可運用生成樹之實例

Graph Theory with Applications

Advanced Graph Theory Topics Minimum Spanning Tree Planar Graph Network Flows

Minimum Spanning Tree 一個weighted graph可含有多種spanning tree 所有邊的weight總和最小稱之為minimum spanning tree(最小生成樹)

解決最小生成樹問題 Kruskal’s Algorithm Prim’s Algorithm 將所有邊的weight做排序，從最小的邊開始連接所有的點，如果新加上去的邊會構成迴圈，則跳過，直到連接完所有的點為止。 Prim’s Algorithm 任選一點當作起點，從此點開始向外尋找最短邊連接到下一個點，避免構成迴圈並連接完所有的點為止。

Kruskal’s Algorithm 128個北美的城市連接出最短的路徑

最小生成樹的應用 都市設計、建物規劃 不適合用於通訊網路 建造電纜、鐵路、捷運 以樹的方式建造通訊網路，當任何一條連線發生故障時，將使得整個網路分為兩邊，無法互相通訊。

Planar Graph 一張在平面上的圖，其中沒有任何兩邊互相交叉 E-N+2=F (E:邊, N:點, F:面)

有些有交叉的圖也可經由修改而成為沒有任兩邊交叉，而成為一平面圖

任何平面圖都可經重新整理後，使得每一邊均為直線

如何判別一個圖是否可平面化？ Kuratowski’s 2 graphs K5: 一個有5個點的complete graph，具有最少點的不可平面化圖（5個點） K3,3: 具有六個點，每個點都連有三條邊的圖，具有最少邊的不可平面化圖（9個邊）

檢查圖中是否包含有K5或K3,3，若有包含任何一種，即為不可平面化。 先將圖化減 Series reduce Parallel reduce 檢查圖中是否包含有K5或K3,3，若有包含任何一種，即為不可平面化。

平面圖的應用 印刷電路板(printed circuit board) 大型積體電路(LSI)設計

Network Flows 一個weighted digraph Source and sink 邊上的數字即代表最大容量

Cut-sets: 一個由邊組成的集合，在圖中去掉這些邊，則圖會成為不連接圖(disconnect)

找出網路中所有的cut-sets有助於我們瞭解網路中脆弱的部分 如右圖的一個網路中，a是一個cut-set，只要a無法正常運作，則右上角的建築物的網路就會斷訊

Max-Flow Min-Cut Theorem 在Network當中，最大的流量就相當於所有的cut-sets當中，最小的容量總和。 Maximum flow = 10+8+7+4 = 29

Extension 一個網路中有多個sources和sinks 再增加兩個node分別代表新的source和sink連結到原來的source和sink，並將流量設為∞ 回到原來的單一source和sink問題

Network Flows的應用 網路流量問題 貨物運送問題 交通流量問題

結論 圖論可以應用的層面很廣，不論是電腦科學、電機工程、土木工程、社會學、經濟學都有廣泛的應用。 生活中很多問題都可以化簡成簡單的圖論模型來解決！

參考資料 Graph Theory with Applications to Engineering and Computer Science, Narsingh Deo, Prentice-Hall Inc., 1974 Graph Theory – An Algorithmic Approach, Nicos Christofides, Academic Press, 1975 http://www.cs.sunysb.edu/~skiena/combinatorica/animations/