3一致超图分解及相关问题

来源 :北京交通大学 | 被引量 : 2次 | 上传用户:chenjiechn
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
超图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,ν)也可以达到其理论上的下界.即:  
其他文献
请下载后查看,本文暂不支持在线获取查看简介。 Please download to view, this article does not support online access to view profile.
期刊
用有限群的极大子群和Sylow子群的极大子群来研究有限群的结构在有限群的研究中有非常重要的作用.很多学者都在这方面做了研究,得到了很多重要的结果。   本文中我们主要研
图的染色与色数问题是图论中的一个重要研究内容,也是图论中的一个十分活跃的领域,且有着深刻而丰富的理论结果和广泛的实际应用,其理论和方法在离散数学中占有重要地位.   1
本文主要研究了两个不同混沌连续系统和复杂动态网络混沌系统的广义同步存在性,并对广义同步流形进行了分类,给出了实现不同种类广义同步的充分条件。主要工作和成果如下: 
学位
请下载后查看,本文暂不支持在线获取查看简介。 Please download to view, this article does not support online access to view profile.
令K为正整数集合,g和v为正整数.一个Zgv上的(gv,g,K,λ)-差族(简记为Zgv上的(gv,g,K,λ)-DF),是指Zgv上的子集(称为基区组)作成的族F满足(1)若B∈F则∣B∣K,以及(2)Zgv{0,v,2v,...,(g-1)v}
兴趣是最好的老师.老师要根据教材的特点、学生的年龄心理特征以及生活实际,采用生动有趣、富有特色的教学方法,为学生创造一个良好的学习氛围,激发学生对学习数学产生强烈的
本文主要研究了Einstein场方程的严格解。Einstein场方程严格解的研究因其对广义相对论和宇宙学有着重要的意义而长期受到关注。迄今为止,该领域仍存在一些有待解决的基本而重
本文应用了模糊点与模糊子集之间的关系,首先,给出BCK-代数的(∈,∈)((∈,∈∨q),((-∈),(-∈)∨(-q)))-模糊蕴涵理想的定义,对其性质进行研究,得到了BCK-代数的模糊子集为BCK-代
斑茅(Saccharum arundinaceum Retz.)的生物产量高,对土壤条件要求低,可作为纤维素乙醇生产的原料作物在我国南方地区广泛种植。实验以斑茅为原料,采用液氨预处理法克服其水