|
圖形上之T-著色理論於1980年由Hale首先提出.Hale利用T-著色理論系統
解幾個頻道分配問題,並于以數學模式化.假如,某個區域擁有幾個無線電
傳送站,我們想對這幾個傳送站作頻道分配.首先,將每個傳送站看成一個
點而傳送站間之干擾現象視為相鄰,因此我們可以建立出一個干擾圖形.所
以,頻道分配可以利用著色理論來處理.然而,干擾之產生將使得頻道分配
有所限制,此限制乃是頻道間隔不可以落在某個集合內,此集合稱為T-集
合,因而產生T-著色.T-著色之主要目的在於找到有效的頻道分配,而能夠
將有限之頻道予以充分之運用.近年來,電視與廣播頻道早已不敷民眾之需
求,有關單位也明白到這一點,決定在近年內開放幾個電視及廣播頻道供民
眾申請使用.然而,在狹小的臺灣干擾現象必定相當嚴重.因此,如何將頻道
作有效之運用,將是一大課題.所以,我們有必要將T-著色理論做深入之探
討.在本論文中,我們首先介紹T-著色問題的來源,定義以及基本結果.1982
年,Cozzens 和 Roberts 證明了圖形的最小徑距介於兩個完全圖形的最小
徑距之間.因此,完全圖形之最小徑距是一個相當重要的問題.在第三章,我
們介紹完全圖形之最小徑距,包括Cozzens 和 Roberts 在 1982年以及
Raychaudhuri 在 1985年所分別提出之r - initial 與 k - multiple
of s 集合,以及一些學者所提出之特定T -集合的完全圖形最小徑距.1991
年,劉德芬博士利用T-graph 結合圖形的同態關係來處理 T-著色問題.我
們學習她的方法並利用此方法將Tesman(1989)所提出之T-集合加以擴充.
此外,我們亦找到r - initial of k 集合滿足性質(*).最後,我們介紹了
逐步演算法以及遞迴程序並提出幾個後續研究方向以供參考.
|