完全圖K2n+1的2-因子分解

霍玉洪 (淮南師范學(xué)院數(shù)學(xué)與計(jì)算科學(xué)系，安徽 淮南 232038)

侴萬(wàn)禧 (安徽理工大學(xué)土木建筑學(xué)院，安徽 淮南 232001)

完全圖K2n+1的2-因子分解

霍玉洪 (淮南師范學(xué)院數(shù)學(xué)與計(jì)算科學(xué)系，安徽 淮南 232038)

侴萬(wàn)禧 (安徽理工大學(xué)土木建筑學(xué)院，安徽 淮南 232001)

以奇階完全圖K2n+1的1-因子分解為基礎(chǔ)，研究了奇階完全圖K2n+1的2-因子分解問(wèn)題，給出了奇階完全圖K2n+1和2-因子分解的具體步驟以及H圈的具體構(gòu)造方法，并以K13為具體實(shí)例進(jìn)行了分析研究。

完全圖；因子分解；奇階；H圈；矩陣

1 基本引理

引理2[7,8]設(shè)完全圖K2n+1的Δ(G)+1個(gè)1因子為E(G1),E(G2),…,E(GΔ(G)+1)，則K2n+1的2-因子分解可歸納為Δ(G)+1個(gè)1因子E(G1),E(G2),…,E(GΔ(G)+1)，并為n個(gè)H圈的邊集E(C1),E(C2),…,E(Cn)。

2 2-因子分解

設(shè)G為完全圖K2n+1，由引理1可得K2n+1的1-因子分解步驟如下：

E(C1)={12,22n,42n,42n-2,…,52n-1,32n-1,32n+1,12n+1}

E(C2)={13,32n-2,72n-2,42n-3,…,52n,12n}

E(C3)={14,46,62n,102n+1,…,23,32n-2,72n-1,12n-1}

…

E(Cn)={1n+1,2n+1,2n,3n,…,82n,82n+1,72n+1,1n+2}

3 實(shí) 例

下面以K13為例來(lái)具體分析分解步驟。

K13的2-因子分解決定于K13的Δ(G)+1=13個(gè)1因子E(G1),E(G2),…,E(G13)，而13個(gè)1因子E(G1),E(G2),…,E(G13)的構(gòu)造步驟如下：

K13的n=6個(gè)H圈的邊集E(C1),E(C2),…,E(C6)的構(gòu)造步驟如下：

E(C1)={12，212，412，410，610，68，78，79，59，511，311，313，113}

E(C2)={13，310，710，67，611，211，213，413，49，89，58，512，112}

E(C3)={14，48，810，210，23，39，69，612，1213，513，57，711，111}

E(C4)={15,56,613,1113,811,38,312,712,47,24,29,910,110}

E(C5)={16,46,34,37,713,1013,510,25,28,812,1112,911,19}

E(C6)={17,27,26,36,35,45,411,1011,1012,912,913,813,18}

[1]劉振宏.應(yīng)用組合論[M].北京：國(guó)防工業(yè)出版社,1993.

[2]孫淑玲,許胤龍.組合數(shù)學(xué)[M].合肥：中國(guó)科學(xué)技術(shù)大學(xué)出版社,1999.

[3]楊燁飛,王朝瑞.組合數(shù)學(xué)及其應(yīng)用[M].北京：北京理工大學(xué)出版社,1992.

[4]Fred S Roberts,Barry Tesmar.Apllied Combinatorics[M].Beijing:China Machine Press,2007.

[5]盧開(kāi)澄,盧華明.組合數(shù)學(xué)[M].北京：清華大學(xué)出版社,2006.

[6]van Lint J H，Wilson R M.A Course in Combinatorics[M].Beijing:China Machine Press,2004.

[7]侴萬(wàn)禧.2n名選手循環(huán)賽安排問(wèn)題[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),2006,36(2):252～256.

[8]侴萬(wàn)禧.2t名運(yùn)動(dòng)員的循環(huán)賽和對(duì)集的劃分[J].安徽理工大學(xué)學(xué)報(bào)(自然科學(xué)版),2006,26(1):64～69.

[編輯] 洪云飛

O157.5

A

1673-1409(2009)02-N016-03

2009-03-07

安徽省2009年高等學(xué)校省級(jí)自然科學(xué)研究項(xiàng)目(KJ2009B269Z)；淮南師范學(xué)院2007年度青年科研基金資助計(jì)劃項(xiàng)目資助(2007Lkp05)。

霍玉洪(1976-)，男，2000年大學(xué)畢業(yè)，碩士，講師，現(xiàn)主要從事應(yīng)用數(shù)學(xué)及圖論方面的研究工作。