|
1. 引言 Kirkman女生问题[1]: 这是组合数学中一个经典问题. 说的是一个班有15名女生, 每天排队出来散步. 15人分成5组, 每组由3名女生组成. 要求在7天里每一个女生和其他女生相伴恰好一次. 每组中的3名女生组成一个三元组, 由三元组组成的集合叫做三元系. 显然这个三元系中应该有个三元组, 而由简单计算可知满足条件的三元系若存在, 则刚好含有个三元组. 问题是: 这样的三元系存在吗? 内容来自www.paper51.com 设1,2,3,4,5,6,7,8,9,10,11,12,13,14,15分别代表15个女生. 此问题的一个解为: paper51.com {1,2,3},{4,8,12},{5,10,15},{6,11,13},{7,9,14}； 内容来自www.paper51.com {1,4,5},{2,8,10},{3,13,14},{6,9,15},{7,11,12}； 内容来自www.paper51.com
{1,6,7},{2,9,11},{3,12,15},{4,10,14},{5,8,13}； http://www.paper51.com {1,8,9},{2,12,14},{3,5,6},{4,11,15},{7,10,13}； 内容来自www.paper51.com {1,10,11},{2,13,15},{3,4,7},{5,9,12},{6,8,14}； 内容来自www.paper51.com {1,12,13},{2,4,6},{3,9,10},{5,11,14},{7,8,15}； copyright paper51.com {1,14,15},{2,5,7},{3,8,11},{4,9,13},{6,10,12}. paper51.com 这个解是怎样找到的呢？本论文将在下面介绍其构造方法, 它是一种特殊的Steiner三元系. copyright paper51.com 在认识什么是Steiner三元系之前, 我们先介绍一下Steiner. 他的全名是Jakob Steiner, 德国数学家, 德国近代综合几何学的开创者. 1796年3月18日生于瑞士伯尔尼州的乌岑斯多夫, 1863年4月1日卒于伯尔尼. 内容来自论文无忧网 www.paper51.com 下面我们先介绍几个定义和定理. paper51.com
定义1[2]: 设是一个非空集, 是上的若干三元子集组成的集合.若满足：对任意的的二元子集, 存在唯一的三元子集, 使得, 则称为一个Steiner三元系, 或称为集合上的一个Steiner三元系. 称为此三元系的阶. copyright paper51.com 定理1[2]: 如果是有限集上的Steiner三元系, 则 内容来自www.paper51.com (a) (b) 内容来自论文无忧网 www.paper51.com
由定理1知, 不是所有的有限非空集合上都存在Steiner三元系. 上都存在Steiner三元系的必要条件是 . Skolen和 Bose分别给出了满足和的Steiner三元系的构造方法, 因此这个条件也是充分的, 即: 内容来自www.paper51.com 定理2: 有限集上存在Steiner三元系的充要条件为. copyright paper51.com 定义2[1]: 设是一个Steiner三元系, . 若存在的一个划分使得每一个是的一个划分,则称此三元系为Kirkman三元系. copyright paper51.com Steiner三元系与两类代数结构密切相关. 为介绍这种关系, 我们先回顾抽象代数中的一些概念. 内容来自www.paper51.com 定义3[3]: 设是一个非空集. 到的映射称为上的一个二元运算. 若“”是上的一个二元运算. 则称二元组为一个群胚(groupoid), 或简称为一个群胚. 内容来自论文无忧网 www.paper51.com 定义4[3]: 若群胚满足对于的任意两个元来说, 方程和都在里有唯一解, 则称此群胚为拟群 (quasigroup). copyright paper51.com 定义5[3]: 含有单位元(幺元)的拟群叫做幺拟群, 或叫做圈 (loop). paper51.com 定义6[3]: 设是一个非空集, “”是上的一个二元运算. 若满足以下三个恒等式: paper51.com
(SQ1) ; paper51.com (SQ2) ; 内容来自www.paper51.com (SQ3) . paper51.com 则称为一个Steiner拟群. copyright paper51.com 注: 设是一个Steiner拟群. 则对于任意的, 存在使得, 此外, 若, 则, 所以方程在中存在唯一解. 由交换律方程也存在唯一解, 因此Steiner拟群确实满足拟群的定义. http://www.paper51.com 定理3[3]: 设是一个Steiner三元系. 在上定义二元运算“”如下： http://www.paper51.com
paper51.com 则是一个Steiner拟群. paper51.com 反之, 若是一个Steiner拟群,令 copyright paper51.com . 内容来自论文无忧网 www.paper51.com 则是一个Steiner三元系. http://www.paper51.com
定义7[3]: 设是一个非空集, “”是上的一个二元运算, 是此运算的单位元, 若满足以下三个恒等式： 内容来自论文无忧网 www.paper51.com
(SL1) ; http://www.paper51.com (SL2) ; 内容来自www.paper51.com (SL3) . http://www.paper51.com 则称为一个Steiner圈, 或简称为Steiner圈. http://www.paper51.com 注：同理Steiner圈确实满足圈的定义. paper51.com
定理4[3]: 若是一个Steiner三元系, , 在上定义二元运算“”如下: http://www.paper51.com
; paper51.com . 内容来自论文无忧网 www.paper51.com 则是一个Steiner圈且. http://www.paper51.com
反之, 若是一个Steiner圈, 且, 令 paper51.com . copyright paper51.com 则是一个Steiner三元系. copyright paper51.com
|