超图的奇圈横贯和偶边着色

来源 :新疆师范大学 | 被引量 : 0次 | 上传用户:bird2000521
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
近年来,超图理论得到迅速发展和完善。超图是有限集合的子集系统,是离散数学中最一般的结构,超图的着色理论在离散数学中起着非常重要的作用。众所周知,图中的树结构在计算机领域得到了广泛的应用。作为图的推广,超图中的圈很早就被研究,1965年Lovazs就证明了n个顶点p个连通分支边集为{Ei},i=1,2,…,m的无环超图H,若Ei≠Ej满足|Ei∩Ej|≤2且不包含3长以上圈,则(?)(|Ei|-2)<n-p。在无圈超图的基础上,后人将问题进一步演绎,着力研究无偶圈的超图和无奇圈的超图,Alcxandr Kostochka,Andras Gyarfas,Michael S.Jacobson,Andre E.Kezdy,Jeno Lehel等人在这方面做了许多工作,他们将一些图论中的结果推广到超图中,还将一些超图中的结果还原回图论得到了较好的结果,这样做更加明确了超图自身的研究意义和超图对图论的指导意义。本文所做的工作主要是将图论中的奇圈横贯和偶边着色的定义和定理向超图推广得到其更一般的形式,通过对超图中超圈的研究来发展和完善超图中超圈理论。整篇文章中,对超圈及其相关理论的研究分如下几个部分:第一部分:给出超图中超圈的定义及其相关的基本概念。第二部分:图G+K2对研究图的奇偶性起着非常重要的作用,本部分推广了此概念,给出了H+K2的定义。定理2.2.1得到超图H的两个顶点x和z之间有奇长链的充分条件,即定理2.2.1 H是连通简单超图满足,x和z是H中的两个顶点,若超图H+K2-{x’,z’}存在有完美匹配,则H中有一条x到z的奇长链。在定理2.2.2中对具有遗传2着色性质的超图H的奇圈横贯用H|K2进行了刻画,即定理2.2.2若n个顶点的超图H具有遗传2可着色性质,那么τ’(H)=n-α(H+H2)。而超图的独立数α有相当多的已知结论,这样简化了超图奇圈横贯的计算。在定理2.2.2的基础上,我们自然对那些图具有遗传2着色性质产生了兴趣,这也是2.3节主要研究的问题。定理2.3.1给出了k-一致超图H具有遗传2着色性质的充分条件,即定理2.3.1如果H是k一致超图,若q(H)的所有系数模k均不为0,则H具有遗传2着色性质。随后定理2.3.2证明了定理2.3.2 H是线性简单超图,若q(H)中有形式为xk,k∈{1,2,…,n}的单项式,那么H具有遗传2着色性质。本部分最后给出了ZH的定义,并得到了定理2.3.4 H是简单超图,若ZH是正规的,那么x(H)≤4。第三部分:图偶圈着色的概念来源于对平衡标号图的研究。本部分将图偶圈着色的定义推广到超图上,并且主要研究了超图最大偶边着色ε(H)。主要证明了定理3.2.1如果H是n个顶点连通的简单r-一致超图,那么εmax(H)≤(?)并且由此得到了推论3.2.1如果H是n个顶点k个连通分支的简单r-一致超图,那么εmax(H)≤(?)。。本部分的最后证明了定理3.2.3 H是n个顶点r-一致的连通超图。若H只包含一个圈,则εmax(H) (?)-1。在图中εmax(G)=n-1,定理3.2.1和定理3.2.3的结果在r=2时与图论中的结论相符,而且还推翻了一个很直观的猜想:n个顶点k个连通分支的r-超图H的最大偶边着色的是(?)。
其他文献
抑郁症作为当今世界的一大心理疾病正在越来越受到人们的普遍关注。高校大学生抑郁症的发病率日益增加,运动锻炼对心理健康的促进作用已经是有目共睹了。通过分析大量抑郁症
随着当前无线通信应用场景的多样化,无线通信在为人类社会发展带来了无限便利的同时,随之而来的信息安全威胁也日趋严重。现阶段主流无线网络安全机制延续了计算机网络的密码
<正>传统中国是个以家庭为本位的社会,而在家庭中一般以父母为纲,未成年子女毫无独立的地位可言。现代以来从西方引进的私法自治理念恰好吻合了这一传
胃癌的转移是一个复杂的、多步骤的生物学过程,涉及多个基因的调控作用,是患者死亡的主要原因,其具体的分子生物学机制目前还不十分清楚。随着新一代基因测序技术和生物信息
<正>随着经济社会的不断发展,人们经济实力的逐渐增加,大家不再把视野局限在个人的利益与需求上,慈善和公益事业近些年得到了广泛关注。同时,在这个互联网发达的时代,信息传
<正> 更年期综合征在中医称为“绝经前后诸证”,以植物神经机能失调及情志改变为其特征。是妇女将届断经时,机体内环境发生转折性生理变化,表现为脏腑、经脉、气血诸方面功能
<正>合理的房价变动趋势是怎样的?这是一个必须搞清楚的问题。它是我们进行房价调控的基础,也是未来确定调控方向、把握调控力度的客观依据。一、收入变动在趋势上决定房价走
藏木水电站1600 k N/320 k N坝顶双向门机轨道跨度15.5 m,全长180.67 m,该门机主要担负着左、右冲砂底孔事故闸门、冲砂廊道事故闸门、进水口检修闸门、进水口拦污栅的启闭和
旧城的街区重建,结合民居、街道、公共空间的保护发展,一直是城市规划的重要关键。香港的旧城(维多利亚城)经历百多年发展,传统的街景及公共空间亦经历更生,从中可以追寻一些