k5时hamiltonwaterloo问题的研究

上传人:E**** 文档编号:118151102 上传时间:2019-12-11 格式:PDF 页数:44 大小:3.06MB
返回 下载 相关 举报
k5时hamiltonwaterloo问题的研究_第1页
第1页 / 共44页
k5时hamiltonwaterloo问题的研究_第2页
第2页 / 共44页
k5时hamiltonwaterloo问题的研究_第3页
第3页 / 共44页
k5时hamiltonwaterloo问题的研究_第4页
第4页 / 共44页
k5时hamiltonwaterloo问题的研究_第5页
第5页 / 共44页
点击查看更多>>
资源描述

《k5时hamiltonwaterloo问题的研究》由会员分享,可在线阅读,更多相关《k5时hamiltonwaterloo问题的研究(44页珍藏版)》请在金锄头文库上搜索。

1、上海交通大学 硕士学位论文 K=5时Hamilton-Waterloo问题的研究 姓名:赵鹏 申请学位级别:硕士 专业:数学 指导教师:沈灏 20090305 k = 5HamiltonWaterlooK Hamilton-WaterlooKKn2f)k r 2 f(2fQ?s2f,(2fR?P HW (n;r,s; Q,R).eKn2f)3K2fn1 2 l n 7 .w,2f7d|?Qdc1,c2, ,cq| Rdd1,d2, ,dt|PHW(n;c1,c2, ,cq;d1,d2, ,dt). ?QHamilton R3f(z2fd3| Pf)PHW(n;r,s;h,3)Horak169D

2、initz17d/ .?QHamilton R4fP HW (n;r,s; h,4)23 . ?QHamilton R 5 fPHW(n;r,s;h,5)PHW(r,s;h,5)d Hamilton- Waterloo KPHW.-HW(n)LT/evkr8. HW(r,s;h,5)35K=HW(n). HW (n; r,s; h,5) n = h 1 (mod 2) n = h 0 (mod 5)l n = h 5 (mod 10). dK zK10k+52f)K= HW (10k + 5; r,s; h,5)35l HW(10k + 5). Kn2f)g,I?E2f x a?EHWIHam

3、ilton5f.|a?E HW(10k + 5;r,s;h,5)e(J 1 ?a K10k+5 ?k 0 (mod 2)HW(10k + 5) ?5 2k + 2, 5 2k + 3, , 5k + 2 ? HW(10k + 5). ?k 2 (mod 5)HW(10k + 5) 0,2,3,4 ,4k + 2,5k + 2 HW(10k + 5). 3:?k 2 (mod 10)HW(10k + 5) 0,2,3, ,50t + 12HW(10k + 5) t N50t + 12 10k + 5. ?k = 1 HW(15) HW(15) = 0,1,2,3,4,5,6,7. =uK10k+

4、5?k 0 (mod 2)k 2 (mod 5)(l k 2 (mod 10) HW(10k + 5)k) d)?k = 1HW(15)k) ). c2f) x Hamilton5f -2- ?a Research on the Hamilton-Waterloo problem:The case of k = 5 Abstract The essential of the Hamilton-Waterloo problem is to research the 2 factorization of a complete graph Kn, in which r of the 2factors

5、 are isomorphic to a given 2factor Q and s of the 2factors are isomorphic to a given 2factor R, denoted HW(r,s;Q,R).It is easy to know that if there is a 2factorization of Kn, its number of 2factors is n1 2 , so n must be odd. It is obviously that the 2factors of a complete graph are consisted of cy

6、cles. We denote HW(n;c1,c2, ,cq;d1,d2, ,dt) when Q is consisted of cycles with c1,c2, ,cqlength, and R is consisted of cycles with d1, d2, ,dtlength. If Q is a complete graph s Hamilton cycle, and R is triangle factor(all the 2factors are consisted of cycles with 3 length, denoted factor), we denote

7、 it HW(n;r,s;h,3). Horak etc.16 and Dinitz17 have made the important research on this case. When Q is the complete graphs Hamilton cycle ,and R is 4 factor, we denote the problem HW(n;r,s;h,4). Luo Ming23 has done some research on this case. When Q is the complete graphs Hamilton cycle, and R is 5fa

8、ctor, we denote this case HW(n;r,s;h,5), or HW(r,s;h,5) abbreviatively. And we denote HWfor the Hamilton-Waterloo problem in this situation. Let HW(n) denotes the set of all the r which satisfi ed the conditions. This paper is to research the existence of the HW(r,s;h,5), namely to fi nd out the sol

9、ution of HW(n). We can see that in the HW(n;r,s;h,5) n = h 1 (mod 2),and n = h 0 (mod 5),so n = h 5 (mod 10). Then the problem could be simplifi ed to research the 2 factorization of K10k+5.That is , to research the existence of HW(10k + 5;r,s;h,5), then to get the solution of HW(10k + 5). Obviously

10、, to research the 2factorization of complete graph we need to construct the graphs 2factors. In this paper we use recursive diff erences method and mixed diff erence methodtwo important methodsto construct the Hamilton cycles and 5factors. By the strong construction tools, we get the following solut

11、ions -3- ?a of HW(10k + 5;r,s;h,5): For complete graph K10k+5,we give the partial solution of HW(10k + 5) when k 0 (mod 2): ?5 2k + 2, 5 2k + 3, , 5k + 2 ? HW(10k + 5). And we give the partial solution of HW(10k + 5) when k 2 (mod 5): 0,2,3,4 ,4k + 2,5k + 2 HW(10k + 5). Base of these we can get the

12、partial solution of HW(10k + 5) when k 2 (mod 10): 0,2,3, ,50t + 12HW(10k + 5) t N50t + 12 10k + 5. When t = 1,we give all the solution of HW(15): HW(15) = 0,1,2,3,4,5,6,7. All of above, for the complete graph K10k+5, when k 0 (mod 2),k 2 (mod 5) (so that k 2 (mod 10),HW(10k + 5) has solutions, and

13、we can give the partial of the solutions; When k = 1,HW(15) has solutions and we can get all of them. Key words: 2factorization, recursive diff erences, mixed diff erence, Hamilton cycle, 5-factors -4- ?a 1 1.10 Hamilton-WaterlooKCc5Jk|K KOberwolfachK.uOberwolfach Kk n Oberwolfach mIOt Sz Skai(1 i t) (u a1+ a2+ + at= nai 3)SzFY3n1 2 USz Tkk =kLg. OberwolfachK31967cdRingel3OberwolfachJl w:n Kn2f)K.KnL kn:Knf)fKnk fkK )f=Tfz:k.AKn 2 f 2K)f. OberwolfachKKn:?u?uX.duKnz2 fX uzdu?K S:= S .z8y.A Kn2f)

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 学术论文 > 其它学术论文

电脑版 |金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号