中国数学家管梅谷於-ncnucsie.PPT

圖 論 簡 介 大 綱 一. 圖論的起緣 二. 圖的定義 三. 圖論的應用 1.七座橋與一筆畫問題 2.環遊世界與漢米爾頓迴圈 3.廣播頻道與著色問題 4.存放藥品與獨立集問題 5.結婚定理與配對問題 6.電燈管道與覆蓋集問題 7.訊息流傳與傳播問題 8.電腦網路與最小斷集問題 四. 結論 一. 圖論的起緣 二. 圖的定義 三. 圖論的應用 1.七座橋與一筆畫問題 1.七座橋與一筆畫問題 2. 環遊世界與漢米爾頓迴圈 2. 環遊世界與漢米爾頓迴圈 3. 廣播頻道與著色問題 3. 廣播頻道與著色問題 圖形G上之著色(Coloring) : 在每一點塗上一個顏色, 使得有邊相連的點必須塗不同色。 3. 廣播頻道與著色問題 推廣問題, 如: 1. T-著色(T-coloring)問題: 在每一點塗上一個顏色, 使得有邊相連的點所塗之顏色差不落於集合T之內。 2. 連續T-著色(No-hole T-coloring)問題: 同T-著色問題, 但多了“所使用的顏色必須為連續”這一條件。 4. 存放藥品與獨立集問題 4. 存放藥品與獨立集問題 5. 結婚定理與配對問題 5. 結婚定理與配對問題 6. 電燈管道與覆蓋集問題 7. 訊息流傳與傳播問題 8. 電腦網路與連通度問題 8. 電腦網路與連通度問題 四. 結 論 * 圖論可說是起源於1736 年,瑞士數學家歐拉 (或譯尤拉Euler) , 歐拉解決了舊普魯士城 K?nisberg (現為Kaliningrad )的七橋問題 (K?nisberg’s seven bridge problem), 也因此產 生了圖形理論, 歐拉亦因此被尊為圖論之父。 1 2 3 4 5 6 7 V : vertex set (點集合); E : edge set (邊集合). Def : 一個圖 (Graph) G 通常用一組有序集合對(V,E)來描述之。其中V = {v1, v2, …, vn}代表點v1, v2, …, vn的集合；而 為邊集合，使得若vi vj ?E則表示點vi和點vj有一條邊相連。 對一個圖G而言, 通常以V(G)及E(G)分別代表其點集合及邊集合 1.七座橋與一筆畫問題 2.環遊世界與漢米爾頓迴圈 3.廣播頻道與著色問題 4.存放藥品與獨立集問題 5.結婚定理與配對問題 6.電燈管道與覆蓋集問題 7.訊息留傳與傳播問題 8.電腦網路與最小斷集問題 K?nisberg 的七橋問題: 舊普魯士城K?nisberg (現為Kaliningrad ) 位於Pregel河兩岸, 這個城的一部份為河中的兩個島, 共有七座橋相通, 如圖所示。城中居民一直為一個問題所困擾著：是否可從某處出發經過每座橋恰只一次, 然後再回到起點? 他們將這問題求教於瑞士數學家歐拉 (或譯尤拉Euler) , 歐拉解決了這個問題, 即是圖論上的一筆畫問題, 稱為歐拉迴路 (Euler tour)。 A B C D A B D C 推廣問題, 如中國郵差問題: 中國數學家管梅谷於1962年提出。郵差從郵局出發送信, 再轉回郵局, 每條街道都必須走過至少一次, 則其最短路徑為何? a d g b e h c f i a d g b e h c f i 環遊世界問題: 有個人想環遊世界，他選出全世界的二十個著名城世, 然後在地圖上開始他的作業。他打算規畫出一條路線, 使他可以依序地玩遍這二十個城市。但，問題是並不是任兩個城市皆有飛機直航, 而他又不願重覆去同一個城市兩次。這個問題轉化為圖論上便是所謂的漢米爾頓迴圈 (Hamilton Cycle)。於1857年愛爾蘭數學家漢米爾頓 (Sir William Hamilton)首次提出。 推廣問題: 我們可近一步地, 加入每段航程的距離(或是票價), 然後試圖找出最短的總飛行距離(或是最便宜的總票價)是怎樣的一條路線。這亦可利用圖論來解決。 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 廣播頻道問題: