分数因子临界图及其相关性质的研究

来源 :山东师范大学 | 被引量 : 0次 | 上传用户:hualing_xue
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文所考虑的图都是简单无向图.设G=(V(G),E(G))是一个图,其中V(G)和E(G)分别表示G的顶点集合和边集合.顶点x在G中的度记为dG(x),δ(G)表示G中所有顶点度的最小值.对于任意的集合S(¢)V(G),由S导出的G的子图记为G[S],G-S表示由V(G)\S导出的子图.用o(G-S)和i(G-S)分别代表G-S中奇分支的个数和孤立顶点的个数. 设g(x)≤f(x)是定义在V(G)上的两个非负整数值函数,H是G的一个支撑子图.如果对于任意的x∈V(G),满足g(x)≤dH(x)≤f(x),则称H是G的一个(g,f)-因子.类似的,如果对于任意的x∈V(G),满足g(x)=f(x),则称日是G的一个f-因子(或g-因子);如果对于任意的x∈V(G),有g(x)=a,f(x)=6且a,b是两个正整数,那么(g,f)-因子就可被称为[a,b]-因子.特别的,对于任意的x∈V(G),有g(x)=f(x)=1时,(g,f)-因子就变成了1-因子,即完美匹配. 设g(x)≤(x)是定义在V(G)上的两个非负整数值函数,h(e)∈[0,1]是-个定义在E(G)上的函数并且dhG(x)=∑e∈Exh(e),其中Ex={xy:xy∈E(G)}.此时dhG(x)被称为是在h作用下的G中顶点x的分数度,h被称为是一个指示函数(inditor fullction).如果对于任意的x∈V(G),有g(x)≤dhG(x)≤f(x),设Eh={e:e∈E(G),h(e)≠0}且Gh是G的一个支撑子图并使得E(Gh)=Eh,那么Gh就是G的一个分数-(g,f)-因子.同样的方法可以类似的定义分数-k-因子、分数-[a,b]-因子等.特别的,对于任意的x∈V(G),有g(x)=f(x)=1时,分数-(g,f)-因子变为分数-1-因子,即分数完美匹配. 图的因子理论是图论中研究的主要问题之一.对因子理论的研究在一个多世纪以前就开始了,但直到上世纪七十年代才逐渐地活跃了起来.到目前为止,对图的因子方面的研究已经得到了不少成果.分数图论是相对年轻的分支,因此仍有许多问题有待解决. 本文共分为六大部分,第四部分和第五部分是整个文章的核心,通过分析证明得出了分数因子临界图和分数-(r,k)-可扩图的一些结论. 第一部分是全文的基础部分.简要介绍了文中所涉及的概念、术语和符号,回顾了图论及图因子问题的发展史,并对图因子问题中常用的重要参数作了详细介绍. 第二部分概括总结了图因子存在性问题中整数因子和分数因子已有的重要定理. 第三部分分析概括出图因子存在性问题中的两种常用研究方法. 第四部分重点研究了分数因子临界图(设G是一个图,若对于顶点集合V(G)的任意n-子集T使得G-T有分数-r-因子,则称G是-个分数-(r,n)-因子-临界图)的一些性质,得出了以下结论: 设G是δ(G)≥r+n的图且孤立韧度I(G)≥r+n-1/r.则G是一个分数-(r,n)-因子-临界图. 假设G是δ(G)≥r+n的图.若G是分数-(r,n)-因子-临界图,则G也是分数-(r,n-1)-因子-临界图. 如果对于任意的u∈V(G),G-{u}-有分数-r-因子,那么G同样也有分数-r-因子.第五部分主要研究了分数-(r,k)-可扩图(设G是一个图,如果对于V(G)的任意r-子集T,G-T是一个分数-k-可扩图,则G是一个分数-(r,k)-可扩图)的一些性质,得出了以下结论: 图G是一个分数-(r,k)-可扩图当且仅当对于任意的集合U∈V(G),有i(G-U)≤U-2K-r.其中,|U|≥2k+r且G[U]包含一个k-匹配. 任意—个分数-(r,k)-可扩图同时也是—个分数一(r1,k1,)-可扩图,其中0≤r1≤r,0≤k1≤k. 设G是—个图.则G是—个分数-(r,k).可扩图当且仅当对于G任意的一个i-匹配M(0≤i≤k),G-V(M)是一个分数-(r,k-i)-可扩图. 一个分数-(r,k)-可扩图是分数-(k+r/2)-可扩的. 第六部分是对全文的一个总结以及对下一步工作的展望.
其他文献
期刊
鲁西南石炭二叠纪煤系形成于内陆表海盆地。潮坪沉积体系是研究区聚煤时期重要的沉积体系之一。作者详细研究了潮坪沉积体系的内部构成、成因相及各种沉积体发育特点,分析了沉
全球制造和经济一体化促使了企业间竞争的不断加剧,并逐渐由同行业单个企业间的竞争演变为由一系列上下游合作伙伴企业构成的供应链之间的竞争。众所周知,库存管理在企业经营
期刊
期刊
期刊
期刊
1999年2月26日这一天,春意盎然。全区农村农业先进工作者表彰会上,自治区党委书记毛如柏将一块金光闪闪、镌刻着“亿元村”的牌匾授给中卫县东园村党支部书记杨建国。会场掌
在当前,国外对于总承包模式的应用和研究已经达到了一定的广度和深度,采用工程总承包模式可以使业主从繁琐的项目管理工作中脱离出来,能有效的提高工程质量、加快工程进度、减少
期刊