论文部分内容阅读
超图H是一个二元组(V,E),其中V是有限集,V中的元素称为顶点,E是V的有限非空子集族,E中的元素称为超边.在过去的四十多年里,图论已被广泛认为是解决几何、数论、运筹学和优化等领域中各种组合问题非常有用的工具.为了解决更多的组合问题,把图的概念推广到超图是非常自然的事情.本文将从组合设计的角度,用组合设计的方法来研究超图.本文主要是研究关于两种特殊类型的超图K(3)4-e和W(3)4的3-一致超图分解的问题.
设Γ是一些简单t-一致超图的集合.t-(ν,Γ,λ)填充(覆盖)是一个二元组(X,B),其中X是含ν个点的集合,B是顶点集定义在X的一些子集上的超图族,B中的每一个超图都同构于Γ中的某一个超图,称为是一个区组,并且X中的每个t-子集至多(至少)在λ个区组中出现.所有的t-(ν,Γ,λ)填充(覆盖)中,区组数能达到最大(最小)值的称为是t-(ν,Γ,λ)最大填充(最小覆盖),其区组数称为是填充(覆盖)数.
当t≥3时,对t-(ν,Γ,λ)最大填充和最小覆盖问题的研究目前还处于起步阶段,已有的结果并不多.本文研究t=3的情形.当t=3时,由于区组的特殊性,以及对Γ的选择的多样性,研究的难度比t=2时增加很多.我们对照t=2的做法,从研究最简单的超轮K(3)4-e和W(3)4入手,也就是研究关于这两种超图的填充和覆盖问题,为以后研究更为复杂的超图分解打下基础.
本文结构组织如下:
第1章简要介绍t-设计,图分解和超图分解的研究背景和现状以及它们之间的关系,并且给出本文的主要结果.
第2章通过引入一些辅助设计,给出了3-(ν,K(3)4-e,λ)填充的基本递推构造方法,并且描述了如何判断这样的一个填充是否为最大填充.利用这些递推构造,以及由计算机直接搜索得到的小阶数的设计,本文证明了对任意正整数ν≥4和λ,存在含有dλ(3,K(3)4-e,ν)个区组的MPλ(3,K(3)4-e,ν),它的边剩余中至多含有2条边.这里的填充数pλ(3,K(3)4-e,ν)=dλ(3,K(3)4-e,ν)=()λν(ν-1)(ν-2)/18」.
第3章研究的是Γ为W(3)4时的最大填充问题.研究的方法与第2章基本相似.只是这时,对边剩余中边数情况的讨论更加复杂,分的类也更多.根据超图W(3)4的特殊性,分析它与t=2的情形下的4长圈分解的关系,能够得到一些特殊的构造方法.通过这些构造,最终证明了填充数pλ(3,W(3)4,ν)理论上的上界也是能达到的.即:
在第4章和第5章研究的是Γ分别为K(3)4-e和W(3)4时的最小覆盖问题.仿照相应最大填充的研究方法来进行研究.通过分析当3-(ν,Γ,λ)覆盖在区组数能够达到下界的情况下其边超越中边数的情形,并把它与第2章和第3章中3-(ν,Γ,λ)最大填充的边剩余中的边数情况做比较,可以得到一些直接的结果.对剩下的情形,通过直接和递推构造来得到.最后可以证明覆盖数cλ(3,K(3)4-e,ν)=「λν(ν-1)(ν-2)/18().而覆盖数cλ(3,W(3)4,ν)也可以达到其理论上的下界.即: