完全二分圖K2m,2n分割成4、6、8、10迴圈之探討

淡江大學機構典藏 > 理學院 > 應用數學與數據科學學系 > 學位論文 > Item 987654321/32909

Please use this identifier to cite or link to this item: https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/32909

Title:	完全二分圖K2m,2n分割成4、6、8、10迴圈之探討
Other Titles:	The study of decompositions of k2m,2n into 4-cycles, 6-cycles, 8-cycles, or 10-cycles
Authors:	林遠隆;Lin, Yuan-lung
Contributors:	淡江大學數學學系碩士班高金美;Kau, Chin-mei
Keywords:	圖;二分圖;分割;迴圈;graph;bipartite graph;decomposition;cycle
Date:	2005
Issue Date:	2010-01-11 02:57:27 (UTC+8)
Abstract:	一個圖的點集合如果可分為兩個互不相交的非空集合，且同一集合中的任意兩點皆不相連，則稱此圖為ㄧ個二分圖，若在不同的集合中的任意兩點都有邊相連，則稱此圖為完全二分圖，並用Km,n來表示。ㄧ個完全二分圖Km,n能分割成一些子圖是指Km,n中的邊可以分成為一些邊均相異的子圖，且這些子圖的點集合的聯集為Km,n的點集合，邊集合的聯集為Km,n的邊集合。在本篇論文中，首先我們證明當2<m<12、2<n<10 時，對於每個非負整數p、q、r、s，只要4p+6q+8r+10s = 4mn，K2m,2n都可以分割成p個4-迴圈、q個6-迴圈、r個8-迴圈、s個10-迴圈。接著利用這些結果我們獲得對於m,n>2及非負整數p、q、r、s，若4p+6q+8r+10s = 4mn，則我們可將完全二分圖K2m,2n分割成p個4-迴圈、q個6-迴圈、r個8-迴圈、s個10-迴圈。 A graph is called a bipartite graph if the vertex set of the graph can be partitioned into two disjoint nonempty sets, and any two vertices in the same set are not adjacency. Moreover, if any two vertices in the different set are adjacency, then this bipartite graph is called a complete bipartite graph, and denoted by Km,n. A complete bipartite graph Km,n can be decomposed into some subgraphs if Km,n can be partitioned into edge-disjoint subgraphs, such that the union of vertex sets of these subgraphs is the vertex set of Km,n, and the union of edge sets is the edge set of Km,n. In this thesis, we show that when 2<m<12、2<n<10, if 4p+6q+8r+10s = 4mn, for all non-negative integers p, q, r, s, then K2m,2n can be decomposed into p 4-cycle, q 6-cycle, r 8-cycle, and s 10-cycle.By using above results, we obtain the following result. For all m,n>2 and non-negative integets p, q, r, s, if 4p+6q+8r+10s = 4mn, then K2m,2n can be decomposed into p 4-cycle, q 6-cycle, r 8-cycle, or s 10-cycle.
Appears in Collections:	[應用數學與數據科學學系] 學位論文

Files in This Item:

File	Size	Format
index.html	0Kb	HTML	427	View/Open

Loading...