19階Steiner三連系的構(gòu)造與計(jì)數(shù)＊

鄭長波，李曉毅，侴萬禧

（1.大連海洋大學(xué)職業(yè)技術(shù)學(xué)院，遼寧大連 116300； 2.沈陽師范大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，遼寧沈陽 110034；3.安徽理工大學(xué)土木建筑學(xué)院，安徽淮南 232001）

區(qū)組設(shè)計(jì)理論是組合數(shù)學(xué)的一個(gè)重要分支，它在試驗(yàn)設(shè)計(jì)、競賽安排及數(shù)字通訊等許多領(lǐng)域中均具有重要作用.早在1850年，Kirkman提出了一個(gè)有趣的“15名女生”問題，并于同年做出解答［1－2］.1971年，D.R.Ray－Chaudhuri與R.M.Wilson共同發(fā)表論文《Kirkman女生問題的解》以闡明6n＋3階Kirkman三連系［3－4］.1961年，中國數(shù)學(xué)家陸家羲提出了BIBD設(shè)計(jì)可分解的充要條件［5－9］.在區(qū)組設(shè)計(jì)中，有一種稱為t－（v，k，λ）設(shè)計(jì)，是指由一個(gè)v元集X和X中某些k元子集（區(qū)組）族β所組成的序?qū)?，使得X中任意t元子集都恰含于λ個(gè)區(qū)組之中，當(dāng)λ＝1，k＝3時(shí)稱為Steiner三連系.

1 基本思路

定義1 設(shè)CT（V，E）為完全圖Kv，若完全圖Kv中的v（v－1）／2個(gè)邊可排成上三角陣，使得Kv中的任意邊Vi，Vj分別與項(xiàng)Vi和項(xiàng)Vj關(guān)聯(lián)，則所得到的上三角陣就稱為邊矩陣，并記為.

v階Steiner三連系可視為完全圖Kv的v（v－1）／6個(gè)完全圖的K3的分解，若直接將完全圖Kv分解出v（v－1）／6個(gè)完全圖K3的困難極大，倘若將完全圖K3的邊矩陣先分解出若干個(gè)已存在的完全圖和若干個(gè)完全三分圖，再將各個(gè)完全圖分解出t（t－1）／6個(gè)完全圖K3，將各個(gè)完全三分圖分解出s×s個(gè)完全圖K3，所得到的全部完全圖K3就構(gòu)成v階Steiner三連

系［2，10－12］.

命題1 設(shè)完全圖Kv的階數(shù)v≡1（mod 2）且（v－1）／2＝t，t為已存的Steiner三連系的階數(shù)，則v階Steiner三連系的構(gòu)造等價(jià)于完全圖Kv的s＝t－1個(gè)t階完全圖，，…，和m＝t（t－1）／2個(gè)完全二分圖，，…，，或n＝t（t－2）／6個(gè)完全三分圖，，…，的分解，每個(gè)完全三分圖＝∪∪.因?yàn)閟＝t－1個(gè)完全圖，，…，為v階Steiner三連系貢獻(xiàn)s×t（t－1）／2個(gè)完全圖K3，n＝t（t－2）／6個(gè)完全三分圖為v階Steiner三連系貢獻(xiàn)s×s×t（t－1）／2個(gè)完全圖K3，全部v（v－1）／6個(gè)完全圖K3恰好是v階Steiner三連系的v（v－1）／6個(gè)區(qū)組［13－15］.

2 19階Steiner三連系

2.1 構(gòu)造方案A

按照方案A構(gòu)造19階Steiner三連系的具體步驟是：

Step 1：將完全圖K19的19×18／2＝171個(gè)邊排成上三角陣，使得任意邊Vi，Vj分別與項(xiàng)Vi和項(xiàng)Vj關(guān)聯(lián)，得邊矩陣.

Step 4：讓t（t－1）／6＝12個(gè)2×2的三連系矩陣中的t（t－1）／6×2×2＝48個(gè)完全圖K3與，，…，構(gòu)成1個(gè)19階Steiner三連系ST（19）：

2.2 構(gòu)造方案B

按照構(gòu)造方案B進(jìn)行19階Steiner三連系構(gòu)造的具體步驟是：

Step 1：同上；

Step 4：將（v－1）／（t－1）＝3個(gè)t＝7階完全圖，，各分解出7個(gè)完全圖K3，得3×7＝21個(gè)完全圖K3.

3 結(jié) 語

基于邊矩陣的子矩陣分解的Steiner三連系的構(gòu)造方法，適用于v≡1（mod t）的v階Steiner三連系的構(gòu)造.構(gòu)造結(jié)果表明：v元集X上的每個(gè)元素恰好出現(xiàn)于r個(gè)區(qū)組中；X的每兩個(gè)元素恰好出現(xiàn)于λ個(gè)區(qū)間組中.若按方案A構(gòu)造Steiner三連系，Steiner三連系的個(gè)數(shù)NA決定于19階Steiner三連系的個(gè)數(shù)N1＝9和完全三分圖的三連系邊矩陣的完全圖K3的分解方案數(shù)N2＝2，故NA＝N1×N2＝14.若按方案B構(gòu)造Steiner三連系，Steiner三連系的個(gè)數(shù)NB決定于3個(gè)7階Steiner三連系的完全圖K3的分解方案數(shù)＝7及完全二分圖的6×6個(gè)完全圖K3的分解方案數(shù)＝6，即有NB＝×＝42.Steiner三連系的總數(shù)可達(dá)N＝NA＋NB＝56個(gè).

綜上，文中的Steiner三連系的構(gòu)造方法和計(jì)數(shù)方法是有效可行的，對Steiner三連系的構(gòu)造方法和計(jì)數(shù)方法具有一定的參考價(jià)值和可推廣性.

［1］ VAN LINT J H，WILSON R M.A course in combinatorics［M］.Beijing：China Machine Press，2004.

［2］ ROBERTS F S，TESMAN B.Applied combinatorics［M］.Beijing：China Machine Press，2007.

［3］ WEST D B.Introduction to graph theory［M］.Beijing：China Machine Press，2004.

［4］ FOULDS L R.Graph theory applications［M］.New York：Springer－Verlag，1992.

［5］ 陸家羲.可分解平衡不完全區(qū)組設(shè)計(jì)的存在性理論［J］.數(shù)學(xué)學(xué)報(bào)，1984，27（4）：28－38.LU Jia－xi.Incomplete block design with biodegradable balance of existence theory［J］.Acta Mathematica Sinica，1984，27（4）：28－38.（In Chinese）

［6］ 康慶德.斯坦納和柯克曼三元系及大集問題［J］.自然雜志，1985，8（6）：61－67.KANG Qing－de.Steiner and Kirkman triple systems and set problem［J］.Nature Magazine，1985，8（6）：61－67.（In Chinese）

［7］ 徐道.Steiner分割問題的進(jìn)一步探討［J］.數(shù)學(xué)通報(bào)，1995，45（1）：41－44.XU Dao.Further explore for Steiner segmentation problem［J］.Shuxue Tongbao，1995，45（1）：41－44.（In Chinese）

［8］ 羅見今.Steiner系若干課題研究的歷史回顧——陸家羲學(xué)術(shù)工作背景概述［J］.數(shù)學(xué)進(jìn)展，1986，75（2）：175－184.LUO Jian－jin.Historical review of the Steiner system research—an overview of Jiayi Lu＇s academic background［J］.Advances in Mathematics，1986，75（2）：175－184.（In Chinese）

［9］ 吳利生.關(guān)于S（2，3，υ）的大集和RBIB的存在性問題——我國組合數(shù)學(xué)工作者陸家羲同志的貢獻(xiàn)［J］.數(shù)學(xué)研究與評論，1984，4（1）：151－154.WU Li－sheng.Existence problem for about set S（2，3，υ）and RBIB—the contribution of Chinese combinatorial mathematics workers Jiayi Lu Comrade［J］.Journal of Mathematical Research and Exposition，1984，4（1）：151－154.（In Chinese）

［10］張瑾，馬良.基于加權(quán)絕對值距離Steiner最優(yōu)樹的選址問題［J］.數(shù)學(xué)的認(rèn)識與實(shí)踐，2008，38（16）：80－84.ZHANG Jin，MA Liang.A location problem based on the weighted rectilinear Steiner minimal tree［J］.Mathematics in Practice and Theory，2008，38（16）：80－84.（In Chinese）

［11］越民義，程叢電.關(guān)于Steiner問題的一個(gè)注記——連接五點(diǎn)之最小網(wǎng)絡(luò)的一種尋優(yōu)方案［J］.運(yùn)籌學(xué)學(xué)報(bào)，2010，14（1）：1－14.YUE Min－yi，CHENG Cong－dian.A note on the Steiner problem—an approach to find the minimal network with five given points［J］.Or Transactions，2010，14（1）：1－14.（In Chinese）

［12］侴萬禧.r×t階Kirkman三連系構(gòu)造的一種方法［J］.數(shù)學(xué)的實(shí)踐與認(rèn)識，2004，34（9）：144－145.CHOU Wan－xi.A method of constructing Kirkman triple system of order r×t［J］.Mathematics in Practice and Theory，2004，34（9）：144－145.（In Chinese）

［13］侴萬禧.高階Steiner三連系及其構(gòu)造方法［J］.安徽理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2004，24（3）：76－80.CHOU Wan－xi.Steiner triple system and its construction method［J］.Journal of Anhui University of Science and Technology：Natural Science，2004，24（3）：76－80.（In Chinese）

［14］侴萬禧，李曉毅.完全圖K5中的生成樹的構(gòu)造與計(jì)數(shù)［J］.沈陽師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，28（3）：327－330.CHOU Wan－xi，LI Xiao－yi.Construction and counting of spanning tree in complete graph K5［J］.Journal of Shenyang Normal University：Natural Science Edition，2010，28（3）：327－330.（In Chinese）

［15］侴萬禧，李曉毅.49階Steiner三連系的構(gòu)造與計(jì)數(shù)［J］.長春工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2009，30（6）：623－628.CHOU Wan－xi，LI Xiao－yi.Construction and numeration of Steiner triple systems of order 49［J］.Journal of Changchun University of Technology：Natural Science Edition，2009，30（6）：623－628.（In Chinese）