# 臺灣博碩士論文加值系統

(100.27.249.103) 您好！臺灣時間：2024/08/14 09:16

:::

### 詳目顯示

:

• 被引用:0
• 點閱:157
• 評分:
• 下載:0
• 書目收藏:0
 頻道設定的問題，主要是在尋找在整體的發送站區域中，要如何分配才能使的所使用的頻道的頻帶最小。這個問題早在1980年就有學者提出以圖論中的K-L(p,q) 標號問題來解決，一般而言，該問題為NP-complete。簡單的說，給定兩正整數p, q，且 ，一個圖形G=(V,E) 的k-L(p,q) 標號為頂點集合對應至0到k的整數之函數，使相鄰頂點的標號差不小於於p且距離為2的頂點標號差不小於q。使圖形G存在 標號之最小值k 稱為該圖之L(p,q) 標號數。本論文除了針對部分特定圖形討論其 標號數之外，亦提出即時標號的觀念，介紹即時標號的應用並探討特定圖形之即時標號的結果。
 The frequency assignment problem is finding the minimum range of frequencies needed for all transmitters in the whole area. In general, a K-l(p,q) labeling for a given graph G=(V,E) with positive integers p and q where p>q , is a function f:v->{0,1,...k} such that |f(x)-f(y)|>=p if d(x,y)=1 , and |f(x)-f(y)|>=q if d(x,y)=2 where d(x,y) is the distance bet en vertices x and y. The L(p,q) labeling number of G is the minimum k such that there exists a labeling of graph G. The k-L(p,q) labeling problem is finding the L(p,q) labeling number of graphs which has been proved to be NP-Complete. This thesis not only established the L(d,1) labeling number of some graphs but introduced on-line L(2,1) -labeling module and provided some labeling algorithms to achieve on-line -labeling number of some graphs.
 CONTENTSABSTRACT i中文摘要 ii致謝 iiiLIST OF FIGURES viLIST OF TABLES ixCHAPTER 1 INTRODUCTION 11.1 Motivation and Applications 11.2 Related Works 61.3 Organization 8CHAPTER 2 L(d,1) -LABELING 102.1 Cartesian Products of a Path With a Complete Bipartite Graph 102.2 Strong Product of a Path With a Complete Bipartite Graph 17CHAPTER 3 ONLINE -LABELING 343.1 Introduction 343.2 Paths 353.3 Cycles 41CHAPTER 4 ONLINE L(2,1) -LABELING OF TREES 454.1 Stars 454.2 Double Stars 474.3 Full Binary Trees 51CHAPTER 5 CONCLUSIONS AND FUTURE WORKS 565.1 Conclusions 565.2 Future Works 56REFERENCES 58
 [1] G. J. Chang, D. Kuo, “The L(2,1)-Labeling Problem on Graphs,” SIAM J. Discrete Math. 9, no.2, (1994) 309-316.[2] G. J. Chang, W. T. Ke, D. Kuo, D. D. F. Liu, R. K. Yeh, “On L(d,1)-labelings of graphs,” Discrete Mathematics 220, (2000) 55-66.[3] G. Chartrand, P. Zhang, “Introduction to Graph Theory,” McGraw-Hill co. 351-356.[4] H. B Chen, G. J. Chang, “Edge Spans of on Graphs”, Dept. of Applied Math., National Chioa Tung Univ., Hsinchu, Taiwan (2002).[5] M. L. Chia, “The of simple Graphs”, Combinatorics Conference, Kaoshiung Taiwan, August 10 (2007).[6] J. Clipperton, J. Gehrtz, Z. Szaniszlo, D. Torkornoo, “ of simple Graphs” Simpson College, July 11 (2005), available at:http://www.valpo.edu/mathcs/verum/papers/2006/L-3-2-1-Labeling.pdf .[7] D. J. Erwin, J. Georges, D. W. Mauro, “On labeling the vertices of products of complete graphs with distance constraints,” Naval Res. Logist. 52, (2005) 138-144.[8] G. Fertin, A. Raspaud, “L(p,q) Labeling of d-Dimensional Grids*,” Disc. Math. (2004) To appear.[9] P. C. Fishburn, F. S. Roberts, Minimum forbidden graphs for L(2, 1)-colorings, DIMACS Technical Report 2000-32, 2000.[10] Z. F□redi, J. R. Griggs and D. J. Kleitman, “Pair labeling with given distance,” SIAM J. Disc. Math. 2, (1989) 491-499.J. Georges, D. W. Mauro, “Generalized vertex labeling with a condition at distance two,” Congr. Numer. 109 (1995) 141-159.[11] J. Georges, D. W. Mauro, “On the criticality of graphs labeled with a condition at distance two,” Congr. Numer. 101 (1994) 33-49.[12] J. Georges, D. W. Mauro, “Generalized vertex labeling with a condition at distance two,” Congr. Numer. 109 (1995) 141-159.[13] J. Georges, D. W. Mauro, “Some results on of the products of complete graphs,” Congr. Numer. 140 (1999) 141-160.[14] J. Georges, D. W. Mauro, M. I. Stein, “Labeling products of complete graphs with a condition at distance two,” SIAM J. Discrete Math. 14 (2000) 28-35.[15] J. Georges, D. W. Mauro, and M. Whittlesey, “Relating path covering to vertex labelings with a condition at distance two,” Discrete Math. 135, no. 1-3, (1994) 103-111.[16] D. Goncalves, “On the of graph,” Discrete Mathematics and Theoretical Computer Science proc. AE, (2005) 81-86.[17] J. R. Griggs, X. T. Jin, Real number graph labellings with distance conditions, SIAM J. Disc. Math. 20 (2006) 302-327.[18] J. R. Griggs and R. K. Yeh, “Labeling graphs with a condition at distance 2,” SIAM J. Disc. Math. 5, (1992) 586-595.[19] W. K. Hale, “Frequency assignment: theory and applications,” proc. IEEE 68, (1980) 1497-1514.[20] P. K. Jha, “Optimal L(2,1)-labeling of Cartesian products of cycles with an application to independent domination,” IEEE Trans. Circuits and system-I 47 (2000) 1531-1534.[21] P. K. Jha, A. Narayanan, P. Sood, K. Sundaram, V. Sunder, “On L(2,1)-labeling of the Cartesian product of a cycle and path,” Ars Combin. 55(2000) 81-89.[22] X. T. Jin, R. K. Yeh, “Graph distance-dependent labeling related to code assignment in computer networks,” published online in Wiley InterScience, vol.52 (2005) 159-164, available at: http://www.interscience.wiley.com.[23] K. Jonas (1993), “Graph Coloring Analogues With a Condition at Distance Two: L(2,1)-Labelings and List λ-Labelings,” Ph.D thesis, Dept. of Math., Univ. of South Carolina, Columbia, SC.[24] D. Korze, A. Vesel, “L(2; 1)-Labeling of strong products of cycles.” Inform. Process. Lett. 94 (4) (2005) 183-190.[25] D. Kuo, J. H. Yan, “On L(2,1)-labeling of Cartesian products of paths and cycles, ” Discrete Math. 283 (2004) 137-144.[26] Z.D. Shao, R. K, Yeh, “The L(2,1)-labeling and operations of graphs,” IEEE Trans. Circuits and System-I52 (2005) 668-671.[27] C. Tiziana, C. Saverio, P. Rossella, “A general approach to L(h,k) label Interconnection networks,” Electronic Notes in Discrete Mathematics. 19 (2005) 211-217.[28] M. Whittlesey, J. Georges, D. W. Mauro, “On the -number of and related graphs,” SIAM J. Discrete Math. 8 (1995) 499-506.[29] R. K. Yeh, “The edge span of distance two labelings of graphs,” Taiwanese J. Math. 4 (2000) 675-683
 國圖紙本論文
 連結至畢業學校之論文網頁點我開啟連結註: 此連結為研究生畢業學校所提供，不一定有電子全文可供下載，若連結有誤，請點選上方之〝勘誤回報〞功能，我們會盡快修正，謝謝！
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 1 以正則圖探討頻道分配問題

 1 高子羽(2003年10月15日)。網路上的芭比娃娃 大家搶著玩 Avatar造型精靈 改變網路互動版圖。數位時代雙週刊電子版。2005年10月15日，取自： 2 吳怡銘 (2004年2月19日)。包山包海世代行銷一把罩。能力雜誌，174，68-73。 3 張玉佩（2005）。從媒體影像觀照自己：觀展╱表演典範之初探。新聞學研究，82: 41-85。

 1 非同步AVR微控器設計及實現 2 利用費頓試劑來氧化Potassiumindigotrisulfonate染料之可行性及動力學的研究 3 含泥厚度與含水量對岩石節理剪力行為之影響 4 應用於方位估測之陣列天線暨波束合成網路之微波元件精進 5 臺灣產鐵線蓮屬（毛茛科）分類研究 6 電漿技術應用於作物種子抑菌與發芽之影響 7 原子力顯微鏡用之溫度控制平台設計 8 誰是旅遊抱怨的最佳解藥？網路討論區之服務補救策略探討 9 祖父母的親職壓力與生活品質之關係研究 10 初任母親之社會支持與自我效能感之相關研究--以彰化縣為例 11 教育行政機構消息來源與媒體互動之研究 12 國中學生對國語文課程詮釋之研究--以一所鄉村學校為例 13 電腦合作學習在國小英語補救教學之研究 14 文蛤 ( Meretrix lusoria ) 組織中無氧終產物累積的研究 15 探究台灣大專學生在合作學習裡的互動類型、閱讀理解、及讀者回應

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室