完全圖的{3，4，8}-圈分解.pdf

1、設(shè)Kv為完全圖，F(xiàn)為Kv的一個(gè)一因子(當(dāng)v≡0(mod 2)時(shí))，若(3)mi，3≤mi≤v，I=1，2，．．．，t，滿足條件：Kv(或Kv-F)=C1+C2+…+Gt，其中Gi的長度為mi，則稱Kv(或Kv-F)可以被mi長圈分解．
　　 顯然，完全圖可以被mi長圈分解的必要條件為：
　　 (I)3≤mi≤v，I=1，2，．．．，t；
　　 (ii)m1+m2+…+mt=v(v-1)/2(v≡1(mod 2))

2、；
　　 m1+m2+…+mt=v(v-2)/2(v≡0(mod 2))．
　　 關(guān)于這個(gè)必要條件是否也充分的問題由Alspach在1981[1]年提出．因此，被稱為Alspach猜想．
　　 這是一個(gè)非常大的猜想，要完全證明這個(gè)猜想是很困難的．自Alspach提出這個(gè)猜想以來，已證明成立的只有以下幾種情況：
　　 (1)v≤14；
　　 (2)m1=m2=…=mt；
　　 (3)mi∈A

3、，I=1，2，…，t．A∈{{3，4，5}，{3，4，6}，{4，6，8}，{4，10}，{6，10}，{8，10}，{3，v}，{u-2，v-1，v}}∪{{2k，2k+1}｜k≥2}．
　　 本文主要是通過對(duì)前人證明方法的綜合應(yīng)用，證明當(dāng)mi∈{3，4，8}時(shí)猜想成立．因?yàn)橛?長圈，3為奇數(shù)，而完全二部圖是不可能出現(xiàn)奇長圈的，這就使得在構(gòu)造過程中遇到了困難，所以這里我們應(yīng)用了一些技巧和方法．
　　 本文第二章第一部分

4、證明了當(dāng)v≡0(mod 2)時(shí)本文的結(jié)論成立．首先給出了將會(huì)用到的引理，然后主要運(yùn)用了若存在相應(yīng)的GDD，PBD，則它們可將Kn-F分解為若干個(gè)小階數(shù)的子圖，再通過討論解的情況將這些小階數(shù)子圖分解，就可得到結(jié)論．并不是所有情形都可以順利的用一種GDD或PBD來解決，在這時(shí)候，就要根據(jù)實(shí)際情況再用另外的GDD來重新對(duì)Kv-F進(jìn)行分解，討論．此外還有一些小階數(shù)的沒有相應(yīng)的GDD，就要另外再用其他方法來解決這個(gè)問題，比如特殊情況下的具體構(gòu)造．

5、第二部分是對(duì)于v≡(mod 2)時(shí)情況的證明．在證明時(shí)首先運(yùn)用了在mi∈{4，6，8}證明過程中用到的方法，即構(gòu)造路圖，拆圖重組．本節(jié)一開始就給出了v≡1(mod 2)時(shí)要用的重要引理，即若Kv-4的{3，4，8}-分解已經(jīng)得到，則Kv的{3，4，8}-圈分解中，C8的個(gè)數(shù)z≥(v-1)/2時(shí)就可以得到，再通過把Kv表示成幾個(gè)圖的并的方法來解決C8的個(gè)數(shù)z<(v-1)/2的情況．這樣，v≡1(mod 2)時(shí)的情況就都得到了．