s×t阶Steiner三连系的一种构造方法

霍玉洪， 侴万禧， 李晓毅

（1.淮南师范学院数学与计算科学系，安徽淮南 232038；2.安徽理工大学土木建筑学院，安徽淮南 232001；3.沈阳师范大学数学与系统科学学院，辽宁沈阳 110034）

0 引 言

区组设计理论是组合数学的一个重要分支，它在试验设计、竞赛安排及数字通讯等许多领域中均有重要的作用。早在1850年，Kirkman［1］提出了一个有趣的“15名女生”的问题，并于同年做出解答。1971年，D R Ray-Chaudhuri与R M Wilson［2－4］共同发表论文“Kirkman女生问题的解”，以阐明6n＋3阶Kirkman三连系的构造。百余年来，就是否对每个n＝0，1，2，3，…，总是存在6n＋3阶Kirkman三连系，一直是个难题。1971年，中国数学家陆家羲提出了BIBD设计可分解的充要条件［5］。

1 基本思路

设G（V，E）为一个完全图Kv，若完全图Kv的阶数V满足v＝3t－2，t为已存Steiner三连系的阶数，则v阶Steiner三连系的构造等价于一个完全图Kv的v（v－1）／6个完全图K3的分解。但是，当完全图Kv的阶数较高时，则无法将完全图Kv直接分解出v（v－1）／6个完全图K3。倘若将完全图Kv先分解出3个t阶完全图及 1个完全三分图，则3个t阶完全图中的3×t（t－1）／6个完全图K3及1个完全三分图中的（t－1）×（t－1）个完全图K3构成v＝3t－2阶Steiner三连系中的v（v－1）／6个完全图K3，而将完全图Kv分解出3个t阶完全图和1个完全三分图的有力工具是完全图Kv的边矩阵。

定义1［5］设G（V，E）为一个完全图Kv，若将完全图Kv中的v（v－1）／2个边按自然顺序排成上三角阵，使得任意边ViVj分别与顶Vi和顶Vj相关联，则所得到的上三角阵就称为完全图Kv的边矩阵，并记为。

2 s×t阶Steiner三连系的构造［6］

设v阶Steiner三连系的阶数v＝s×t，s，t为已存的Steiner三连系的阶数，则s×t阶Steiner三连系的构造方案有两种：方案A和方案B。

按照方案A构造3×t阶Steiner三连系的步骤如下：

步骤1：将完全图Kv中的v（v－1）／2个边排成边矩阵。

按照方案B构造s×t阶Steiner三连系的步骤如下：

步骤1：将完全图Kv中的v（v－1）／2个边排成边矩阵。

步骤2：将完全图Kv的边矩阵划分为t个s阶完全图的边矩阵，i＝1，2，3，…，t，以及t（t－1）／2个完全二分图的边矩阵，i，j＝1，2，…，t。

3 21阶Steiner三连系［7－8］

3.1 方案A

按方案A构造21阶Steiner三连系的具体步骤如下：

步骤1：将完全图K21中的v（v－1）／2个边排列成边矩阵。

3.2 方案B

按方案B构造21阶Steiner三连系的具体步骤如下：

步骤1：将完全图K21的v（v－1）／2个边排列成边矩阵。

从而得另一个21阶Steiner三连系ST13（21）。

4 21阶Steiner三连系的计数

5 结 语

1）给出了用于图论研究的一个工具——完全图的边矩阵，借助于它可将任意s×t阶完全图K3分解为v（v－1）／6个完全图K3；

2）提出了s×t阶Steiner三连系构造的一种方法；

3）解决了s×t阶Steiner三连系的计数问题。

［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］ 杨骅飞，王朝瑞.组合数学及其应用［M］.北京：北京理工大学出版社，1992.

［6］ 侴万禧.r×t阶Kirkman三连系构造的一种方法［J］.数学的实践与认识，2004，34（9）：144-145.

［7］ 侴万禧.高阶Steiner三连系及其构造方法［J］.安徽理工大学学报：自然科学版，2004，24（3）：76-80.

［8］ 侴万禧，黄云峰.20面体平图的4着色与对偶树的分解［J］.长春工业大学学报：自然科学版，2008，29（6）：623-627.