点赋权二部图上最大边装填问题和最小顶点覆盖问题的相关性及其算法研究

发布时间：2017-11-25 06:11

  本文关键词：点赋权二部图上最大边装填问题和最小顶点覆盖问题的相关性及其算法研究

  更多相关文章： 匹配 顶点覆盖 难 边装填 计算复杂性 整数规划

【摘要】：给定一个无向图,一个边的子集称为匹配,如果里面的任意两条边都没有共同的交点；一个顶点的子集称为顶点覆盖,如果图中每一条边的两个端点中的至少一个在该顶点子集内。经典的最大匹配问题要求图中包含边数最多的匹配,而经典的顶点覆盖问题要求图中包含顶点数最少的顶点覆盖。匹配与顶点覆盖问题是组合最优化研究的中心问题。在计算复杂性方面,匹配可认为是类问题的典型代表,顶点覆盖问题可认为是难问题的典型代表。对匹配与顶点覆盖问题的持续和深入研究推动了学科的发展,丰富了算法理论和技巧,揭示了深刻的数学关系。Kǒnig(1931)找到了让这两个问题相互联系的图论结构：二部图。经典的Kǒnig定理断言：在二部图中,最大的匹配包含的边数等于最小的顶点覆盖包含的顶点数。20世纪以来离散数学的发展见证了Kǒnig定理的深刻性。很多推动学科发展的著名定理都和Kǒnig定理等价,它们包括：代数学中的P. Hall定理,偏序集上的Dilworth定理,图论中的Menger定理,网络流的最大流最小割定理等等。本文研究点赋权二部图上的边装填与顶点覆盖问题,关注它们的关系及其算法研究。给定一个无向图,每个顶点上有一个正整数权重,一个边的子集(边允许重复)称为一个边装填,如果图中每个顶点与中的边相关联的数目不超过该点的权重；一个顶点的子集称为顶点覆盖,如果图中每一条边都与相交。最大边装填问题要求图中包含边数最多的边装填,而最小顶点覆盖问题要求图中顶点权重之和最小的顶点覆盖。这两个问题推广了经典的最大匹配与最小顶点覆盖问题,有重要的理论意义和广阔的应用前景。本文分析了这两个问题的计算复杂性,用整数规划理论证明了这两个问题的最优值在二部图结构下相等,并提供了多项式时间算法求解任意二部图上的这两个问题的最优解。我们的结果推广了Kǒnig定理,并为相关的装填与覆盖问题提供了有益的参考。
【学位授予单位】：昆明理工大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5

【相似文献】

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

1 祝丹梅,孙艳蕊;最小顶点覆盖问题的一个近似算法[J];辽宁师专学报(自然科学版);2004年03期

2 陈文彬;;逼近4正则图的最小顶点覆盖问题的难解性(英文)[J];广州大学学报(自然科学版);2014年01期

3 金珍;万龙;;具有完美匹配的图的顶点覆盖问题[J];浙江大学学报(理学版);2013年05期

4 王莲花;杨建雅;王继顺;;最大顶点覆盖问题的一种近似算法[J];数学的实践与认识;2007年19期

5 贾兴德;图之极小顶点覆盖[J];曲阜师范大学学报(自然科学版);1995年02期

6 张惠玲;谢邱敏;李炜;;最少顶点覆盖问题的研究[J];中国新通信;2014年13期

7 杜俊峰;涂建华;;奖励收集顶点覆盖问题的一个2-近似算法[J];北京化工大学学报(自然科学版);2014年02期

8 聂晓艳;耿俊;汤建钢;;图的最小顶点覆盖的粘贴DNA计算模型[J];首都师范大学学报(自然科学版);2013年01期

9 王淑栋,刘文斌,许进;图的最小顶点覆盖问题的质粒DNA计算模型[J];华中科技大学学报(自然科学版);2004年11期

10 ;[J];;年期

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

1 曲惠琴;DNA计算若干问题研究[D];复旦大学;2005年

2 董亚非;若干DNA计算粘贴模型的研究[D];华中科技大学;2004年

3 刘湘辉;IP网络带宽测量的模型与算法的研究[D];国防科学技术大学;2005年

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

1 郭洪敏;最小顶点覆盖问题的几种DNA算法研究[D];安徽理工大学;2016年

2 段侠;点赋权二部图上最大边装填问题和最小顶点覆盖问题的相关性及其算法研究[D];昆明理工大学;2016年

3 何峰;二分图顶点覆盖问题的求解及应用[D];昆明理工大学;2002年

4 庄涛;s-路径顶点覆盖问题的算法研究[D];山东大学;2012年

5 蔡晟;顶点覆盖问题的确定参数可解算法研究[D];复旦大学;2008年

6 张召刚;树上的最大顶点覆盖的算法设计和分析[D];浙江大学;2007年

7 杜俊峰;顶点覆盖推广问题的算法设计与图不变量的研究[D];北京化工大学;2015年

8 彭震宇;最大独立集和最小弱顶点覆盖问题求解及其应用研究[D];江南大学;2008年

9 李玉超;顶点覆盖k-路问题的研究和富勒烯图的参数计算[D];北京化工大学;2014年

10 沈树梅;FPT-算法在CBVC问题中的运用[D];昆明理工大学;2005年

，

本文编号：1225037