19阶Steiner三连系的构造与计数＊

郑长波，李晓毅，侴万禧

（1.大连海洋大学职业技术学院，辽宁大连 116300； 2.沈阳师范大学数学与系统科学学院，辽宁沈阳 110034；3.安徽理工大学土木建筑学院，安徽淮南 232001）

区组设计理论是组合数学的一个重要分支，它在试验设计、竞赛安排及数字通讯等许多领域中均具有重要作用.早在1850年，Kirkman提出了一个有趣的“15名女生”问题，并于同年做出解答［1－2］.1971年，D.R.Ray－Chaudhuri与R.M.Wilson共同发表论文《Kirkman女生问题的解》以阐明6n＋3阶Kirkman三连系［3－4］.1961年，中国数学家陆家羲提出了BIBD设计可分解的充要条件［5－9］.在区组设计中，有一种称为t－（v，k，λ）设计，是指由一个v元集X和X中某些k元子集（区组）族β所组成的序对，使得X中任意t元子集都恰含于λ个区组之中，当λ＝1，k＝3时称为Steiner三连系.

1 基本思路

定义1 设CT（V，E）为完全图Kv，若完全图Kv中的v（v－1）／2个边可排成上三角阵，使得Kv中的任意边Vi，Vj分别与项Vi和项Vj关联，则所得到的上三角阵就称为边矩阵，并记为.

v阶Steiner三连系可视为完全图Kv的v（v－1）／6个完全图的K3的分解，若直接将完全图Kv分解出v（v－1）／6个完全图K3的困难极大，倘若将完全图K3的边矩阵先分解出若干个已存在的完全图和若干个完全三分图，再将各个完全图分解出t（t－1）／6个完全图K3，将各个完全三分图分解出s×s个完全图K3，所得到的全部完全图K3就构成v阶Steiner三连

系［2，10－12］.

命题1 设完全图Kv的阶数v≡1（mod 2）且（v－1）／2＝t，t为已存的Steiner三连系的阶数，则v阶Steiner三连系的构造等价于完全图Kv的s＝t－1个t阶完全图，，…，和m＝t（t－1）／2个完全二分图，，…，，或n＝t（t－2）／6个完全三分图，，…，的分解，每个完全三分图＝∪∪.因为s＝t－1个完全图，，…，为v阶Steiner三连系贡献s×t（t－1）／2个完全图K3，n＝t（t－2）／6个完全三分图为v阶Steiner三连系贡献s×s×t（t－1）／2个完全图K3，全部v（v－1）／6个完全图K3恰好是v阶Steiner三连系的v（v－1）／6个区组［13－15］.

2 19阶Steiner三连系

2.1 构造方案A

按照方案A构造19阶Steiner三连系的具体步骤是：

Step 1：将完全图K19的19×18／2＝171个边排成上三角阵，使得任意边Vi，Vj分别与项Vi和项Vj关联，得边矩阵.

Step 4：让t（t－1）／6＝12个2×2的三连系矩阵中的t（t－1）／6×2×2＝48个完全图K3与，，…，构成1个19阶Steiner三连系ST（19）：

2.2 构造方案B

按照构造方案B进行19阶Steiner三连系构造的具体步骤是：

Step 1：同上；

Step 4：将（v－1）／（t－1）＝3个t＝7阶完全图，，各分解出7个完全图K3，得3×7＝21个完全图K3.

3 结 语

基于边矩阵的子矩阵分解的Steiner三连系的构造方法，适用于v≡1（mod t）的v阶Steiner三连系的构造.构造结果表明：v元集X上的每个元素恰好出现于r个区组中；X的每两个元素恰好出现于λ个区间组中.若按方案A构造Steiner三连系，Steiner三连系的个数NA决定于19阶Steiner三连系的个数N1＝9和完全三分图的三连系边矩阵的完全图K3的分解方案数N2＝2，故NA＝N1×N2＝14.若按方案B构造Steiner三连系，Steiner三连系的个数NB决定于3个7阶Steiner三连系的完全图K3的分解方案数＝7及完全二分图的6×6个完全图K3的分解方案数＝6，即有NB＝×＝42.Steiner三连系的总数可达N＝NA＋NB＝56个.

综上，文中的Steiner三连系的构造方法和计数方法是有效可行的，对Steiner三连系的构造方法和计数方法具有一定的参考价值和可推广性.

［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］ 陆家羲.可分解平衡不完全区组设计的存在性理论［J］.数学学报，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］.数学通报，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系若干课题研究的历史回顾——陆家羲学术工作背景概述［J］.数学进展，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］ 吴利生.关于S（2，3，υ）的大集和RBIB的存在性问题——我国组合数学工作者陆家羲同志的贡献［J］.数学研究与评论，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］张瑾，马良.基于加权绝对值距离Steiner最优树的选址问题［J］.数学的认识与实践，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］越民义，程丛电.关于Steiner问题的一个注记——连接五点之最小网络的一种寻优方案［J］.运筹学学报，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三连系构造的一种方法［J］.数学的实践与认识，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三连系及其构造方法［J］.安徽理工大学学报：自然科学版，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中的生成树的构造与计数［J］.沈阳师范大学学报：自然科学版，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三连系的构造与计数［J］.长春工业大学学报：自然科学版，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）