霍玉洪, 侴萬(wàn)禧, 李曉毅
(1.淮南師范學(xué)院數(shù)學(xué)與計(jì)算科學(xué)系,安徽淮南 232038;2.安徽理工大學(xué)土木建筑學(xué)院,安徽淮南 232001;3.沈陽(yáng)師范大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院,遼寧沈陽(yáng) 110034)
區(qū)組設(shè)計(jì)理論是組合數(shù)學(xué)的一個(gè)重要分支,它在試驗(yàn)設(shè)計(jì)、競(jìng)賽安排及數(shù)字通訊等許多領(lǐng)域中均有重要的作用。早在1850年,Kirkman[1]提出了一個(gè)有趣的“15名女生”的問(wèn)題,并于同年做出解答。1971年,D R Ray-Chaudhuri與R M Wilson[2-4]共同發(fā)表論文“Kirkman女生問(wèn)題的解”,以闡明6n+3階Kirkman三連系的構(gòu)造。百余年來(lái),就是否對(duì)每個(gè)n=0,1,2,3,…,總是存在6n+3階Kirkman三連系,一直是個(gè)難題。1971年,中國(guó)數(shù)學(xué)家陸家羲提出了BIBD設(shè)計(jì)可分解的充要條件[5]。
設(shè)G(V,E)為一個(gè)完全圖Kv,若完全圖Kv的階數(shù)V滿足v=3t-2,t為已存Steiner三連系的階數(shù),則v階Steiner三連系的構(gòu)造等價(jià)于一個(gè)完全圖Kv的v(v-1)/6個(gè)完全圖K3的分解。但是,當(dāng)完全圖Kv的階數(shù)較高時(shí),則無(wú)法將完全圖Kv直接分解出v(v-1)/6個(gè)完全圖K3。倘若將完全圖Kv先分解出3個(gè)t階完全圖及 1個(gè)完全三分圖,則3個(gè)t階完全圖中的3×t(t-1)/6個(gè)完全圖K3及1個(gè)完全三分圖中的(t-1)×(t-1)個(gè)完全圖K3構(gòu)成v=3t-2階Steiner三連系中的v(v-1)/6個(gè)完全圖K3,而將完全圖Kv分解出3個(gè)t階完全圖和1個(gè)完全三分圖的有力工具是完全圖Kv的邊矩陣。
定義1[5]設(shè)G(V,E)為一個(gè)完全圖Kv,若將完全圖Kv中的v(v-1)/2個(gè)邊按自然順序排成上三角陣,使得任意邊ViVj分別與頂Vi和頂Vj相關(guān)聯(lián),則所得到的上三角陣就稱為完全圖Kv的邊矩陣,并記為。
設(shè)v階Steiner三連系的階數(shù)v=s×t,s,t為已存的Steiner三連系的階數(shù),則s×t階Steiner三連系的構(gòu)造方案有兩種:方案A和方案B。
按照方案A構(gòu)造3×t階Steiner三連系的步驟如下:
步驟1:將完全圖Kv中的v(v-1)/2個(gè)邊排成邊矩陣。
按照方案B構(gòu)造s×t階Steiner三連系的步驟如下:
步驟1:將完全圖Kv中的v(v-1)/2個(gè)邊排成邊矩陣。
步驟2:將完全圖Kv的邊矩陣劃分為t個(gè)s階完全圖的邊矩陣,i=1,2,3,…,t,以及t(t-1)/2個(gè)完全二分圖的邊矩陣,i,j=1,2,…,t。
按方案A構(gòu)造21階Steiner三連系的具體步驟如下:
步驟1:將完全圖K21中的v(v-1)/2個(gè)邊排列成邊矩陣。
按方案B構(gòu)造21階Steiner三連系的具體步驟如下:
步驟1:將完全圖K21的v(v-1)/2個(gè)邊排列成邊矩陣。
從而得另一個(gè)21階Steiner三連系ST13(21)。
1)給出了用于圖論研究的一個(gè)工具——完全圖的邊矩陣,借助于它可將任意s×t階完全圖K3分解為v(v-1)/6個(gè)完全圖K3;
2)提出了s×t階Steiner三連系構(gòu)造的一種方法;
3)解決了s×t階Steiner三連系的計(jì)數(shù)問(wèn)題。
[1] VanLint J H,Wilson R M.A coarse in combinatorics[M].Beijing:China Machine Press,2004.
[2] Fred S Roberts,Barry Tesman.Applied combinatorics[M].Beijing:China Press,2007.
[3] Douglas B West.Introduction to graph theory[M]. Beijing:China Machine Press,2004.
[4] Foulds L R.Graph theory application[M].New York:Springer Verlag,1992.
[5] 楊驊飛,王朝瑞.組合數(shù)學(xué)及其應(yīng)用[M].北京:北京理工大學(xué)出版社,1992.
[6] 侴萬(wàn)禧.r×t階Kirkman三連系構(gòu)造的一種方法[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),2004,34(9):144-145.
[7] 侴萬(wàn)禧.高階Steiner三連系及其構(gòu)造方法[J].安徽理工大學(xué)學(xué)報(bào):自然科學(xué)版,2004,24(3):76-80.
[8] 侴萬(wàn)禧,黃云峰.20面體平圖的4著色與對(duì)偶樹的分解[J].長(zhǎng)春工業(yè)大學(xué)學(xué)報(bào):自然科學(xué)版,2008,29(6):623-627.