臺灣博碩士論文加值系統

圖G可以用兩個集合V與E來表示它，即G=(V,E)，其中V是一非空的有限集合，稱為點集合， E是含有V中二個相異元素的子集所形成的集合，稱為邊集合。如果V中任兩點間，恰好有一個邊相連，則稱此圖為完全圖(complete graph)，若V中元素的個數為 n則稱為n點完全圖，記為Kn。若V中任兩點間，恰好有m個邊相連，則稱此圖形為m倍n點完全圖，記為mKn。如果考慮圖中每個邊都有方向性且V中任兩點間，恰好有相異兩個方向的邊相連，就叫此圖形為n點對稱有向完全圖，記為Kn*。圖形分割的問題，就是探討如何將一個圖G的邊分割成一些邊都相異的子圖。在1981年Alspach 提出，若且唯若m1+m2+…+mt=n(n-1)/2時，是否能將一個n點完全圖Kn分割成數個邊相異的環圈C1，C2，…，Ct，它們的長度分別為m1，m2，…，mt。若Ci(i=1,2,…,t)的長度皆相等且等於v，則稱這些長度為v的環圈所成的集合為n階v環圈系統(v-cycle system) 。若n點有向完全圖Kn*可分割成數個邊相異的有向環圈C1，C2，…，Ct，且Ci(i=1,2,…,t)的長度皆相等且等於v，則稱這些長度為v的有向環圈所成的集合為n階有向v環圈系統(directed v-cycle system)
在本篇論文中，我們將提出n點對稱有向完全圖Kn*分割成n-1有向環圈系統及2倍n點完全圖2Kn分割成n環圈系統的建構法，事實上由前者亦可得到在2倍n點完全圖2Kn分割成n-1環圈系統的建構法。

A graph can be described by two sets V and E. ie. G=(V,E) if V is a nonempty set, we called V a vertex set, E is a subset of two-element subset of V, we called E an edge set. If there is exactly one edge joining any pair of vertices of V and V contains n elements, we call G a complete graph with n vertices, denoted by Kn. If there are exactly m edges joining any pair of vertices of V, then we call G an m-fold complete graph with n vertices, Denote by mKn. If there are two edges with different directions connecting any pair of vertices in a complete graph with n vertices, then we call this graph a symmetric directed graph , denoted by Kn*. The decomposition problem is a problem which discusses how to decompose a graph G into edge-disjoint subgraphs of G.
In 1981, Alspach conjectured that if and only if m1+m2+…+mt=n(n-1)/2 then there is a decomposition of Kn into edge-disjoint cycles, C1,C2,…,Ct，where the length of Ci is mi, for i=1,2,…,t. If m1= m2= …= mt=v then we call the set of these cycles with length v a v cycle system of order n.
In this thesis. We discuss how to decompose Kn* into edge-disjoint directed cycles of length n-1 and 2Kn into edge-disjoint cycles of length n. We give constructions to both cases. At the same time, from the decomposition of Kn* we can get a decomposition of 2Kn.

第一章 緒論 ……………………………………1
第二章 基本定義 ………………………………..3
第三章 Kn*分割成n-1有向環圈系統 .….……..9
第四章 2Kn分割成n環圈系統 ……………….24
參考書目………………..………………………..31

1. Juraj Bosak, Decompositions of Graph, Kluwer Academic
Publishers, Dordrecht, The Netherlands.(1990).
2. P. Hell, and A. Rosa, Graph Decompositions, Handcuffed
Prisoners and Balanced p-Designs, Discrete Math. 2(1972)
229-252.