跳到主要內容

臺灣博碩士論文加值系統

(3.235.185.78) 您好!臺灣時間:2021/07/29 22:20
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:劉俊傑
研究生(外文):Jun-Jie Liu
論文名稱:在廣義稜鏡圖和環形網格圖上的反頻寬問題
論文名稱(外文):The Antibandwidth Problem on Generalized Prism Graphs and Tori
指導教授:王弘倫
指導教授(外文):Hung-Lung Wang
學位類別:碩士
校院名稱:國立臺北商業技術學院
系所名稱:資訊與決策科學研究所
學門:電算機學門
學類:電算機應用學類
論文種類:學術論文
論文出版年:2013
畢業學年度:101
語文別:中文
論文頁數:37
中文關鍵詞:廣義稜鏡圖環形網格圖反頻寬
外文關鍵詞:Generalized prism graphsToriAntibandwidth
相關次數:
  • 被引用被引用:0
  • 點閱點閱:111
  • 評分評分:
  • 下載下載:5
  • 收藏至我的研究室書目清單書目收藏:0
給定一個圖 G =(V,E),反頻寬問題是在每個點上放置 1,2,3,...,|V|的連續正整數中的一個值且不可重覆,使得相鄰點的差值中最小值為最大,該最大值以 ab(G)表示。在本篇論文中,我們研究廣義稜鏡圖 Pm x Cn 及環形網格圖 Cm x Cn 的反頻寬有一些成果如下:
(1) 對於偶數 n,假如 m ≥ n,則 ab(Pm x Cn)=n(m-1)/2;否則,ab(Pm x Cn)≥ n(m-1)/2。
(2) 對於奇數 n,假如 m ≤ n,則 ab(Pm x Cn)=m(n-1)/2;否則,ab(Pm x Cn)≥ m(n-1)/2。
(3) 假如 n 是偶數,ab(P2 x Cn)=n-2;否則,ab(P2 x Cn)=n-1。
(4) 對於偶數 n 和 m,若 m ≤ n,則 ab(Cm x Cn)≥ m(n-2)/2。
(5) 對於奇數 m 且偶數 n,若 m ≤ n,則 ab(Cm x Cn)= m(n-1)/2。
  The antibandwidth problem consists of placing the vertices of a graph on a line in consecutive integer points in such a way that the minimum difference of adjacent vertices is maximized. The corresponding maxmin value is denoted by ab(G). In this paper, we investigate the antibandwidth problem on generalized prism graphs Pm x Cn and tori Cm x Cn and obtain the following results:
(1) For even n, if m ≥ n, then ab(Pm x Cn)=n(m-1)/2; otherwise, ab(Pm x Cn)≥ n(m-1)/2.
(2) For odd n, if m ≤ n, then ab(Pm x Cn)=m(n-1)/2; otherwise, ab(Pm x Cn)≥ m(n-1)/2.
(3) If n is even, ab(P2 x Cn)=n-2; otherwise,ab(P2 x Cn)=n-1.
(4) For even n, m, if m ≤ n, ab(Cm x Cn)≥ m(n-2)/2.
(5) For odd m and even n, if m ≤ n, ab(Cm x Cn)= m(n-1)/2.
中文摘要 i
英文摘要 ii
誌謝 iii
目錄 iv
表目錄 vi
圖目錄 vii
一、緒論 1
1.1 研究動機與相關應用 1
1.2 符號定義 3
二、文獻探討 6
三、主要成果 12
3.1 ab(Pm x Cn)的下界 12
3.2 ab(P2 x Cn)的反頻寬 19
3.3 ab(Cm x Cn)的一些界限值 22
四、結論與未來研究方向 33
4.1 結論 33
4.2 未來研究方向 34
參考文獻 35
[1] J.-A. Bondy. Graph Theory. Murty, U.S.R.(2008).
[2] P. Cappanera. A survey on obnoxious facility location problems. University of Pisa, Technical Report, 1999.
[3] T. Calamoneri, A. Massini, I. Vrt'o, and L. Török. Antibandwidth of complete k-ary trees. Discrete Mathematics,
309(22):pp.6408-6414, 2009.
[4] S. Donnelly and G. Isaak. Hamiltonian powers in threshold and arborescent comparability graphs. Discrete Mathematics, 202(1-3):pp.33-44, 1999.
[5] J. Daz, J. Petit, and M. Serna. A survey of graph layout problems. ACM Computing Surveys (CSUR), 34(3):pp.313-356, 2002.
[6] W.-K. Hale. Frequency assignment: Theory and applications. Proceedings of the IEEE, 68(12):pp.1497-1514, 1980.
[7] Y. Hu, S. Kobourov, and S. Veeramoni. On maximum dierential graph coloring. In 14th Symposium on Graph drawing (GD), pp. 274-286, 2011.
[8] G. Isaak. Powers of hamiltonian paths in interval graphs. Journal of Graph Theory, 28(1):pp.31-38, 1998.
[9] T. Jiang, Z. Miller, and D. Pritikin. Separation numbers of trees. Theoretical Computer Science, 410(38-40):pp.3769-3781, 2009.
[10] W.-Y. Lin and A.-C. Chu. Antibandwidth of bipartite graphs. The 29th Workshop on Combinatiorial Mathematics and
Computation Theory, pp.191-195, 2012.
[11] J. Y.-T. Leung, O. Vornberger, and J.-D.
Witthoff. On some variants of the bandwidth minimization problem. SIAM Journal on Computing, 13(3):pp.650-667, 1984.
[12] Y.-X. Lin and J.-J. Yuan. The dual bandwidth problem for graphs. Journal of ZhengZhou University Natural Science
Edition, 35(1):pp.1-5, 2003.
[13] Z. Miller and D. Pritikin. On the separation number of a graph. Networks, 19(6):pp.651-666, 1989.
[14] A.-C. Mai and Z.-T. Wei. The vertex-neighbor-integrity of the cartesian product graphs. Journal of Henan Normal
University(Natural Science), 35(4):pp.8-10, 2007.
[15] A. Raspaud, H. Schroder, O. Sýkora, L. Török,
and I. Vrt'o. Antibandwidth and cyclic antibandwidth of meshes and hypercubes. Discrete Mathematics, 309(11):pp.3541-3552, 2009.
[16] Y. Saad and M.-H. Schultz. Topological properties of hypercubes. IEEE Computer Society, 37(7):pp.867{872, 1988.
[17] L. Török and I. Vrt'o. Antibandwidth of d-dimensional meshes. Combinatorial Algorithms: 20th International Workshop, IWOCA, LNCS 5874, pp.471-477, 2009.
[18] L. Török and I. Vrt'o. Antibandwidth of three-dimensional meshes. Discrete Mathematics, 310(3):pp.505-510, 2010.
[19] G. Wang, J. Chen and C. Lin. A new fault-tolerant broadcast routing algorithm on mesh networks. Journal of
Interconnection Networks, 11(3-4):pp.175-187, 2010.
[20] X.-H. Wang, X.-L. Wu, and S. Dumitrescu. On explicit formulas for bandwidth and antibandwidth of hypercubes. Discrete Applied Mathematics, 157(8):pp.1947-1952, 2009.
[21] W.-L. Yao, J. Zhou, and X.-X. Lu. Dual bandwidth of some special trees. Journal of ZhengZhou University Natural Science Edition, 35(3):pp.16-19, 2003.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文
 
1. 黃照貴、顏郁人 (2009),「以關係承諾觀點探討虛擬社群不同參與程度成員之行為」,《資訊管理學報》,16(_S),57-81。
2. 陳玉樹、謝宜栴 (2008),「師徒功能對工作績效的影響:以職場個人學習為中介效果.」,《中正教育研究》,7(2), 65-96。
3. 邱美秀 (2012),「融合質性與量化研究法以深化兒童數學學習情緒的研究」,《慈濟大學教育研究學刊》,(8),119-143。
4. 林靈宏、劉水深、洪順慶 (1994),「消費品類型、創新類型與新產品行銷策略關係研究」,《管理評論》,13(1),57-77。
5. 林金定、嚴嘉楓、陳美花 (2005),「質性研究方法:訪談模式與實施步驟分析」,《身心障礙研究季刊》,3(2), 122-136。
6. 林秀碧、林美珍、楊仁壽 (2006),「以紮根理論探討醫院常規的形成與演化機制」,《醫護科技學刊》,8(4),259-276。
7. 林世堂、蔣世寶、陳吟瑋 (2011),「應用紮根理論分析媒體設計科系學生對聲音設計之關注程度」,《嶺東學報》,(30), 23-72。
8. 吳克銳、徐振凱、鄭瑩妮 (2009),「以紮根理論建構陸航飛行員壓力模型」,《復興崗學報》,(95),103-126。
9. 何雍慶、吳文貴、佘溪水 (2006),「臺灣企業行銷研究活動之研究」,《輔仁管理評論》,13(1),57-84。
10. 繆敏志、張火燦、江宜芹 (2012),「獎賞敏感性與懲罰敏感性對工作績效之影響」,《文大商管學報》,17(1), 21-42。
11. 蔡淑敏、蔡雪惠 (2010),「臺灣金融保險業行銷策略之研究-以本土及外商人壽保險公司為例」,《東亞論壇》,(469), 101-116。
12. 歐陽彥慧(2009),「金融從業人員在工作不安定下對工作績效之影響-以工作壓力與工作投入為中介變項」,《華人經濟研究》,7(2),78-95。
13. 楊亨利、吳俊德 (2009),「群體能力、社會網絡與激勵政策對組織成員間知識分享的影響」,《資訊管理學報》,16(_S), 21-55。
14. 佘溪水、侯博仁 (2009),「關係行銷、顧客滿意度與忠誠度之研究-以高科技產業為例」,《聯大學報》,6(2),323-343。
15. 方世榮 (2002),「國際行銷通路關係管理的探討」,《臺大管理論叢》, 13(1),97-125。