一些乘积图和完全二部图的k路顶点覆盖

发布时间：2020-04-29 15:35

【摘要】：图的k-路顶点覆盖理论在无线传感网络和交通控制领域都有很重要的应用。近几年来在国内外得到了广泛的研究。图的k-路顶点覆盖问题,也简称为k-VCP,找到一个最小的顶点子集F,使得在图G每一条长度为k的路中至少含有F中的一个顶点。k-路顶点覆盖的最小基数叫做图G的k-路顶点覆盖数,记做ψk(G)。实际上,我们用路的顶点数来表示次序,同时我们用长度来表示路的边数。由图G =(V(G),E(G))和图H=(V(H),E(H))构成的笛卡尔乘积图G□H的顶点集为V(G)× V(H),并且当u1 = u2且v1v2∈E(G)或u1u2 ∈E(G)且v1=v2时,顶点(u1,v1)和顶点(u2,v2)是相连的.由图G =(V(G),E(G))和图H=(V(H),E(H))构成的字典乘积图GoH的顶点集为V(G)×V(H),并且当 u1u2 ∈ E(G),或 u1 = u2 且v1v2∈E(H)时,顶点(u1,v1)和顶点(u2,v2)是相连的.由图G =(V(G),E(G))和图H =(V(H).E(H))构成的强乘积图G(?)H的顶点集为V(G)×V(H),并且当u1u2 ∈ E(G)且v1 = v2,或u1 = u2 且 v1v2 ∈ E(H),或u1u2 ∈ E(G)且巧v1v2 ∈E(H)时,顶点(u1,v1)和顶点(u2,v2)是相连的.本文主要研究了乘积图的k-路顶点覆盖问题.第一章首先简单介绍了预备知识和图的k路顶点覆盖的相关研究背景.第二章给出了 Pm□Cn的k路顶点覆盖数的上下界.根据引理1.1和1.2我们证明了 ψk(Wn+1)的精确值,并且在此结果的影响下得到了Pm和Wn+1之间各类乘积图的k路顶点覆盖数的估计值.第三章证明了Km,n的k路顶点覆盖数的确切的值.与此同时在Km,n的结果下,我们得到Km,n和P2的笛卡尔乘积图的k路顶点覆盖数的估计值第四章研究了笛卡尔乘积图Pm□Cn和强乘积图Pm(?)Cn的k路顶点覆盖的更加精确的上界,并且给出了ψk(Cm□Pn2)的下界.本文所得结论是全新的.可以通过构造k路顶点覆盖集的方式得以验证.每一章都给出了构造的相应k路顶点覆盖集.证明了所得结论的正确性及有效性.所得结果为更复杂图的k路顶点覆盖问题提供了一定的理论基础.
【学位授予单位】：天津师范大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O157.5

【相似文献】

相关期刊论文 前10条

1 支志兵;宁爱兵;胡琳琳;张惠珍;;3度图的最小顶点覆盖问题的多项式时间算法[J];数学理论与应用;2014年03期

2 吴春;朱国魂;谢玉忠;林宏;;一种求解平面图的最小顶点覆盖算法[J];计算机系统应用;2010年09期

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

4 王新辉;刘三阳;刘红卫;;顶点覆盖问题的强化半定规划松弛[J];西安电子科技大学学报;2005年06期

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

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

7 马金良;;顶点覆盖问题的一个算法[J];微电子学与计算机;1988年12期

8 郑光勇;李肯立;潘果;徐雨明;蒋伟进;焦铬;;化学反应优化算法求解最小顶点覆盖问题[J];小型微型计算机系统;2015年02期

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

10 张春露;殷志祥;;图的最小顶点覆盖问题的链置换模型[J];佳木斯大学学报(自然科学版);2018年02期

相关博士学位论文 前4条

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

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

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

4 吴帆;基于生化反应的典型约束可满足问题求解算法研究[D];湖南大学;2017年

相关硕士学位论文 前10条

1 李钊;一些乘积图和完全二部图的k路顶点覆盖[D];天津师范大学;2018年

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

3 方靓;泛化顶点覆盖问题的局部搜索算法研究[D];东北师范大学;2016年

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

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

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

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

8 周金凤;图的最小顶点覆盖问题的几种DNA计算模型[D];安徽理工大学;2013年

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

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

，

本文编号：2644734