80+70+50+100 = 300
80+20+50+30 = 180
9
3. 廣播頻道與著色問題
廣播頻道問題:
當兩個廣播電台距離太近時, 若給相同的頻道將會產生干擾。那 麼我們該如何給每個電台一個合適的頻道, 使得不相互干擾, 並且所 使用的頻道總數最少? 這個問題放到圖型上來想, 則是一個基本的點 著色問題(vertex coloring problem)。這個問題近年來被引申並廣泛的 討論著。
碰!!
13
4. 存放藥品與獨立集問題
存放藥品問題:
某大學的化學系想存儲存一些化學藥品，但我們知道有些化學 藥品，是很有可能因放置太近而發生反應，產生猛烈的爆炸。因此 我們要將這些互相間有危險性的藥品分置兩實驗室中存放。若我們 想知道，最多可有多少種藥品能同時存放於同一間實驗室，那麼將 這個問題放到圖型上來想，則是在問一個圖上的最大獨立集個數, 稱 為獨立數(Independent Number)。我們將可很容易的解答這個問題。
A
A
C B
Байду номын сангаас
B
C
D
D
6
1.七座橋與一筆畫問題
推廣問題, 如中國郵差問題:
中國數學家管梅谷於1962年提出。郵差從郵局出發送信, 再轉回 郵局, 每條街道都必須走過至少一次, 則其最短路徑為何?
a
b
c
a
b
c
d
e
f
g
h
i
d
e
f
g
h
i
7
2. 環遊世界與漢米爾頓迴圈
環遊世界問題:
有個人想環遊世界，他選出全世界的二十個著名城世, 然後在地 圖上開始他的作業。他打算規畫出一條路線, 使他可以依序地玩遍這 二十個城市。但，問題是並不是任兩個城市皆有飛機直航, 而他又不 願重覆去同一個城市兩次。這個問題轉化為圖論上便是所謂的漢米 爾頓迴圈 (Hamilton Cycle)。於1857年愛爾蘭數學家漢米爾頓 (Sir William Hamilton)首次提出。
圖論簡介
1
大綱
一. 圖論的起緣 二. 圖的定義 三. 圖論的應用
1.七座橋與一筆畫問題 3.廣播頻道與著色問題 5.結婚定理與配對問題 7.訊息流傳與傳播問題
四. 結論
2.環遊世界與漢米爾頓迴圈 4.存放藥品與獨立集問題 6.電燈管道與覆蓋集問題 8.電腦網路與最小斷集問題
2
一. 圖論的起緣
圖論可說是起源於1736 年,瑞士數學家歐拉 (或譯尤拉 Euler) , 歐拉解決了舊普魯士城 Könisberg (現為Kaliningrad ) 的七橋問題 (Könisberg’s seven bridge problem), 也因此產 生了圖形理論, 歐拉亦因此被尊為圖論之父。
14
5. 結婚定理與配對問題
配對問題:
一個紅娘節目要在十個男主角和十個女主角之間做一配對，使
成對的組合越多越好。先決條件是每位女主角都交了一份“名單”，
上面寫著她所願意接受的對象分別是那幾位。那麼決定是否能全數
配對的條件為何呢? 解決的方法便是圖論上的Hall’s Theorem，也就
是結婚定理。這是屬於圖論上完美配對問題 (Perfect Matching)所討論
8
2. 環遊世界與漢米爾頓迴圈
推廣問題:
我們可近一步地, 加入每段航程的距離(或是票價), 然後試圖找出 最短的總飛行距離(或是最便宜的總票價)是怎樣的一條路線。這亦可 利用圖論來解決。
a
80
ca
80
ca
80
c
100
100
100
30
20 30
20 30
20
b
70
db
70
db
70
d
50
50
50
100+20+70+30 = 220
5
1.七座橋與一筆畫問題
Könisberg 的七橋問題:
舊普魯士城Könisberg (現為Kaliningrad ) 位於Pregel河兩岸, 這 個城的一部份為河中的兩個島, 共有七座橋相通, 如圖所示。城中 居民一直為一個問題所困擾著：是否可從某處出發經過每座橋恰只 一次, 然後再回到起點? 他們將這問題求教於瑞士數學家歐拉 (或譯尤 拉Euler) , 歐拉解決了這個問題, 即是圖論上的一筆畫問題, 稱為歐拉 迴路 (Euler tour)。
A
B
10
3. 廣播頻道與著色問題
圖形G上之著色(Coloring) :
在每一點塗上一個顏色, 使得有邊相連的點必須塗不同色。
0
1
2
3
0
1
0
1
1
0
0
2
11
3. 廣播頻道與著色問題
推廣問題, 如: 1. T-著色(T-coloring)問題:
在每一點塗上一個顏色, 使得有邊相連的點所塗之顏色差不落於集 合T之內。
3
二. 圖的定義
1
23
45
67 V1,2,3,4,5,6,7 E1,2,2 3,2 5,3 7,4 7,4 5,5 6,6 67
Def : 一個圖 (Graph) G 通常用一組有序集合對(V,E)來描述之。其中V =
{v1, v2, …, vn}代表點v1, v2, …, vn的集合；而 E { v ivj:1 i n ,1 j n } 為邊 集合，使得若vi vj E則表示點vi和點vj有一條邊相連。
的部份。
A
V : vertex set (點集合); E : edge set (邊集合).
對一個圖G而言, 通常以V(G)及E(G)分別代表其點集合及邊集合
4
三. 圖論的應用
1.七座橋與一筆畫問題 2.環遊世界與漢米爾頓迴圈 3.廣播頻道與著色問題 4.存放藥品與獨立集問題 5.結婚定理與配對問題 6.電燈管道與覆蓋集問題 7.訊息留傳與傳播問題 8.電腦網路與最小斷集問題
2. 連續T-著色(No-hole T-coloring)問題:
同T-著色問題, 但多了“所使用的顏色必須為連續”這一條件。
0
2
0
2
2
0
23
0
T = {0, 1}
T ={0, 1}
0
2 T-coloring 01
23 NT-coloring
12
4. 存放藥品與獨立集問題
存放藥品問題:
某大學的化學系想存儲存一些化學藥品，但我們知道有些化學 藥品，是很有可能因放置太近而發生反應，產生猛烈的爆炸。因此 我們要將這些互相間有危險性的藥品分置兩實驗室中存放。若我們 想知道，最多可有多少種藥品能同時存放於同一間實驗室，那麼將 這個問題放到圖型上來想，則是在問一個圖上的最大獨立集個數, 稱 為獨立數(Independent Number)。我們將可很容易的解答這個問題。