圖 論 簡 介
大 綱 一. 圖論的起緣 二. 圖的定義 三. 圖論的應用 1.七座橋與一筆畫問題 2.環遊世界與漢米爾頓迴圈 大 綱 一. 圖論的起緣 二. 圖的定義 三. 圖論的應用 1.七座橋與一筆畫問題 2.環遊世界與漢米爾頓迴圈 3.廣播頻道與著色問題 4.存放藥品與獨立集問題 5.結婚定理與配對問題 6.電燈管道與覆蓋集問題 7.訊息流傳與傳播問題 8.電腦網路與最小斷集問題 四. 結論
一. 圖論的起緣 圖論可說是起源於1736 年,瑞士數學家歐拉 (或譯尤拉Euler) , 歐拉解決了舊普魯士城 Könisberg (現為Kaliningrad )的七橋問題 (Könisberg’s seven bridge problem), 也因此產 生了圖形理論, 歐拉亦因此被尊為圖論之父。
對一個圖G而言, 通常以V(G)及E(G)分別代表其點集合及邊集合 二. 圖的定義 1 2 3 4 5 6 7 Def : 一個圖 (Graph) G 通常用一組有序集合對(V,E)來描述之。其中V = {v1, v2, …, vn}代表點v1, v2, …, vn的集合；而 為邊集合，使得若vi vj E則表示點vi和點vj有一條邊相連。 V : vertex set (點集合); E : edge set (邊集合). 對一個圖G而言, 通常以V(G)及E(G)分別代表其點集合及邊集合
三. 圖論的應用 1.七座橋與一筆畫問題 2.環遊世界與漢米爾頓迴圈 3.廣播頻道與著色問題 4.存放藥品與獨立集問題 5.結婚定理與配對問題 6.電燈管道與覆蓋集問題 7.訊息留傳與傳播問題 8.電腦網路與最小斷集問題
1.七座橋與一筆畫問題 Könisberg 的七橋問題: 舊普魯士城Könisberg (現為Kaliningrad ) 位於Pregel河兩岸, 這個城的一部份為河中的兩個島, 共有七座橋相通, 如圖所示。城中居民一直為一個問題所困擾著：是否可從某處出發經過每座橋恰只一次, 然後再回到起點? 他們將這問題求教於瑞士數學家歐拉 (或譯尤拉Euler) , 歐拉解決了這個問題, 即是圖論上的一筆畫問題, 稱為歐拉迴路 (Euler tour)。 A B D C A B C D
1.七座橋與一筆畫問題 推廣問題, 如中國郵差問題: 中國數學家管梅谷於1962年提出。郵差從郵局出發送信, 再轉回郵局, 每條街道都必須走過至少一次, 則其最短路徑為何? a d g b e h c f i a d g b e h c f i
2. 環遊世界與漢米爾頓迴圈 環遊世界問題: 有個人想環遊世界，他選出全世界的二十個著名城世, 然後在地圖上開始他的作業。他打算規畫出一條路線, 使他可以依序地玩遍這二十個城市。但，問題是並不是任兩個城市皆有飛機直航, 而他又不願重覆去同一個城市兩次。這個問題轉化為圖論上便是所謂的漢米爾頓迴圈 (Hamilton Cycle)。於1857年愛爾蘭數學家漢米爾頓 (Sir William Hamilton)首次提出。
2. 環遊世界與漢米爾頓迴圈 推廣問題: a b c d a b c d a b c d 我們可近一步地, 加入每段航程的距離(或是票價), 然後試圖找出最短的總飛行距離(或是最便宜的總票價)是怎樣的一條路線。這亦可利用圖論來解決。 a b c d 80 50 20 30 100 70 a b c d 80 50 20 30 100 70 80+70+50+100 = 300 a b c d 80 50 20 30 100 70 80+20+50+30 = 180 20 30 100 70 100+20+70+30 = 220
3. 廣播頻道與著色問題 廣播頻道問題: 當兩個廣播電台距離太近時, 若給相同的頻道將會產生干擾。那麼我們該如何給每個電台一個合適的頻道, 使得不相互干擾, 並且所使用的頻道總數最少? 這個問題放到圖型上來想, 則是一個基本的點著色問題(vertex coloring problem)。這個問題近年來被引申並廣泛的討論著。 A B
3. 廣播頻道與著色問題 圖形G上之著色(Coloring) : 在每一點塗上一個顏色, 使得有邊相連的點必須塗不同色。 2 1 3 1 2
3. 廣播頻道與著色問題 推廣問題, 如: 1. T-著色(T-coloring)問題: 2. 連續T-著色(No-hole T-coloring)問題: 同T-著色問題, 但多了“所使用的顏色必須為連續”這一條件。 T = {0, 1} T-coloring 2 T ={0, 1} NT-coloring 2 2 3 1
4. 存放藥品與獨立集問題 存放藥品問題: 某大學的化學系想存儲存一些化學藥品，但我們知道有些化學藥品，是很有可能因放置太近而發生反應，產生猛烈的爆炸。因此我們要將這些互相間有危險性的藥品分置兩實驗室中存放。若我們想知道，最多可有多少種藥品能同時存放於同一間實驗室，那麼將這個問題放到圖型上來想，則是在問一個圖上的最大獨立集個數, 稱為獨立數(Independent Number)。我們將可很容易的解答這個問題。 碰!!
4. 存放藥品與獨立集問題 存放藥品問題: 某大學的化學系想存儲存一些化學藥品，但我們知道有些化學藥品，是很有可能因放置太近而發生反應，產生猛烈的爆炸。因此我們要將這些互相間有危險性的藥品分置兩實驗室中存放。若我們想知道，最多可有多少種藥品能同時存放於同一間實驗室，那麼將這個問題放到圖型上來想，則是在問一個圖上的最大獨立集個數, 稱為獨立數(Independent Number)。我們將可很容易的解答這個問題。
5. 結婚定理與配對問題 配對問題: A C E A B C c b a D d E e c e A B C c b a A B C c b 一個紅娘節目要在十個男主角和十個女主角之間做一配對，使成對的組合越多越好。先決條件是每位女主角都交了一份“名單”，上面寫著她所願意接受的對象分別是那幾位。那麼決定是否能全數配對的條件為何呢? 解決的方法便是圖論上的Hall’s Theorem，也就是結婚定理。這是屬於圖論上完美配對問題 (Perfect Matching)所討論的部份。 A C E A B C c b a D d E e c e A B C c b a A B C c b a c e
5. 結婚定理與配對問題 代表團(SDR)問題: A B C c b a D d E e A = {c} B = {a, b, c} 一個城市裡的每個人都參加了若干個俱樂部, 現在要從每個俱樂部各選出一個代表組成代表團, 使得每個俱樂部的代表都不同; 亦即, 每一個人只能代表一個俱樂部出席代表團。則, “是否存在著這樣的代表團”這問題亦可用圖論上完美配對問題來解決。 A B C c b a D d E e A = {c} B = {a, b, c} C = {c, e} D = {a, c, d, e} E = {c, e} A = {a, c} B = {a, b, c} C = {c, e} D = {a, c, d, e} E = {c, e} A c C e E ? A a B b C c D d E e
6. 電燈管道與覆蓋集問題 電燈管道問題: 某座辦公大樓平面圖如下, 其中邊代表走廊, 點代表轉角口。而每道走廊都裝設了電燈, 其開關可設於此走廊兩端的轉角口其中之一。我們的目標是使安裝了開關的轉角口越少越好, 那麼該如何安裝才是最好的呢? 這個問題在圖論上就是圖上的覆蓋集 (Covering)問題。
7. 訊息流傳與傳播問題 訊息流傳問題: 班上有一件事情要宣佈，班代想打電話告訴全班。但若他一個個打似乎太慢了。假設一個班有五十個人，而打一通電話需要一分鐘，那總共就需要四十九分鐘。但若是他打了第一個電話之後，便請第一個同學再打給別人；而第二通電話打了之後，又再請第二個同學打給別人；依此類推，我們知道最快只需六分鐘便可讓全班都知道。但問題是，也許某些同學沒有某些同學的電話，那麼這時，想在最短時間內打完所有電話，便需要靠圖論幫助來解決。在圖論上我們稱這為傳播 (Broadcasting) 問題。 6次 5次
8. 電腦網路與連通度問題 電腦網路斷線問題: 有一公司內有多部電腦, 彼此之間拉了許多條線路互相連通, 我們想知道其網路設計的好不好。考慮若有某線路毀損後, 所有的電腦是否仍可保證彼此互通? 更進一步地, 討論此網路設計可保證在同時至多有幾條線路毀損後仍互通? 這個問題即等同於圖上的“連通度” ( Connectivity )問題。
8. 電腦網路與連通度問題 推廣問題: 如, 最大流量問題: 考慮有一運輸管線自甲地經過一些中繼站, 將物資運送至乙地。 若每條管線都有不同的最大負載量, 那麼最多一次能輸送多少物資至乙地呢? 這便是最大流量問題。這個問題可由圖論上的“網路” ( Network ) 上的最大流量(Maximum flow)問題來解決。 2+3+3+2 = 10 7 2 4 1 3 8 5 9 甲 乙 5 2 3 1 甲 乙 7+8 = 15
四. 結 論 圖論為一在二十世紀快速成長的一門學問。自原本只是組合數學書中一個章節的短短數頁, 如今已百倍增長為一可單獨研討之學科。它之所以會如此快速成長, 主要的原因是圖論的應用性非常之廣。諸如：物理, 化學, 生物, 心理學, 社會學等等。而另一個原因則是, 一些在電腦科學理論上, 處 理關於複雜度的問題, 亦能被轉換成圖論問題來解決。因此圖論已與我們的生活習習相關, 我們可預見的是, 圖論在未來將越來越受重視, 而圖論的研究也將更加蓬勃發展, 且讓我們拭目以待。
謝謝大家!! 有興趣歡迎選修圖論…