Graph Theory Part II Applications in daily life 報告人：王文斕

Outline 圖的點著色(Vertex Coloring) 最小生成樹(Minimum Spanning Tree) 最短路徑問題(Shortest Path) 最大流量問題(Maximum Flow)

圖的點著色 (Vertex Coloring)

圖的點著色(Vertex Coloring) Question : 對一已知圖形的點著色, 若相鄰兩點的顏 色不能相同, 則最少需要多少種不同的顏 色才能填滿所有的點. 此問題可用廣度搜尋法解決 三部圖 二部圖

圖的點著色(Vertex Coloring) 日常生活中的例子 廣播頻道的選擇 選擇最少的頻道滿足最多的廣播電台, 而且彼此間不互相干擾

圖的點著色(Vertex Coloring) More in Vertex Coloring : T—著色問題(T-coloring) 對圖上每一點著色, 使相鄰兩點的顏色差(每種顏色被賦予一個值)不等於某幾個預設值 連續T—著色問題(No-hole T-coloring) 相似於T—著色問題, 但所用顏色的賦予值必須連續

最小生成樹 (Minimum Spanning Tree)

最小生成樹(Minimum Spanning Tree) Question : Given一個點集合和各點之間的連線(被 賦予不同的數值), 求出一條路徑使所有 的點相連且路徑上所有加權值的總和最 小. Main Algorithms: 1. Kruskal Algorithm 2. Prim Algorithm

最小生成樹(Minimum Spanning Tree) Kruskal Algorithm(用邊集) 由小到大排序為：ab, bc, de, fg, ad, be, dg, ce, bd, cf, eg, ef

最小生成樹(Minimum Spanning Tree) Kruskal Algorithm(用邊集) 由小到大排序為：ab, bc, de, fg, ad, be, dg, ce, bd, cf, eg, ef

最小生成樹(Minimum Spanning Tree) Kruskal Algorithm(用邊集) 由小到大排序為：ab, bc, de, fg, ad, be, dg, ce, bd, cf, eg, ef

最小生成樹(Minimum Spanning Tree) Kruskal Algorithm(用邊集) 由小到大排序為：ab, bc, de, fg, ad, be, dg, ce, bd, cf, eg, ef

最小生成樹(Minimum Spanning Tree) Kruskal Algorithm(用邊集) 由小到大排序為：ab, bc, de, fg, ad, be, dg, ce, bd, cf, eg, ef

最小生成樹(Minimum Spanning Tree) Kruskal Algorithm(用邊集) 由小到大排序為：ab, bc, de, fg, ad, be, dg, ce, bd, cf, eg, ef

最小生成樹(Minimum Spanning Tree) Kruskal Algorithm(用邊集) 由小到大排序為：ab, bc, de, fg, ad, be, dg, ce, bd, cf, eg, ef

最小生成樹(Minimum Spanning Tree) Kruskal Algorithm(用邊集) 由小到大排序為：ab, bc, de, fg, ad, be, dg, ce, bd, cf, eg, ef

最小生成樹(Minimum Spanning Tree) Kruskal Algorithm

最小生成樹(Minimum Spanning Tree) Prim Algorithm(用點集)

最小生成樹(Minimum Spanning Tree) Prim Algorithm(用點集)

最小生成樹(Minimum Spanning Tree) Prim Algorithm(用點集)

最小生成樹(Minimum Spanning Tree) Prim Algorithm(用點集)

最小生成樹(Minimum Spanning Tree) Prim Algorithm(用點集)

最小生成樹(Minimum Spanning Tree) Prim Algorithm(用點集)

最小生成樹(Minimum Spanning Tree) Prim Algorithm(用點集)

最小生成樹(Minimum Spanning Tree) Prim Algorithm(用點集)

最小生成樹(Minimum Spanning Tree) Prim Algorithm

最小生成樹(Minimum Spanning Tree) 日常生活中的例子 電信局配接電纜問題 電信總局要如何配接電纜才能使各電信局能互通訊息, 但同時令配線經費最低？

最小生成樹(Minimum Spanning Tree) 日常生活中的例子 大公司部門與部門之間的溝通管道

最短路徑問題 (Shortest Path)

最短路徑問題(Shortest Path) Question : Given 一圖, 求出從某一點到其他各點 的最短路徑(每邊可賦予不同的加權值). Main Algorithms: Dijkstra Algorithm 利用此演算法即可求出一網路中任兩點的最短路徑!

最短路徑問題(Shortest Path) Dijkstra Algorithm

最短路徑問題(Shortest Path) 日常生活中的例子 在 Internet 中 router 用來建 forwarding table 所用的routing protocol – Link State routing protocol.

最大流量問題 (Maximum Flow)

最大流量問題(Maximum Flow) Question : 已知一網路(每條邊上都有一流量值), 求 出由某點a (source)至另一點b (sink)所 能運載的最大流量. Main Algorithms: The Ford-Fulkerson method

最大流量問題(Maximum Flow)

最大流量問題(Maximum Flow) 日常生活中的例子 石油運輸管線— 若每條石油輸送管都有不同的最大負載量, 那麼要如何分配輸送量才能一次輸送最多石油到目的地呢?

結論 圖論是一種較為直接明暸的演算法 圖論涵蓋的範圍很廣, 內容也很豐富, 單就學術方面而言, 已有很大的發展空間和研究價值 在日常生活中, 我們經常可以找到與圖論息息相關的內容, 利用圖論我們可以更有效地解決問題

References Introduction To Algorithms, Ch.22-26, 2nd Edition, MIT Press 沿著歐拉的足跡—圖論初探 哥尼斯堡七橋問題與數學抽象 簡介圖論演算法, 數學傳播季刊 第19卷 第三期