資料載入中.....
|
請使用永久網址來引用或連結此文件:
http://ir.lib.ncu.edu.tw/handle/987654321/7824
|
| 題名: | 圖形的路徑分解,迴路分解和星形分解;Path, Cycle and Star Decompositions of Graphs |
| 作者: | 李明茹;Ming-Ju Lee |
| 貢獻者: | 數學研究所 |
| 日期: | 2007-06-22 |
| 上傳時間: | 2009-09-22 11:06:24 (UTC+8) |
| 出版者: | 國立中央大學圖書館 |
| 摘要: | 圖形分解是圖形理論中的一個非常重要的主題，因為許多數學結 構與圖形分解有相當緊密的聯結，而且圖形分解的結果可以廣泛的應用 到其他的領域。因子分解(factorization)是一種特殊型態的圖形分 解，其與組合設計(combinatorial design)有密不可分的關係。我們有 許多類型的分解問題，例如星型分解(star decomposition)、路徑分解 (path decomposition)、迴路分解(cycle decomposition)、完全二部 圖分解(complete bipartite decomposition)等等。直到今日，上述分 解依然是熱門討論話題。 在本篇論文中，某些有向圖的反向迴路(antidirected cycle)分 解和有向路徑分解與某些圖形的毛毛蟲因子分解(caterpillar factorization)的問題將被探討。圖形分解與圖形的蔭度(arboricity) 有著多樣且緊密的關係。本論文，我們同時會討論某些圖形的線性蔭度 (linear arboricity)與星形蔭度(star arboricity)。 本論文將分為七個章節來做探討。第一章將介紹基本的定義與符 號。第二章為探討圖形的路徑分解。首先，我們為完全三部多重邊圖的 同構路徑分解給定一個充分必要條件。接著探討完全三部多重有向邊圖 的同構有向路徑分解。第三章將對完全對稱圖形的反向迴路分解的存在 給定一個充分必要條件。第四章將對完全對稱圖形減去一因子 (one-factor)的反向迴路分解的存在給定一個充分必要條件。第五章將 討論皇冠圖(crown)中毛毛蟲的因子分解。首先給予在皇冠圖中均衡的 毛毛蟲因子分解一個充分必要條件。接著再給予在對稱皇冠圖中，有向 毛毛蟲因子分解的充分必要條件。第六章，首先考慮皇冠圖的星形蔭度 問題。先給定一個下界。接著探討在某些特定皇冠圖的星形蔭度。第七 章，我們考慮在某些特定k當中，完全圖的長度為k的線性蔭度(linear k-arboricity)問題。 Graph decomposition is an important subject of graph theory since many mathematical structures are linked to it and its result can be widely applied in other fields. The factorization is a special type of graph decomposition, and it has close connections to combinatorial designs. There are various decomposition problems such as clique decomposition, star decomposition, path decomposition, cycle decomposition, complete bipartite decomposition, and so on. Nowadays, they continue to be popular topics of research. In this thesis, the problems of antidirected cycle decomposition and directed path decomposition of some digraph, and that of caterpillar factorization of some graphs are investigated. There are various close connections between graph decomposition and the arboricity of a graph. In this thesis, we also show that the linear arboricity and the star arboricity of some graphs. There are seven chapters in this thesis. In Chapter 1, some basic definitions and notations are introduced. In Chapter 2, we first establish a necessary and sufficient condition for the isomorphic path decomposition of complete tripari tite multigraphs. We then investigate the isomorphic directed path decomposition of complete tripartite multidigraphs. In Chapter 3, we give a necessary and sufficient condition for the existence of the antidirected cycle decompositions of complete symmetric graphs. In Chapter 4, we give a necessary and sufficient condition for the existence of the antidirected cycle decompositions of complete symmetric graphs minus a one-factor. In Chapter 5, the caterpillar factorization of crowns are studied. We first establish a necessary and sufficient condition for the balanced caterpillar factorization of crowns. Then we give a necessary and sufficient condition for the directed caterpillar factorization of symmetric crowns. In Chapter 6, we first consider the problem of the star arboricity of crowns. A lower bound is given. Then we investigate the star arboricity of some special crowns. In Chapter 7, we consider the problem of the linear k-arboricity of complete graph Kn for some specific k. |
| 顯示於類別: | [數學研究所] 博碩士論文
|
在NCUIR中所有的資料項目都受到原著作權保護.
|
