關(guān)于Hamilton-Waterloo問(wèn)題的研究.pdf

1、組合設(shè)計(jì)理論是離散數(shù)學(xué)的一個(gè)重要分支，這一理論的基本問(wèn)題即是各類(lèi)設(shè)計(jì)的存在性與構(gòu)作，自1847年Kirkman[64，108]解決一類(lèi)經(jīng)典的設(shè)計(jì)即Steiner三元系的存在性問(wèn)題以來(lái)，關(guān)于組合設(shè)計(jì)的研究得到了蓬勃的發(fā)展.近幾十年來(lái)可分解設(shè)計(jì)尤其得到重視，歷史上著名的Kirkman女生問(wèn)題即是研究λ=1時(shí)的可分解三元系（即Kirkman三元系）的存在性，這一問(wèn)題歷經(jīng)一百多年，已經(jīng)由Ray-Chadhuri與Wilson[86]和陸家羲[7

2、9]分別獨(dú)立地予以解決.
　　區(qū)組設(shè)計(jì)的存在性問(wèn)題可以看作圖分解為完全子圖的問(wèn)題.如Steiner三元系即為完全圖的3階完全圖分解.在區(qū)組設(shè)計(jì)之后，圈設(shè)計(jì)自然地成為了圖的分解問(wèn)題的一個(gè)重要的研究對(duì)象.關(guān)于這一問(wèn)題的研究最早可以追溯到20世紀(jì)60年代，Kotzig[67]和Rosa[90]解決了完全圖K2xk+1的七-圈分解問(wèn)題.從那以后，圈分解問(wèn)題尤其是完全圖的可分解的圈分解問(wèn)題引起了很多專(zhuān)家學(xué)者的關(guān)注.關(guān)于這一問(wèn)題已有數(shù)百篇文章

3、發(fā)表.
　　在完全圖的圈分解問(wèn)題中，Oberwolfach問(wèn)題是其中重要的一類(lèi).這一問(wèn)題是Ringle于1967年在德國(guó)Oberwolfach召開(kāi)的圖論會(huì)議上提出的，它研究的是是否可以把完全圖分解成一些2-因子（2-正則生成子圖），使得所有的2-因子都同構(gòu)于一個(gè)給定的2-因子F.當(dāng)F由長(zhǎng)為3的圈組成時(shí)，此問(wèn)題即是Kirkman女生問(wèn)題，而當(dāng)F為一個(gè)Hamilton圈時(shí)，這一問(wèn)題就是完全圖的Hamilton圈分解問(wèn)題.
　　H

4、amilton-Waterloo問(wèn)題是Oberwolfach問(wèn)題的一個(gè)推廣.對(duì)于給定的2-因子R和S，Hamilton-Waterloo問(wèn)題研究是否能把完全圖Kn（當(dāng)n為奇數(shù)時(shí)）或Kn-In（當(dāng)n為偶數(shù)時(shí)，In為Kn的一個(gè)1-因子）分解為若干個(gè)2-因子，使得其中r個(gè)2-因子同構(gòu)于R，另外s個(gè)同構(gòu)于S.當(dāng)給定的兩個(gè)2-因子分別由長(zhǎng)為p和q的圈組成時(shí)，我們稱(chēng)這樣的2-因子分解是均勻的，此時(shí)記2-因子分解為HW(n;r，s;p，q).本文將對(duì)

5、均勻情形的Hamilton-Waterloo問(wèn)題展開(kāi)研究，重點(diǎn)研究其中一類(lèi)2-因子為Hamilton圈，另一類(lèi)2-因子由k長(zhǎng)圈構(gòu)成（記為Ck-因子）的情形，其中k為任意給定正整數(shù).
　　本文第一章將詳細(xì)介紹Hamilton-Waterloo問(wèn)題的歷史，研究進(jìn)展，研究方法及本文的主要結(jié)果.
　　在第二章中我們首先給出HW(n;r，s;p，q)存在的必要條件.然后分奇數(shù)階完全圖和偶數(shù)階完全圖兩種情況，對(duì)HW(n;r，s;n，2k

6、+1)的存在性展開(kāi)研究，證明了當(dāng)Hamilton圈的個(gè)數(shù)大于一個(gè)依賴(lài)于n和k的數(shù)時(shí)，相應(yīng)的2-因子分解是存在的.
　　第三章對(duì)n為偶數(shù)時(shí)HW(n;r，s;n，3)的存在性進(jìn)行深入的研究.當(dāng)n=0(mod18)時(shí)，我們利用擬Kirkman三元系的相關(guān)結(jié)果，除了3個(gè)情形外，證明了對(duì)于任意滿(mǎn)足第二章給出的必要條件的n，HW(n;r，s;n，3)均是存在的.當(dāng)n三6(mod18)時(shí)，我們利用Kirkman3-標(biāo)架設(shè)計(jì)的結(jié)果，除了r=1的情