【摘 要】
：
图的分解是将一个图划分成一组边不相交的子图.图G的荫度是指G边分解所需e（H）的最少森林数.图G的分数荫度定义为γf（G）=maxH（?）G,v（H）1e（H）/v（H）-1.1986年,Payan最早介绍了这个概念.而著名的Nash-Williams定理提出并证明了一个图G可分解为至多k个森林的充分必要条件.1961年,Nash-Williams和Tutte独立证明了一个图G包含k个边不相交的支
论文部分内容阅读
图的分解是将一个图划分成一组边不相交的子图.图G的荫度是指G边分解所需e（H）的最少森林数.图G的分数荫度定义为γf（G）=maxH（?）G,v（H）1e（H）/v（H）-1.1986年,Payan最早介绍了这个概念.而著名的Nash-Williams定理提出并证明了一个图G可分解为至多k个森林的充分必要条件.1961年,Nash-Williams和Tutte独立证明了一个图G包含k个边不相交的支撑树的充分必要条件.2012年,Montassier等人关于一个图G的分数荫度提出了著名的九龙树猜想和强九龙树猜想.目前,九龙树猜想在2017年被蒋和杨解决.而强九龙树猜想只被证明出了一些特殊情况:2013年,Seog-Jin Kim等人证明了当k=1,d=2时的强九龙树猜想是正确的.这些结果都是对图的森林分解更深层次的研究.1993年,Chen等人提出了i-森林和i-树的概念.2019年,Fan等人提出了图G的i-荫度概念:γi（G）为覆盖图G的边所需i-森林的最小数.定义了vi（G）=（min|P|>i）（e（G/P））/（|P|i）,证明了 Nash-Williams 定理和 Tutte 定理是对偶关系,还证明了:一个点数为n且满足vi（G）=k+ε,0<ε≤1的图G包含k+1个边不相交的i-森林,其中k个是i-树,另一个是i-森林,其边数至少有ε（n-i）,且界是紧的等结果.图的森林覆盖推广到拟阵上,则为拟阵的独立集覆盖.1965年,Edmonds证明了拟阵M中的元素可以被分解为k个独立集合的充分必要条件.2019年,Fan等人证明了:令M是E上的拟阵,如果β（M）=maxφ≠X（?）E|X|/rM（X）=k+ε,k∈N≤ ε<1,那么E能分解成k+1个独立集,且其中一个独立集的元素个数最多为ε·r（M）.本文在i-森林和i-树的定义基础上,将k=1,d=2时的强九龙树猜想进行了推广.另外我们还考虑参数的非整数界来扩展Nash-Williams-Tutte定理.同时,以符号图上的提升图形拟阵（没有环）为代表,研究九龙树定理在符号图上的推广.本学位论文分为五个章节,如下所示:第一章,给出本文中所要用到的图论的基本概念,简述相关领域的研究现状,本文的主要结果.第二章我们讨论了当k=1,d=2时,在图的i-森林分解下的强九龙树猜想.即:当k=1,d=2时,假设图G满足τi（G）=maxH（?）G,|H|>ie（H）/|H|-i≤1+1/2,那么图G能边分解成2个i-森林,并且其中一个i-森林,它的每个连通分支最多包含2条边.第三章,我们证明了对于一个连通图G,k是任意的非负整数,d是满足1 ≤ d<|V（G）|的整数,若图G满足k+1 ≥ φ=min|P|>1e（G/P）/|P|-1>k+d-1/d,则图G包含k个支撑树和一个森林,且这个森林至少有一个连通分支的边数大于等于d.同时找出反例证明以上所给的界是紧的.第四章,我们研究提升图形拟阵的独立集覆盖问题,假设图G是只有一个非平衡圈的连通符号图,E是连通符号图G的边集,M是一个在E上的提升图形拟阵.如果β（M）=maxφ≠X（?）E|X|/rM（X）≤1+d/d+2,那么E能分解成两个独立集B1和I,且I在G中的导出图G[I]的最大度最多为d.除此之外,我们给出了关于以上结果的一个猜想,并叙述了证明这个猜想的思路以及证明过程中所遇到的问题.第五章,我们主要阐述了后续可研究的问题.
其他文献
海岸带作为海陆过渡地带,承载着全球60%人口[1],密集的人口和高强度的生产活动使得海岸带地区土地利用方式发生了巨大改变,沿海地区脆弱的生态环境也受到威胁。近30年来,人类的工业、农业和生活已经引起了土地利用方式和景观格局的剧烈变化[2]。随着我国沿海经济的日益发展,海岸带地区的人类活动与景观格局的耦合关系已经成为区域可持续发展和景观生态学研究的热点问题[3]。厘清人类活动与景观格局之间的响应关系
亚洲季风区人口密集,其社会经济发展受夏季风强度变化影响强烈。亚洲夏季风在以往间冰期的演化特征,能为深入了解当前间冰期（Marine Isotope Stage1,MIS1）及预测未来亚洲夏季风演化过程提供重要参考。本研究将从中国季风系统出发,基于已发表的中国间冰期石笋δ18O记录,对不同间冰期亚洲夏季风变化特征进行整体探讨,并综合学术界重要发现,得出以下结论:（1）对不同经纬度的中国石笋δ18O记
台风暴雨致灾指标直接关系到人们对于台风暴雨洪涝的灾情预估以及防灾减灾工作,相关研究具有重要意义。目前台风暴雨洪涝致灾指标研究对台风降水的分离关注很少,并且与高时空分辨率卫星数据配套的高精度致灾指标的优化不足,同时指标需要考虑暴雨致灾因子强度体现的降雨强度及暴雨持续时间方面,以及台风暴雨洪涝算法的结果验证计算。在以往相关研究中,降水量的空间分布格局多基于气象站点的降水数据,或再利用插值方法进行空间化
目前,钛硅分子筛已在工业上得到广泛应用,Ti-MWW分子筛是常见钛硅分子筛之一,因其具有独特的孔道结构和溶剂效应,在过氧化氢选择性氧化反应中表现出了优异的催化性能而受到广泛关注。因此,开展对Ti-MWW分子筛的合成及其催化性能方面的研究具有重要的意义。然而,现有方法合成的Ti-MWW分子筛中常会形成非骨架八面体Ti物种,在烯烃环氧化反应中会导致环氧烷烃开环,对催化性能产生不利影响,需要经过酸处理去
随着城市的发展,人口的持续增长,城市中高密度建筑集群的数量也越来越多,然而,由于缺乏足够的关注与思考,在迅速的城市化进程中,世界各地的高密度建筑集群趋向于同质化---相似的布局、相似的外观、相似的形式。在现有的规范和设计观念下,不同地区的城市高密度建筑集群并没有像传统地域建筑和聚落那样呈现出极高的环境适应性与文脉传承性。在可以预见的未来,我们的城市高密度建筑集群将如何传承传统文脉,应对地域性气候值
为满足强度和轻量化的要求,铝合金摩托车轮毂通常由钢制花键套与铝合金轮毂基体复合铸造而成。两种金属的热属性差异易导致接合处间隙过大,影响轮毂使用安全性。课题组开发了摩轮花键套接合质量检测装备,通过对花键轴施加周期性载荷,使瑕疵轮毂的双金属部件的配合间隙通过一定方式暴露出来,进而通过视觉识别出来。该装备基本满足了委托单位—今飞集团的铝合金摩托车轮毂检测指标要求,但人工上下料装配轮毂和花键轴的方法难以满
加积型红土作为中国南方典型的陆相沉积物,是揭示第四纪环境变迁的重要沉积载体。过去对于加积型红土的研究主要集中于年代学、地层学、地球化学以及物源领域,不同地区样品及不同代用指标均表明自中更新世以来加积型红土经受了中等至高等强度风化。然而对在此风化背景下的土壤学细节研究却甚少,网纹化机制尚不清晰。本文选取位于江西省九江市海会镇的L-HH剖面,在野外调查的基础上,对剖面进行了沉积层段划分,自下而上分为三
红细胞沉降是一种临床常用的监测多种炎症性疾病的疾病指标。目前已有部分测量红细胞沉降的标准方法,但这些传统方法仍然存在诸如无法实时监测沉降状态以及测试时间长等问题。针对上述问题,本论文提出了一种基于生物电阻抗谱（Electrical Impedance Spectroscope,EIS）的实时定量检测方法。在相同的条件下,通过对呈现两种形状的平行板电极容器（平行形状,T形）进行对比试验,证实了红细胞
随着我国经济的逐步上升,我国能源消耗的对外依存度也随着提高。以油气为例,每年的进口量占我国油气总消耗量的70%。当前,我国的能源消费方式还相对单一,清洁能源的利用率较低。此外,常规能源开发已进入后期,而非常规油气的开发将成为调整能源结构的有效手段。以页岩气为主的非常规天然气就成为世界上新的化石能源供应的主力军,而且我国页岩气的可采储量位居世界前列。但页岩气的高效开发还存在着很多基础性科学问题。页岩
圩区圩田系统是苏皖地区人地和谐相处的智慧结晶,人类聚居其中,沿水筑堤,圩堤顺水势线型生长,村屋沿堤集聚,在其历史进程中,自然而然形成了形态特殊的线型村落。这些村落受到圩堤、圩田的影响,线型发展、生长、演变,其本身具有一定的地域特殊性、生态脆弱性以及空间特殊性。现如今圩区系统水网破坏、洪涝灾害以及水体污染等问题开始显现;青壮人口流失,文化失落,标签化改造正逐步侵蚀着圩田圩区系统,千村一面的样板化改造