论文部分内容阅读
本文主要研究连通图的割空间相关理论和相关的若干性质,这些内容在图论研究领域中占重要地位。但是,与连通图的圈空间相关理论相比,连通图的割空间相关理论的发展并不是很成熟,而且对其研究得也比较少。本文将应用连通图的割空间与圈空间相互正交的关系,解决部分割空间的问题。本文也尝试将圈空间部分现有的研究方法应用到割空间。本文第三章主要研究关于连通图的割中的问题,首先证明了割成为极小割的充要条件;然后,证明了极小割与极小割的对称差可以得到一个新的割;证明了最小割与最小割的集合并运算能得到一个最小割;最后,证明了,阶无向连通图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)也可以采用先求割数目进而得到圈数目的方法。