图的森林分解和伪森林分解的推广研究

来源 :福州大学 | 被引量 : 0次 | 上传用户:lzl2008000
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图的分解是将一个图分解成一组边不相交的子图,它是图论这门学科的一个重要研究方向,并且有着极为广泛的应用.Nash-Williams于1964年提出并证明了一个图可分解为至多k个森林的充分必要条件,称之为Nash-Williams定理.Tutte和Nash-Williams独立证明了 一个图含有k个边不交支撑树的充分必要条件.Montassier等人在2012年提出了著名的九龙树猜想,此猜想于2015年被蒋和杨解决,它是对图的森林分解更深层次的研究.1965年,Hakimi等人提出了伪森林的概念,并对图的伪森林分解做了研究.本文主要对森林,树以及伪森林这几个概念进行了推广,分别称它们为i-森林,i-树和j-伪森林.另外,我们还定义了j-伪树(这里i是正整数,j是非负整数).在这些定义的基础上,我们推广了前人的结论并得出了一些新的结果.本文结构如下:第一章,我们先介绍了本文所涉及到的基本符号和前人的成果,然后定义了一些新的概念,标号,并列举了我们的研究成果,第二章,我们证明了几个引理,这几个引理是后续证明的有力工具.第三章,我们证明了一个图能分解成k个i-森林的充分必要条件,以及一个图包含k个树的充分必要条件(一个图G包含k个i-树的充分必要条件为φ_i(G)≥ k,其中φ_i(G)是关于图G的一个参数),并证明了这两个定理是等价的.当φ_i(G)=k + ε时,我们讨论了分数部分ε所代表的含义.第四章,我们证明了一个图能分解成k个j-伪森林的充分必要条件,以及一个图包含k个j-伪树的充分必要条件(一个图G包含k个j-伪树的充要条件为φ_j~*(G)≥k,其中φ_j~*(G)是关于图G的一个参数),并证明了这两个定理是等价的.当γ_j~*(G)=k + ε时,我们讨论了分数部分ε所代表的含义。第五章,我们对九龙树定理做了推广,讨论了图的i-森林分解下的九龙树定理。第六章,我们给出了前文中一些定理的其它证明方法,同时也对某些定理进行了改进。
其他文献
配变台区作为电网连接用户的基本供电单位,其安全可靠地运行对电网的供电可靠性有着至关重要的影响。随着我国对智能配电网建设要求的不断深化,配变台区的智能化水平也决定了整个配电网的智能化水平。在已有的研究中,学者主要以台区重过载、台区负荷情况等方面对配变台区的运行状态进行态势预测,缺乏针对配变台区低压跳闸故障的预测研究。随着大数据信息技术与人工智能技术在电力行业的逐步应用,其在电网运行、设备状态监测、客
在语文教学活动中阅读教学是重要的组成部分,在阅读课堂上,不仅要注重学生对于文本的创造性解读,而且要强调学生的阅读体验,能够结合自己的实际经验,更加深入的理解作品,丰富精神世界。然而在实际的教学过程中,由于应试教育的影响和教学模式的固化,降低了课堂的教学效率,导致学生的学习积极性不高。教师难教和学生厌学的现象依然普遍存在,阅读教学要求和教学现状之间依然存在着不可忽视的矛盾。如何打破目前的这种困境,平
民以食为天,食以安为先。粮食安全怎样确保,首先需要一定数量的耕地作为保障。有史以来,耕地就是人类生存的基本资源和基础条件。众所周知,我国人口众多、人均耕地资源贫乏,随着改革开放的不断深入、经济社会的不断发展、城镇化建设水平的不断提高,人地之间的矛盾进一步凸显,深入加强耕地保护工作已经刻不容缓。作为国家经济调控政策的重要组成部分,税收是国家调控经济发展模式、取得财政收入的重要手段。相对与国家其他公共
锚杆锚固技术由于施工简便、成本低等优点,被广泛应用于隧道、矿井、山体加固等多个建筑工程领域。锚杆支护性能的好坏与否对于被支护工程的安全性和可靠性来说至关重要,因此
帕金森病是一种慢性退行的运动障碍,症状主要表现为震颤、僵硬、运动缓慢、姿势不稳等。帕金森病不能完全治愈,病情的发展会降低患者的生活质量。帕金森病患者的受众群体通常为老年人,去医院诊断行动不便,且目前的诊断成本较高。因此,基于语音障碍的远程诊断受到了学者的广泛关注。本文以语音数据集为分析对象,研究帕金森病的远程诊断问题。数据来源于Sakar等(Appl.Soft.Comput.,2018,74(1)
中国经济发展迅猛,如今我国已成为世界第二大经济体。在经济快速发展的背后,我国金融体制的不完善也显露出来,特别是在资本市场中,股价暴跌带来的影响十分恶劣,不仅会损害投资者财富,积压负面情绪,危害金融市场的发展,而且可能会给实体经济带来灾难。税收征管是我国的重要法律制度,可以提高企业的治理水平,然而是否可以将治理作用延伸至资本市场正是本文研究的主要内容。本文从税收征管的角度出发,以宏观的视角考察了股价
心肌梗死(MI)后导致心肌细胞的大量死亡,伴随着心肌微环境发生变化,进而电信号传导受阻导致纤维化瘢痕的形成,心肌组织严重缺血。三个密不可分的因素致使心肌梗死在临床上采取
随着信息科技领域“互联网+”概念的提出,Web应用系统迎来最好发展时机,Web应用系统需要和异质技术架构和平台的系统或者功能库进行数据交互难题日益凸显。为实现跨平台数据
β-碳选择性消除反应可以发生在环状或无环体系中,实现开环或扩环,断裂或加成,并且在有些反应过程中形成的金属有机中间体可以作为后续反应的活性前体,从而构建许多有意义的
煤炭行业是国民经济的支柱产业之一,在国民经济发展中占据重要地位。煤炭生产中存在着各种各样的职业有害因素,它们在一定条件下,可对作业者的身心健康以及安全造成不良影响,