论文部分内容阅读
给定正整数t，v，k和λ，设X为一个v元集，B是由X的某些k元子集（称为区组）所组成的子集族.若X的任意一个t元子集都至多包含在B的λ个区组中，则称（X，B）为一个t-(v，k，λ)填充设计.令Dλ(v，k，t)表示t-(v，k，λ)填充设计最大可能的区组个数，Dλ(v，k，t)叫做填充数.若（X，B）是区组数为Dλ(v，k，t)的-（v，k，λ）填充设计，则叫做最优t-（v，k，λ）填充设计.当λ=1时，把D1(v，k，t)简写为D(v，k，t). 一个混合超图就是一个三元集合H=（X，C，D），其中X是顶点集（有限集），C和D是X的两个子集族.集合C和集合D中的元素分别称为混合超图H的C-超边和D-超边.特殊地，当C=D时，H叫做双边超图;当D=(0)时，H叫做C-超图;当C=(0)时，H叫做D-超图，此时就是一般超图.所以超图是混合超图的特殊情况.混合超图H的一个严格k-染色是指恰好用k种颜色对其顶点集进行染色，并且满足每条C-超边至少有两个点染同色，同时每一条D-超边至少有两个点染不同色.显然，对于混合超图来说，最大染色数和最小染色数都有重要意义.混合超图H的可严格k-染色的最大（最小）的数k叫做H的上色数（下色数）. 混合超图的染色问题是在1992年首次提出的，该理论是国际上比较新的一个课题，有很多的问题等待我们去解决.这个问题后来被推广到了设计中，例如把Steiner三元系和四元系看做超图，研究其染色问题. 本文把混合超图和上色数等概念应用到最优2-(v，3，1)填充设计中，把最优2-(v，3，1)填充设计的点集作为混合超图的顶点集，区组同时作为C-超边和D-超边得到双边超图，来研究一些小阶数的最优2-(v，3，1)填充设计的上色数，并在此基础上，通过两种递推构造法得出了一些更大阶数的最优2-(v，3，1)填充设计上色数的界.