图的割、割基相关理论研究

来源 :中央民族大学 | 被引量 : 0次 | 上传用户:xuruiqi8627361
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文主要研究连通图的割空间相关理论和相关的若干性质,这些内容在图论研究领域中占重要地位。但是,与连通图的圈空间相关理论相比,连通图的割空间相关理论的发展并不是很成熟,而且对其研究得也比较少。本文将应用连通图的割空间与圈空间相互正交的关系,解决部分割空间的问题。本文也尝试将圈空间部分现有的研究方法应用到割空间。本文第三章主要研究关于连通图的割中的问题,首先证明了割成为极小割的充要条件;然后,证明了极小割与极小割的对称差可以得到一个新的割;证明了最小割与最小割的集合并运算能得到一个最小割;最后,证明了,阶无向连通图G(V,E)中割的数目最多为2n-1-1个;n阶有向连通图G(V,E)中不同割的数目为2n-2。本文第四章证明了n阶连通图G(V,E)割空间中割基相关性质。首先证明了割基的非唯一性,具体内容是举出割空间中两个具体割基并给予证明;对比n阶连通图G(V,E)圈空间中的基本圈,相应的给出n阶连通图G(V,E)的割空间中基本割概念,并证明了割空间中一个割基可以由n-1个线性无关的基本割构成。其次,证明了割空间中最大割基的唯一性。对于这块内容考虑到一个最大割基可以反映出一个连通图的最大割信息,由此得到结论:许多的连通图中最大割的信息包含在最大割基中。根据前期得到的关于一个基变换的Hall型定理得到以下成果(1)给出了证明一个割基是最大割基的充要条件;(2)证明了最大割与最大割基的关系;(3)证明了两个最大割基保持权重一致。最后,本文给出了在无向连通图中最大割基的权重取值范围为在有向连通图中最大有向割的权重下界为最后,本文给出割的应用,主要思想是尝试先对平面图的对偶图中割的数目进行估计再反过来估计平面图中圈的数目,力争优化已有关于圈、最短圈数目的上限值。一方面,先考虑n阶无向连通图,首先证明了n阶无向连通图G(V,E)(平面图)中的圈与其连通对偶图G’(V’,E’)中的割一一对应。在此基础上得到一个推论:若n阶无向连通图G’(V’,E’)中割数目最多为2n-1-1个,那么它的连通对偶图G(V,E)中的圈数目也不超过2n-1-1个。其次,简述了几种比较简便并且高效求最小割的方法,其时间复杂度比目前求最短圈的时间复杂度低。另一方面,针对n阶有向连通图G(V,E),弓用了“TP”对偶图的定义,使得n阶有向连通图G(V,E)中的圈与其连通对偶图G’(V’,E’)中的割一一对应结论成立。这样,对于n阶有向连通图G(V,E)也可以采用先求割数目进而得到圈数目的方法。
其他文献
双孢蘑菇不仅味道鲜美,含有丰富的营养价值,还有一定的保健功效。具有抑制肿瘤的发展,降低血压,改善神经功能,降低血脂等作用。双孢蘑菇是全球栽培范围最广,种植规模最大,产量最高的食用菌,目前中国的双孢蘑菇产量和消费量逐年增加。由于双孢蘑菇采后呼吸作用旺盛,容易发生褐变现象,因此,常温下的货架期仅有1-3天,从而制约了双孢蘑菇的流通与销售。本文研究高浓度二氧化碳/氮气处理对双孢蘑菇采后生理及品质的影响,
本人研究生一年级进行量子光学与量子信息方面的理论学习,并深入研究了量子态的测量诱导的非局域性(Measurement-Induced Nonlocality,简称MIN)的相关内容。从研究生二年级开
本文主要研究三类微分方程边值问题正解的存在性。第一类是带有积分边界条件的三阶两点微分方程边值问题正解的存在性,文中运用Krasnosel-skii不动点定理得到边值问题存在一
格论是代数学的一个分支,它是在集合系统上定义逻辑运算,并研究它的拓扑性质的一门学科。19世纪英国数学家George Boole尝试对传统逻辑符号化,使之更为精确和便于运算,引入了
由于微分方程的定解问题与物理、化学、生物、工程、经济等其他领域的许多实际问题有着紧密的联系,微分方程解的存在性与多重性已成为微分方程与应用领域的重要课题之一.本文
气候变暖是近一个世纪以来全球最关注的环境问题之一。气候变暖等一系列气候问题给地球生态系统带来了巨大影响。它不仅影响生态系统的结构和功能,还影响生态系统服务。国内
本文以量子色动力学的NJL模型为基础,主要探讨了在有限重子数及同位旋化学势下可能的非轴矢流反常导致的夸克味道混合机制。我们发现同位旋矢量道和同位旋标量道的矢量相互作
豆科植物和根瘤菌建立共生关系,形成新的植物器官根瘤,为植物提供可利用的氮源。豆科植物和根瘤菌之间的相互作用包括根瘤菌的侵染,根瘤原基的形成和固氮根瘤的形成,都受到宿
本文运用Nehari流形及变分方法研究几类非局部椭圆型偏微分方程,分别讨论了它们解的存在性,多解性及变号解的存在性问题。在第一章中我们应用Nehari流形方法研究一类是有界区
非线性这门科学,在自然科学和社会科学当中,发挥着越来越重要的作用,所以,人们开始越来越关注此类问题。许多人发现大量的非线性问题的研究,都需要将其转化为非线性的演化方