完全圖分割成4-迴圈或漢米爾頓迴圈之探討

機構典藏 > College of Sciences > Department of Applied Mathematics and Data Science > Thesis > Item 987654321/51860

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

Title:	完全圖分割成4-迴圈或漢米爾頓迴圈之探討
Other Titles:	Decomposition of complete graph into 4-cycles or Hamilton cycles
Authors:	何婉嫙;Ho, Wan-hsuan
Contributors:	淡江大學數學學系碩士班高金美;Kau, Chin-mei
Keywords:	圖;完全圖;分割;迴圈;漢米爾頓迴圈;graph;complete graph;decomposition;cycle;Hamilton cycle
Date:	2010
Issue Date:	2010-09-23 16:13:17 (UTC+8)
Abstract:	當一個含有 n 個點的簡單圖中，任意兩點皆有邊相連，則稱此圖為完全圖，記為 K_n；當一個含有 n 個點的連通圖，若其每一個點的度數皆為 2，則稱此圖為 n-迴圈，記為 C_n。若一個完全圖 K_n可分割成4-迴圈或 n-迴圈是指 K_n中的邊可分割成一些邊均相異的4-迴圈或 n-迴圈，且這些迴圈之邊的聯集即為 K_n中的邊集合。在本篇論文中，我們證明了： (1) 當 n 為奇數且 n≥3 時，設 α,β 為正整數或零，若 4α+βn=(n(n-1))/2 ，則 K_n 可以分割成 α 個4-迴圈以及 β 個漢米爾頓迴圈。 (2) 當 n 為偶數且 n≥4 時，設 α,β 為正整數或零，若 4α+βn=(n(n-2))/2 ，則 K_n-I 可以分割成 α 個4-迴圈以及 β 個漢米爾頓迴圈，其中 I 為 K_n 的一個1-因子。 A complete graph with n vertices is a simple graph in which every pair of distinct vertices is connected by a unique edge, denoted by K_n. The cycle is a connected graph with n vertices which all vertices are degree 2 and denoted by C_n. A complete graph K_n can be decomposed into 4-cycles and n-cycles if K_n can be partitioned into edge-disjoint 4-cycles and n-cycles such that the union of edge sets of these cycles is the edge set of K_n. In this thesis, we prove that: (1) For odd integer n, n≥3, if there exists nonnegative integers α and β such that 4α+βn=(n(n-1))/2 , then K_n can be decomposed into α 4-cycles and β n-cycles. (2) For even integer n, n≥4, if there exists nonnegative integers α and β such that 4α+βn=(n(n-2))/2 , then K_n-I can be decomposed into α 4-cycles and β n-cycles, where I is a 1-factor of K_n.
Appears in Collections:	[應用數學與數據科學學系] 學位論文

Files in This Item:

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

Loading...