系統識別號 | U0002-0107200712200300 |
---|---|
DOI | 10.6846/TKU.2007.00015 |
論文名稱(中文) | 完全三分圖分割成星狀圖的探討 |
論文名稱(英文) | Decompose complete tripartite graph into asteroidal graph |
第三語言論文名稱 | |
校院名稱 | 淡江大學 |
系所名稱(中文) | 數學學系碩士班 |
系所名稱(英文) | Department of Mathematics |
外國學位學校名稱 | |
外國學位學院名稱 | |
外國學位研究所名稱 | |
學年度 | 95 |
學期 | 2 |
出版年 | 96 |
研究生(中文) | 李維鴻 |
研究生(英文) | Wei-Hung Lee |
學號 | 694150169 |
學位類別 | 碩士 |
語言別 | 繁體中文 |
第二語言別 | |
口試日期 | 2007-06-06 |
論文頁數 | 36頁 |
口試委員 |
指導教授
-
高金美
委員 - 高金美 委員 - 傅恆霖 委員 - 周兆智 |
關鍵字(中) |
完全三分圖 迴圈 星狀圖 分割 |
關鍵字(英) |
complete tripartite graph cycle asteroidal graph decomposition |
第三語言關鍵字 | |
學科別分類 | |
中文摘要 |
在本篇論文中,我們主要是探討一個完全三分圖Kp,q,r是否能分割成三角星狀圖(簡稱星狀圖)。 我們先獲得Kp,q,r可以分割成星狀圖的必要條件,同時利用拉丁方陣進而得到若Kp,q,r可以分割成星狀圖,則Knp,nq,nr亦可以分割成星狀圖,對於一些特殊型態的p、q、r,我們獲得Kp,q,r的星狀圖分割,同時我們將所有q為6的倍數且q>=r>=q/2、5q/2>=p>=q的Kq,q,r與Kp,q,q分割成星狀圖,最後我們給予K2n,2n,2n分割成循環星狀圖的建構法。 |
英文摘要 |
In this thesis, we mainly discuss whether the complete tripartite graph Kp,q,r can be decomposed into asteroidal graphs. First we obtain the necessary condition of the decomposition of Kp,q,r into asteroidal graphs. By using latin square, we prove that if Kp,q,r can be decomposed into asteroidal graphs then Knp,nq,nr can do too. For the special values of p、q、r, we give the decompositions. We obtain that Kq,q,r and Kp,q,q can be decomposed into asteroidal graphs if q is multiple of 6 andq>=r>=q/2、5q/2>=p>=q. At last, we give a construction to get cyclic asteroidal graph decomposition of K2n,2n,2n. |
第三語言摘要 | |
論文目次 |
目錄 第一章 簡介……………………………………………………………1 第二章 預備知識………………………………………………………3 第三章 主要結果………………………………………………………9 第一節 Kp,q,r分割成星狀圖………………………………………9 第二節 Kp,p,r、Kp,r,r分割成星狀圖……………………………13 第三節 Kp,p,p分割成星狀圖………………………………………18 第四章 K2n,2n,2n分割成循環星狀圖………………………………20 附件…………………………………………………………………27 參考文獻…………………………………………………………36 圖表目錄 圖1………………………………………………………………………3 圖2………………………………………………………………………3 圖3………………………………………………………………………4 圖4………………………………………………………………………4 圖5………………………………………………………………………5 圖6………………………………………………………………………5 圖7………………………………………………………………………6 圖8………………………………………………………………………6 圖9………………………………………………………………………7 圖10……………………………………………………………………7 圖11……………………………………………………………………8 圖12……………………………………………………………………8 圖13……………………………………………………………………18 |
參考文獻 |
[1] E. J. Billington, D.G. Hoffman, Decomposition of complete tripartite graphs into gregarious 4-cycles, Discrete Math. 261(2003)87-111. [2] M. Buratti, A. Del Fra, Existence of cyclic k-cycle system of the complete graph, Discrete Math. 261(2003)113-125. [3] D. B. West, Introduction to graph theory 2nd Ed. 1996, 2001, Prenfice Hall, Inc |
論文全文使用權限 |
如有問題,歡迎洽詢!
圖書館數位資訊組 (02)2621-5656 轉 2487 或 來信