| 摘要: | 由於與其他數學結構的緊密連結，及其結果可廣泛地應用在其他領域， 圖形分解(graph decomposition)已成為圖形理論中 非常重要的一個主題。 均勻分解(balanced decomposition)及因子分解(factorization) 是兩種特定形式的分解問題， 其與組合設計(combinatorial design)有著密切的關聯性。 多重邊完全圖(complete multigraph)的均勻分解與因子分解， 分別對應於均勻不完全區塊設計(balanced imcomplete block design, BIBD) 與可分解設計(resolvable design)。 如今，這兩方面的研究仍極為盛行。 圖形分解有許多種類型，諸如完全圖分解(clique decomposition)、 星形分解(star decomposition)、路徑分解(path decomposition)、 迴路分解(cycle decomposition)以及 完全二部圖分解(complete bipartite decomposition)等等。 本論文主要在探討無向圖(undirected graph)之 均勻星形分解(balanced star decomposition)與 均勻路徑分解(balanced path decomposition)， 以及有向圖(digraph)之 有向星形因子分解(directed star factorization)與 有向路徑因子分解(directed path factorization)等問題。 本篇論文分成六章。首章我們介紹一些基本定義及所使用的符號。 在第二章中，我們探討均勻星形分解。 我們得到規則多重邊圖(regular multiple graph) 以及多重邊完全二部圖(complete bipartite multigraph) (當兩分部點數不同時，其為非規則圖)分解成均勻星形的充要條件。 在第三章中，我們探討路徑分解問題。 首先我們得到多重邊完全二部圖分解成均勻路徑的充要條件； 其次我們給予完全三部圖(complete tripartite graph) (分部之點數為奇數)分解成路徑之充要條件。 在第四章中，我們探討皇冠圖(crown)的 分解不變量(decomposition invariants)， 其中包含了路徑數(path number)、線性蔭度(linear arboricity) 以及星形蔭度(star arboricity)。 在第五章中，首先我們探討對稱皇冠圖(symmetric crown) 因子分解成有向星形及有向路徑之問題，並得到其充要條件。 其次我們探討對稱完全多部有向圖(symmetric complete multipartite digraph) 的星形因子分解問題，並給予一些充份條件。 在第六章中，我們 探討對稱完全二部有向圖(symmetric complete bipartite digraph) 的雙向星形分解(distar decomposition)問題， 並得到一些充份條件。 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. Balanced decomposition and factorization are special types of graph decomposition, and they have close connections to combinatorial designs. Balanced decompositions of complete multigraphs and factorizations of complete multigraphs correspond to blanced imcomplete block designs (BIBD) and resolvable designs, respectively. Nowadays, they continue to be popular topics of research. There are various decomposition problems such as clique decomposition, star decomposition, path decomposition, cycle decomposition, complete bipartite decomposition, and so on. In theis thesis, the problems of balanced star decomposition and balanced path decomposition of some graphs, and that of directed star factorization and directed path factorization of some digraphs are investigated. There are six chapters in this thesis. In Chapter 1, some basic definitions and notation are introduced. In Chapter 2, the balanced star decompositions of graphs are investigated. We first give a criterion for the balanced star decompositions of regular multiple graphs. We then give a necessary and sufficient condition for the existence of the balanced star decompositions of complete bipartite multigraphs which are not regular if the partite sets have different size. In Chapter 3, the path decomposition of graphs are studied. We first establish a necessary and sufficient condition for the balanced path decomposition of complete bipartite multigraph. We then give a criterion for the path decomposition of complete tripartite graph. In Chapter 4, we find some decomposition invariants of crown, which include the path number, linear arboricity and star arboricity. In Chapter 5, we first consider the problems of directed star factorizations and directed path factorizations of the symmetric crown, the necessary and sufficient conditions are given. We then study directed star factorization of the symmetric complete mutipartite digraph and give some sufficient conditions. In Chapter 6, we consider the problem of decomposing the symmetric complete bipartite digraph into distars, some sufficient conditions are given. |
