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

发布时间：2017-08-03 20:31

  本文关键词：图的割、割基相关理论研究

  更多相关文章： 割空间 割 基本割 割基 最大割基

【摘要】：本文主要研究连通图的割空间相关理论和相关的若干性质,这些内容在图论研究领域中占重要地位。但是,与连通图的圈空间相关理论相比,连通图的割空间相关理论的发展并不是很成熟,而且对其研究得也比较少。本文将应用连通图的割空间与圈空间相互正交的关系,解决部分割空间的问题。本文也尝试将圈空间部分现有的研究方法应用到割空间。本文第三章主要研究关于连通图的割中的问题,首先证明了割成为极小割的充要条件；然后,证明了极小割与极小割的对称差可以得到一个新的割；证明了最小割与最小割的集合并运算能得到一个最小割；最后,证明了,阶无向连通图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)也可以采用先求割数目进而得到圈数目的方法。
【关键词】：割空间 割 基本割 割基 最大割基
【学位授予单位】：中央民族大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 摘要3-5
• 英文摘要5-10
• 第一章 引言10-13
• 第二章 预备知识13-16
• 第三章 连通图中割的若干性质16-22
• 第一节 割与极小割的关系16-20
• 第二节 割的计数问题20-22
• 第四章 割空间中割基的相关性质22-31
• 第一节 割基的非唯一性证明22-27
• 第二节 最大割基的唯一性证明27-31
• 第五章 割的应用31-36
• 第一节 应用割理论求解无向圈的计数问题31-34
• 第二节 应用割理论求解有向圈的计数问题34-36
• 第六章 总结展望36-37
• 参考文献37-40
• 致谢40-41
• 攻读学位期间发表的学术论文目录41

【相似文献】

中国期刊全文数据库 前10条

1 谢果;判定k-点连通图与k-边连通图极小性的定理[J];四川师范大学学报(自然科学版);2000年05期

2 余世群;一类极大临界h连通图的性质[J];湖北民族学院学报(自然科学版);2002年04期

3 齐登记,余世群;收缩临界6-连通图中的6度点[J];湖北民族学院学报(自然科学版);2002年04期

4 赵克文,曾克扬;哈密尔顿连通图的一点注记[J];工程数学学报;2003年02期

5 赵克文;哈密尔顿连通图与邻域并条件[J];信息工程大学学报;2003年02期

6 余世群;一类极大临界2连通图的结构[J];湖北民族学院学报(自然科学版);2004年04期

7 陈仪朝,苏健基;恰含5条非基本边的极小3连通图[J];广西师范大学学报(自然科学版);2004年03期

8 林福财;关于4连通图的容错直径和宽直径[J];漳州师范学院学报(自然科学版);2005年01期

9 余世群;;一类极大临界4连通图的结构[J];湖北民族学院学报(自然科学版);2006年02期

10 刘育兴;苏健基;;恰有k条非基本边的极小3连通图[J];数学研究与评论;2006年04期

中国重要会议论文全文数据库 前1条

1 张薇;张立辉;乞建勋;李星梅;苏志雄;;带正权的无向连通图中最短路问题研究[A];中国运筹学会第九届学术交流会论文集[C];2008年

中国博士学位论文全文数据库 前10条

1 罗朝阳;图的点度与距离型拓扑指标参数及其应用[D];山东大学;2015年

2 吴亚平;k-连通图中最长圈及余直径研究[D];华中师范大学;2011年

3 康海燕;连通图中可去边和圈的研究[D];山东大学;2010年

4 刘素娟;2-（边-）连通图的彩虹连通数[D];南开大学;2013年

5 陈晓东;无爪图及其扩展图的Hamilton性[D];大连理工大学;2012年

6 侯新民;网络（图）广义直径的研究[D];大连理工大学;2002年

7 蔡建生;图的因子和分数因子[D];山东大学;2007年

8 梁浩;图的拉普拉斯矩阵和临界群[D];中国科学技术大学;2009年

9 洪振木;某些网络可靠性和有效性研究[D];中国科学技术大学;2014年

10 Alaa Amer Najim;关于图的边添加和边减少问题研究[D];中国科学技术大学;2006年

中国硕士学位论文全文数据库 前10条

1 齐恩凤;k-连通图的可收缩边和可收缩圈[D];广西师范大学;2006年

2 余世群;一类极大临界h连通图的结构[D];广西师范大学;2003年

3 覃城阜;收缩临界5-连通图的性质[D];广西师范大学;2004年

4 杨迎球;k连通图中的k可收缩边[D];广西师范大学;2007年

5 张志芳;6连通图中的可收缩边[D];河南师范大学;2011年

6 毕振明;恰含6条非基本边的极小3连通图[D];山东大学;2012年

7 王雪;7-连通图最长圈上的可收缩边及3-连通图可收缩非边的分布[D];山东大学;2013年

8 刘秀松;几类图的全局强迫数和完全强迫数[D];兰州大学;2015年

9 吴敏如;图中过给定点集的圈结构[D];华中师范大学;2015年

10 常晓玲;4-连通图中最长圈上弦的存在性与可去边的关系[D];山东大学;2015年

，

本文编号：616216