导读:本文包含了顶点覆盖论文开题报告文献综述、选题提纲参考文献及外文文献翻译，主要关键词:顶点,笛卡尔,算法,最小,乘积,近似,正则。
顶点覆盖论文文献综述
张雷,张安,陈永,陈光亭[1]（2019）在《叁正则图上的P_3顶点覆盖问题》一文中研究指出研究了叁正则图上的P_3顶点覆盖问题。P_3顶点覆盖问题是指删除原图中的若干顶点使得剩余子图中不存在长度大于等于3的路径,目标是删除点的个数尽可能少。通过分析贪婪算法解的结构,证明了算法的近似比为■,并给出了紧例。(本文来源于《杭州电子科技大学学报(自然科学版)》期刊2019年05期）
张文杰,涂建华[2]（2019）在《Series-Parallel图上最小权顶点覆盖3-路问题的有效算法》一文中研究指出研究了Series-Parallel图上的顶点覆盖3-路问题,利用动态规划思想,给出一个能在多项式时间内完成的有效算法,该算法的运行时间为O(|V|)。(本文来源于《北京化工大学学报(自然科学版)》期刊2019年01期）
申星[3]（2018）在《基于博弈的独立集和顶点覆盖问题研究》一文中研究指出复杂网络可以用于描述同一系统内不同个体之间、个体与整体之间以及不同整体之间的关系。复杂网络的最大独立集问题(MISP)和最小顶点覆盖问题(MVCP)是两个典型的集合优化问题,且都是NP-hard问题。最大独立集问题指的是求解一个(或若干个)网络节点构成的集合,使得所求得的集合规模最大、且集合内的节点相互之间没有连边。该优化问题得到整个网络中个体之间互不影响的最大的个体集合。最小顶点覆盖问题的目的在于找出给定复杂网络的规模最小的节点集合,并保证网络中任意一条边至少有一个顶点在所选的节点集合中。现实生活中的许多问题可以归结为这两种问题,比如高校教师排课系统、监控设备安置问题、线路规划问题、网络优化问题等。本文首先研究复杂网络的演化博弈动力学行为,然后创新性地结合网络的博弈规律,分别对局部搜索和全局搜索方法进行了研究、改进与实验,提出了基于囚徒困境博弈求解最大独立集问题的迭代局部搜索算法(IGLS)和基于雪堆博弈和遗传机制求解最小顶点覆盖问题的进化算法(GMA-MVC)。最后,通过实验,验证了本文所提出的IGLS算法和GMA-MVC算法的优势。本文的主要内容如下:1.研究复杂网络上的节点博弈行为,建立网络异步博弈方式下的纳什均衡状态与网络极大独立集、顶点覆盖集和最小顶点覆盖集之间的关系。在满足一定的约束条件下,网络进行同步雪堆博弈的严格纳什均衡状态等价于网络的顶点覆盖状态,但是同步博弈状态会陷入震荡,无法保证网络博弈行为一定可以收敛到纳什均衡,本文基于异步演化博弈,在保证一定收敛到纳什均衡状态的前提下,建立了网络异步演化博弈与最大独立集问题和最小顶点覆盖问题之间的关系,为解决这两个问题奠定了理论基础。2.基于囚徒困境博弈求解最大独立集问题的迭代局部搜索算法。基于复杂网络的博弈演化规律,创新地提出基于博弈的局部搜索机制(GLS),并与传统的迭代局部搜索算法框架相结合,提出IGLS算法。本文提出的GLS机制可以准确而快速地搜索到合法解并对该解集进行局部搜索,这种局部搜索操作可以同步实现弱扰动操作,同时,与其他局部搜索方法相比,GLS机制可以灵活地实现多种局部搜索方式,且操作过程简洁、易实现。本文提出的IGLS算法是基于GLS机制的迭代局部搜索算法,实验表明,IGLS算法在大多数网络上可以搜索到全局最优解,效果较好。3.基于雪堆博弈和遗传机制求解最小顶点覆盖问题的进化算法。本文借鉴经典的遗传算法框架,基于网络异步雪堆博弈与最小顶点覆盖问题之间的联系,将网络博弈的节点状态(被覆盖或未被覆盖)集合看作遗传操作的个体,不同个体代表不同的解集。遗传算法通过交叉、变异而使用全局信息搜索最优解,但是无法保证交叉、变异产生的新个体满足顶点覆盖问题的约束条件,新个体往往不是合法的顶点覆盖集。因此,本文提出基于雪堆博弈的个体修正方法,在种群更新的同时,每一个不是合法顶点覆盖集的个体都通过雪堆博弈机制维持自身的合法性并进行一定程度的局部搜索,实现了综合利用局部信息和全局信息目的。通过实验对比,GMA-MVC算法具有较好的性能。(本文来源于《西安电子科技大学》期刊2018-06-01）
张春露,殷志祥[4]（2018）在《图的最小顶点覆盖问题的链置换模型》一文中研究指出针对DNA计算解决最小顶点覆盖覆盖问题,采用对空解的数据池进行解的删除操作,找出解的补集,重而获得问题的最优解。在链置换的基础上,代替酶的作用,提高了实验的效率,节省时间,此算法独特新颖,简单可靠。(本文来源于《佳木斯大学学报(自然科学版)》期刊2018年02期）
李钊[5]（2018）在《一些乘积图和完全二部图的k路顶点覆盖》一文中研究指出图的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-03-01）
巩成艳,殷志祥,赵鑫月[6]（2017）在《基于自组装纳米颗粒探针的最小顶点覆盖问题的DNA计算模型》一文中研究指出DNA自组装技术为DNA计算的发展带来了一些新的启发。目前,解决各种NP完全问题的方法有多种多样的计算模型,其中有些是非常有用的,可以解决复杂的NP完全问题。在本文中,在自组装纳米颗粒探针的基础上,介绍了关于最小顶点覆盖问题的一种新的DNA计算模型。将给定问题的变量0或1所有可能的组合,编码在自组装纳米探针的识别区,通过靶序列的杂交来判断其可行解。相对于传统的DNA计算模型,该模型具有方便、灵敏、稳定性高的优点。(本文来源于《长春师范大学学报》期刊2017年12期）
占善华,谢小军[7]（2018）在《一种增量式约简方法求解最小顶点覆盖问题》一文中研究指出最小顶点覆盖问题是一个应用很广泛的NP难题,针对该问题给出一种增量式属性约简方法。首先将最小顶点覆盖问题转换为一个决策表的最小属性约简问题;利用增量式属性约简思想,随着图中边数的增多,提出一种更新最小顶点覆盖的增量式属性约简算法;该算法时间复杂度低于计算整个图的最小顶点覆盖的时间复杂度,同时针对大规模图问题,可随着边的增加动态更新最小顶点覆盖,因此降低了属性约简的方法求解最小顶点覆盖问题的运行时间。实验结果表明了该算法的可行性和有效性。(本文来源于《计算机应用研究》期刊2018年12期）
王利民,华景煜[8]（2017）在《顶点P_k覆盖问题的研究综述》一文中研究指出顶点覆盖问题是经典的NP完全问题,在排序、计算机网络等现实生活中有许多的应用.近几年来,许多研究者开始探究它的推广形式——顶点P_k覆盖(VCP_k)问题,即寻找一个顶点子集,从拓扑结构图中删除后使得剩下的顶点导出的子图不包含P_k路,其中P_k是指包含k个顶点的路.本文简单介绍了VCP_k问题的应用背景,归纳了它在近似算法、精确算法、参数化算法3个方面的主要研究进展,并分析了一些主要的方法和技巧.在此基础上,对VCP_k问题及其相关问题的研究前景进行了展望.(本文来源于《南京信息工程大学学报(自然科学版)》期刊2017年05期）
张弼弢[9]（2016）在《一些乘积图的k-路顶点覆盖》一文中研究指出图的k-路顶点理论在无线传感器网络和交通控制领域都有很重要的应用。近年来这一课题得到了国内外越来越多的学者广泛的研究。给定一个图G和一个正整数k,如果G中每一条顶点个数为k的路都至少包含S中的一个顶点,那么图G顶点集的子集S就叫做G的一个k-路顶点覆盖。k-路顶点覆盖的最小基数叫做图G的k路顶点覆盖数,记作ψk(G).本文主要包括四章:在第一章中,我们介绍了预备知识和图的k-路顶点覆盖及其相关研究背景和研究现状。第二章中,我们给出了ψk(Pm□Kn)和ψk(Pmokn)的一些界和某些特殊情况下的确切值。第叁章中,我们分别给出了ψk(Pm□Kn),ψk(SmoKn),ψk(Sm(?)Kn),ψk(Sm◇Kn),和ψk(Sm×Kn)的确切值。第四章中,我们给出了ψk(Pm□Pn)和ψk(Pm□Pn2)的一些下界。(本文来源于《天津师范大学》期刊2016-06-30）
郭洪敏[10]（2016）在《最小顶点覆盖问题的几种DNA算法研究》一文中研究指出传统的计算机由于其自身存储量和计算能力的有限,已经不能满足日益发展的科学形势。1994年,Adleman探索性的将现代生物技术与DNA操作技术结合起来,成功解决了具有七个节点的有向赋权图的哈密尔顿路径问题(Hamilton path problem),从此打开了生物计算的大门,让DNA分子作为一种新型的计算机硬件成为可能。而DNA分子由于具有传统计算机无法比拟的海量存储量和高度的计算并行性,使得其在密码学,数学,计算机等领域得到了广泛的青睐。本文将具体阐述DNA计算的研究背景、DNA分子结构、DNA分子操作过程等基本理论,并且对DNA分子操作过程中的初始编码问题进行了具体的分析,包括初始编码问题的基本概念,初始编码的约束条件和具体的编码方法；还将简单介绍一些常用的DNA计算模型(剪接模型、分子信标、质粒DNA模型以及DNA自组装模型等)的基本操作原理及优缺点。此外,本文将具体介绍最小顶点覆盖问题、可满足性问题、线性规划问题的基本概念,并巧妙的将复杂的最小顶点覆盖表转化为形式简便的0-1规划问题和可满足性问题,这也是本文的创新之处。并在此基础上,结合DNA自组装模型、质粒DNA模型,给出基本算法和具体生物操作过程,具有一定研究意义。(本文来源于《安徽理工大学》期刊2016-06-01）
顶点覆盖论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
研究了Series-Parallel图上的顶点覆盖3-路问题,利用动态规划思想,给出一个能在多项式时间内完成的有效算法,该算法的运行时间为O(|V|)。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
顶点覆盖论文参考文献
[1].张雷,张安,陈永,陈光亭.叁正则图上的P_3顶点覆盖问题[J].杭州电子科技大学学报(自然科学版).2019
[2].张文杰,涂建华.Series-Parallel图上最小权顶点覆盖3-路问题的有效算法[J].北京化工大学学报(自然科学版).2019
[3].申星.基于博弈的独立集和顶点覆盖问题研究[D].西安电子科技大学.2018
[4].张春露,殷志祥.图的最小顶点覆盖问题的链置换模型[J].佳木斯大学学报(自然科学版).2018
[5].李钊.一些乘积图和完全二部图的k路顶点覆盖[D].天津师范大学.2018
[6].巩成艳,殷志祥,赵鑫月.基于自组装纳米颗粒探针的最小顶点覆盖问题的DNA计算模型[J].长春师范大学学报.2017
[7].占善华,谢小军.一种增量式约简方法求解最小顶点覆盖问题[J].计算机应用研究.2018
[8].王利民,华景煜.顶点P_k覆盖问题的研究综述[J].南京信息工程大学学报(自然科学版).2017
[9].张弼弢.一些乘积图的k-路顶点覆盖[D].天津师范大学.2016
[10].郭洪敏.最小顶点覆盖问题的几种DNA算法研究[D].安徽理工大学.2016
论文知识图
![最小顶点覆盖[10]](http://image.cnki.net/GetImage.ashx?id=528430&suffix=.jpg)
