Steiner三连系的构造与计数.docx

Steiner三连系的构造与计数.docxSteiner三连系的构造与计数
论文导读：的构造有t种选择。，从而形成v(v-1)/6 个三连系。｝…的构造的选择数，…，105个9阶Kirkman三连系的构造结果证实了9阶Kirkman三连系的计数方法。关键词：三连系，阶，构造，计数，存在 
1、基本思路
定义1设顶集V(G)=｛c 　　1 　　,c 　　2 　　,…c 　　v 　　｝,边集E(G)=｛c 　　1 　　c 　　2 　　,c 　　1 　　c 　　3 　　,…,c 　　1 　　c 　　v 　　,c 　　2 　　c 　　3 　　…,c 　　2 　　c 　　v 　　,…, c 　　v-1 　　c 　　v 　　｝，G为完全图K 　　v 　　 ，若将K 　　v 　　的|E(G)|=v(v-1)/2个边按自然顺序排成三角阵,使得任意边c 　　i 　　c 　　j 　　与顶点c 　　i 　　和顶点c 　　j 　　存在着关联关系，则所得三角阵称为边矩阵，并记为K 　　v 　　′。论文参考网。
定义2 设顶集V(G)=｛c 　　1 　　,c 　　2 　　,…c 　　v 　　｝，V(G)的3个子集V 　　i 　　=｛c 　　m 　　,c 　　m+1 　　,…,c 　　m+t-1 　　｝，V 　　j 　　=｛c 　　p 　　,c 　　p+1 　　,…,c 　　p+t-1 　　｝，V 　　k 　　=｛c 　　q 　　,c 　　q+1 　　,…,c 　　q+t-1 　　｝，若V 　　i 　　的每个顶与V 　　j 　　的t个顶和V 　　k 　　的t个顶相邻接，V 　　j 　　的每个顶与V 　　k 　　的t个顶相邻接，则图G称为完全三分图，记为K 　　 　　 　　, K 　　 　　 　　的3个子图称为完全二分图，分别记为K 　　 　　 　　，K 　　 　　 　　，K 　　 　　 　　并有K 　　 　　 　　=K 　　 　　 　　∪K 　　 　　 　　∪K 　　 　　 　　。
倘若存在于完全三分图K 　　 　　 　　中的t×t个完全图K 　　3 　　已被分离出，则所形成的t×t三连系矩阵K 　　 　　 　　可表述为：
K 　　 　　 　　= 　　 　　 　　易见，仅将V 　　i 　　, V 　　j 　　,V 　　k 　　 中顶点的最小序号m,p,q代入矩阵K 　　 　　 　　，即得 t×t个完全图K 　　3 　　。但K 　　 　　 　　不是唯一的，K 　　 　　 　　的构造有t种选择。
定理1 设顶集v(G)=｛c 　　1 　　,c 　　2 　　,…c 　　v 　　｝，|V(G)|=v=2t+1, t为已存在Steiner三连系的阶，则存在v=2t+1阶Steiner三连系，且v=2t+1阶Steiner三连系的构造等价于一个完全图K 　　v 　　的v(v-1)/6个完全图K 　　3 　　的分解。
证明：设K 　　v 　　′为v=2t+1阶完全图K 　　v 　　的边矩阵，则K 　　v 　　′的i行j列及对角线上的3(v-1)/2个边可并成(v-1)/2个完全图K 　　3 　　，K 　　v