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.