资源描述：
《Steiner三连系的构造与计数》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、Steiner三连系的构造与计数科技信息'0高校讲台oSCIENCE&TECHNOLOGYINFORMATION2007年第21期Steiner三连系的构造与计数雷小磊翕万禧(安徽理工大学土木工程系安徽淮南232001)摘要:提出了2t+1阶Steiner三连系的构造方法和计数方法,阐述了完全三分图及完全二分图在组合设计中的应用.证明了关于2t+l阶Steiner三连系存在和构造方面的定理.介绍了7x20个19阶Steiner三连系构造的全过程.关健词:三连系;阶;构造;计数;存在TheconstructionandenumerationofSteinert
2、riplesystemsoforder2t+1Leixiao-leiChouWan-xi?(DeptofCivilEngineering.AnhuiUniversityofScienceandTechnology,HuainanAnhui232001?China)Abstract:ThedefinitionsofbothconstructingandenumeratingSteinertripleoforder2t+1areproposed.eapplicationgraphsinBIBDconstructionisdescribed.Theexistenceand
3、constructiontheoremofSteinertriplesystemsoforder2t+lisproved.140Steinertriplesystemsoforder19andtheirentireconstructionprocedurearepresented.Keywords:Triplesystems;order;construction;enumeration;existence1.基本思路定义1:设顶集V(G)={Cl,c2,…c},边集E(G)={C1Cc1C3,…,C1Ccac3…,cac一?,Cv-lC},G为完全图K,若将K的IE
4、(G)I=v(v一1)/2个边按自然顺序排成三角阵,使得任意边cc与顶点C.和顶点Cj存在着关联关系,则所得三角阵称为边矩阵,并记为K.定义2:设顶集v(G】={ci,c…cv},V(G)的3个子集V={Cm,C+1'…,c},Vj={c一,c一1},Vk={cq'q+1,…,c-1},若Vi的每个顶与的t个顶和v的t个顶相邻接,V.的每个顶与Vk的t个顶相邻接,则图G称为完全三分图,记为K:====k,KLu0d,k)的3个子图称为完全二分图,分别记为,,并有=uu.倘若存在于完全三分图中的txt个完全图K3已被分离出,则所形成的txt三连系矩阵l(::可表述为:
5、:{m,p,q){m,p+l,q~1)…{m,p+t一1,q+t一1){m+l,p+l,q){m+l,p+2,q+1)…{m+l,p,q+卜1);ii{m+t一1,p+t-l,q){m+卜1,p,q+1)…{m+卜1,p+t一2,q+t一1)易见,仅将V,Vj,V中顶点的最小序号m,P,q代人矩阵K:===『,即得txt个完全图.但:不是唯一的,K的构造有t种选择.定理1:设顶集v(G)={Cl,C…C},IV(.G)I=v=2t+l,t为已存在Steiner三连系的阶,则存在v=2t+l阶Steiner三连系,且v=2t+l阶Steiner三连系的构造等价于一个完
6、全图K的v(v一1)/6个完全图K3的分解.证明:设K为v=2t+l阶完全图K的边矩阵,则K的i行j列及对角线上的3(v一1)/2个边可并成v一1)/2个完全图K3,K的i行j列及对角线以外区域可划分出t(1—1)/6个各由3个完全二分图K2.,K22,K20,k的2x2三连系矩阵K:,从而形成vv一1),6个三连系.定理1得证.'命题1:设顶集v(G)={Cl,C?cv},IV(G)I=v=2t+l,t为已存在Steiner三连系的阶,G为完全图K,K为完全图K的边矩阵,则Kv的t(t—ly2个2x2子矩阵的划分方案有P一,p2,…,p什1等v+1种,其中方案P表
7、示:K的i行j列及对角线所占为A区,A区以外的B区域划分为t"一1)/2个2x2子矩阵.证明:设t=3,v=2t+l=7,则的t(t一1)/2=3个2x2子矩阵划分方案数为v+l=8,即有P,P2,…,P等8种方案,经过子矩阵划分后,边矩阵分别为"",",…,".命题1得证.K,()=ABBBBAABBBBBBBBABBBBAc1c2c5c6c2c3c4c5c6c7fAABBBBAAAAABBBBABBBBAC1C2C3c
8、C5C6KT'()=K1()=AABBBBABBBBAABBAAABBAc2c3c4c5c6c7fABBBBABBBBAABBABBAAAA
