论文部分内容阅读
n为一正整数,S为n个不同元素的集合。基于S的n阶拉丁方是一个n行n列的阵列,阵列上的每个元素均为S的元素,使得S的n个元素在每一行每一列都是S中元素的一个排列。若此拉丁方矩阵为对称矩阵,则称此阵列为对称拉丁方。对两个拉丁方A与B,若存在Nθ,使得Nθ(A) = B,则称A与B同构。其中Nα(A)表示n阶拉丁方A经元素1,2,...,n作置换α后所得的拉丁方。设L = (lij)v×v,M = (mij)v×v是两个v阶拉丁方,若矩阵(lij,mij)v×v中的v2个元素偶(lij,mij)(0≤i,j≤v 1)都互不相同,则称L与M正交,或L与M是互相正交的拉丁方。拉丁方与正交拉丁方理论研究是组合数学的重要组成部分,有着丰富的研究成果。与正交拉丁方的研究相对应的是比正交条件弱的各种概念及问题的研究。1782年,在构造一对6阶正交拉丁方失败后,L.欧拉构造了一对不完全拉丁方,它们产生出34个不同的有序元素偶和两个空位置,后来这种拉丁方被称为欧拉型的不完全欧拉方。此后,各种比正交弱的概念被陆续提出和研究。两个v阶拉丁方,L = (lij)和M = (mij)被称作是r-正交拉丁方,如果把他们重叠起来可以得到恰好r个不同的有序元素偶,即|{(lij,mij) : 0≤i,j≤v ? 1}| = r。若在一对v阶r-正交拉丁方L和M中,M是L的转置,则称L是r-自正交拉丁方,并记L为r ?SOLS(v)。本文主要研究对称拉丁方的有关性质与非同构计数,在此基础上进一步研究了偶阶对称拉丁方的快速构造和不完全正交拉丁方的构造问题。在第一章中,介绍了对称拉丁方和r-正交拉丁方问题的背景和研究发展过程。以及对称拉丁方和不完全正交拉丁方的概念及其已有的结果。并且研究了对称拉丁方的若干性质。在第二章中,给出了拉丁方同构的概念,利用奇阶与偶阶对称拉丁方的性质,将n阶对称拉丁方进行同构分类和非同构计数。并编写了实现这种算法的程序,标准对称拉丁方的生成采用了回溯法生成技巧。使得n阶标准对称拉丁方的搜索在实现时大大加速,并得出了8阶对称拉丁方的10936320类同构类代表元。在第三章中,利用图论的有关知识,给出了偶阶对称拉丁方构造的六种具体方法。在第四章中,运用递归构造的方法构造不完全的r-自正交拉丁方,给出了三种带有特定有序元素偶集合(即DOP集)的v - SOLS(v)。