s×t階Steiner三連系的一種構(gòu)造方法

霍玉洪， 侴萬(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）

0 引 言

區(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］。

1 基本思路

設(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的邊矩陣，并記為。

2 s×t階Steiner三連系的構(gòu)造［6］

設(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。

3 21階Steiner三連系［7－8］

3.1 方案A

按方案A構(gòu)造21階Steiner三連系的具體步驟如下：

步驟1：將完全圖K21中的v（v－1）／2個(gè)邊排列成邊矩陣。

3.2 方案B

按方案B構(gòu)造21階Steiner三連系的具體步驟如下：

步驟1：將完全圖K21的v（v－1）／2個(gè)邊排列成邊矩陣。

從而得另一個(gè)21階Steiner三連系ST13（21）。

4 21階Steiner三連系的計(jì)數(shù)

5 結(jié) 語(yǔ)

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.