English  |  正體中文  |  简体中文  |  Items with full text/Total items : 75533/75533 (100%)
Visitors : 27404555      Online Users : 386
RC Version 7.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
Scope Tips:
  • please add "double quotation mark" for query phrases to get precise results
  • please goto advance search for comprehansive author search
  • Adv. Search
    HomeLoginUploadHelpAboutAdminister Goto mobile version

    Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/7824

    Title: 圖形的路徑分解,迴路分解和星形分解;Path, Cycle and Star Decompositions of Graphs
    Authors: 李明茹;Ming-Ju Lee
    Contributors: 數學研究所
    Date: 2007-06-22
    Issue Date: 2009-09-22 11:06:24 (UTC+8)
    Publisher: 國立中央大學圖書館
    Abstract: 圖形分解是圖形理論中的一個非常重要的主題,因為許多數學結 構與圖形分解有相當緊密的聯結,而且圖形分解的結果可以廣泛的應用 到其他的領域。因子分解(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.
    Appears in Collections:[數學研究所] 博碩士論文

    Files in This Item:

    File SizeFormat

    All items in NCUIR are protected by copyright, with all rights reserved.

    社群 sharing

    ::: Copyright National Central University. | 國立中央大學圖書館版權所有 | 收藏本站 | 設為首頁 | 最佳瀏覽畫面: 1024*768 | 建站日期:8-24-2009 :::
    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - 隱私權政策聲明