顶点覆盖推广问题的算法设计与图不变量的研究

发布时间：2017-11-14 00:29

  本文关键词：顶点覆盖推广问题的算法设计与图不变量的研究

  更多相关文章： 近似算法 迭代松弛方法 部分顶点覆盖问题 奖励收集顶点问题 图不变量 度阻尼距离 单圈图 双圈图 仙人掌图

【摘要】：考虑一个顶点赋权图,定义图中每个顶点子集的权重为其包含的顶点总权重,同时,如果存在某个顶点子集,满足图中每条边均至少有一个端点属于该顶点子集,则称其为顶点覆盖集。顶点覆盖问题是指在给定的图G中寻找一个权重最小的顶点覆盖集。该问题作为图论经典问题,受到了研究者的广泛关注。本文主要研究内容之一是顶点覆盖问题的两个推广问题——部分顶点覆盖问题与奖励收集顶点覆盖问题。如果要求顶点子集只需覆盖图中至少k条边,则顶点覆盖问题就转化为部分顶点覆盖问题,显然有当k取到图的边数时,部分顶点覆盖问题将退化为顶点覆盖问题。类似地,如果给每条边赋予惩罚费用,对于图中的顶点子集,定义一种特殊的权重,为其包含的顶点总权重加上未被其覆盖的边的总费用,目标为寻找一个权重最小的顶点子集,则称为奖励收集顶点覆盖问题,显然有惩罚费用均远大于顶点权值时,奖励收集顶点覆盖问题将退化为顶点覆盖问题。本文采用迭代松弛方法依次设计了部分顶点覆盖问题的一个近似度为2+q/~(OPT)的近似算法,其中Q表示有限的最大的顶点权值,OPT表示该问题的最优解的值,一个近似度为2的近似算法,以及奖励收集顶点问题的一个2-近似算法。图不变量,指图(或图的一部分)到实数集的一个映射,并且其在同构图中取值相同。其中,基于顶点间距离的一系列图不变量在理论化学领域得到了广泛的研究和应用。本文着重研究了度阻尼距离,其由Gutman等在2012年首次提出,其定义为其中dG(u)表示顶点u的度,RG(u,v)表示顶点u,v之间的阻尼距离。我们研究并刻画了具有最大度阻尼距离的单圈图和双圈图,以及具有最小度阻尼距离的仙人掌图。
【学位授予单位】：北京化工大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：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年

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

1 储燕;WSN中基于帆布协议的覆盖问题与路由算法研究[D];苏州大学;2015年

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

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

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

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

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

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

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

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

，

本文编号：1183104