导读:本文包含了图同构问题论文开题报告文献综述及选题提纲参考文献，主要关键词:NP问题,哈密顿环,图同构,判定条件
图同构问题论文文献综述
侯爱民[1]（2013）在《哈密顿环与图同构问题的理论研究及算法设计》一文中研究指出哈密顿环问题和图同构问题是两类特殊的NP问题。到目前为止，这两个问题还不能设计出一个输入规模的多项式时间复杂度的算法。已经找到的算法，在最坏情况下，其时间复杂度是输入规模的指数阶或阶乘阶的函数。因此，除了继续寻找多项式时间复杂度的算法外，如何提高现有算法的时间效率，是解决这两个问题的一个有效途径。作为子图同构，哈密顿环问题在计算复杂性理论，作业调度，计算机布线，车辆路由，机器人路径控制，印刷电路板钻孔等领域具有广泛的应用价值。图同构问题在计算复杂性理论，模式识别，计算机视觉处理，信息检索，数据挖掘，VLSI设计验证，化学分子结构识别等领域具有广泛的应用价值。尤其在当今“大数据”时代，“大数据挖掘”是当下最迫切需要解决的实际问题。其中的图数据挖掘是大数据挖掘的核心发展方向之一，也是计算机学科相关研究中的当下热点。而图匹配（无论是原图匹配还是子图匹配）技术在图数据挖掘中占有核心地位。寻找新的判定条件和判定算法，提高已知算法的时间效率，一直是研究这两个问题的关键所在。本文正是从这两个方面着手开展研究。着重研究了新型的充分必要条件和必要条件，以及基于这些条件的判定算法。提出的这些条件不仅提供了设计新型算法的理论基础，指明了提高已知算法的时间效率的有效途径；而且在大多数场合下，是目前为止效率最好的。证明了这些算法的正确性，分析了这些算法的时间复杂度和空间复杂度，使用C语言编程实现了这些算法的仿真研究，以及和他人的算法的对比分析。主要工作包括：1.通过分析哈密顿环的合并规律，证明了基于单条公共边连通的基本圈合并法则的充分必要条件，推导了必要条件计算公式。与已知的仅有的闭包图充分必要条件不同，本文提出的充分必要条件可以处理所有的哈密顿图。本文提出的必要条件计算公式，既可以处理已知的仅有的连通分支数必要条件和Grinberg必要条件能处理的情况，也可以处理他们不能处理的情况，是目前为止效率最好的一个必要条件。此外，该必要条件计算公式，既可以处理平面图，也可以处理非平面图。当处理平面图时，Grinberg公式是本文公式的特殊形式。即本文公式是Grinberg公式的推广形式。2.哈密顿图的充分条件基本上都是涉及连通性和独立性，都是试图确保将图中的边尽量“分散”开，从而达到减少边数也能确保哈密顿环的存在。在其证明的过程中，都是直接寻找到一个哈密顿环。与这些条件采用的证明方法不同，Erds的充分条件使用边数的界函数，求出最大非哈密顿图的边数。这个边数揭示了非哈密顿图的数值特征。通过案例分析，发现了Erds条件的不足，研究了违反Chvátal充分条件的非哈密顿图的特征，寻找了新的“最大”非哈密顿图的边数的界函数。采用数学分析极值法，获得了非哈密顿图的一个边数最大值。这个边数最大值证明并修正了Erds充分条件，给出了更小的界。同时，也推导出n个顶点、最小度为k的最大非哈密顿图仅有两种类型。3.设计了基于充分必要条件的哈密顿环问题的判定算法，使用C语言编程实现了该算法的仿真研究，并和他人的算法进行了对比分析。由于染色体编码具有可拼接/可分解的特征，因此该算法在搜索哈密顿环的过程中，会自适应地调节搜索方向，朝着生成哈密顿环或最大长度环的方向前进。此外，由于充分必要条件有效地限定了找到可行解的搜索范围，从而避免了边选择的全排列组合的穷尽搜索，因此该算法是效率非常高的穷举型搜索算法，即使在最坏情况下也能获得良好的表现，不是输入规模的指数阶或阶乘阶的函数。通过算法分析，得到以下结论：空间复杂度为O(n×am×nsc_(max)~(k-1))，时间复杂度最坏为O(n×am×nsc_(max)~(k-1))。这里，am为初始种群大小，nsc_(max)为每次迭代中成功合并的基本圈的选择方案数的最大值，k为生成最大长度基本圈时成功合并基本圈的迭代次数。它们都与基本圈的数量和构造有关，取决于原始图形的拓扑结构。4.通过分析子图同构导致父图同构的规律，证明了基于子图同构判定父图同构的充分必要条件。设计了基于充分必要条件的图同构问题的判定算法，使用C语言编程实现了该算法的仿真研究，并和他人的算法进行了对比分析。同时也为他人提出来的已知的高效率的判定算法VF2提供了理论依据。通过算法分析，得到以下结论：空间复杂度为O(n~2)，时间复杂度为O(rm×n~3)。这里，rm=k∏(|cell_i|!)为潜在的一阶子图中能匹配i=1的行-行置换的个数。5.通过分析顶点邻接关系的异同分布规律，提出了基于顶点异或距离/同或距离的必要条件。对于非树的连通图，该必要条件是目前为止效率最好的一个必要条件，它具有更高的顶点集合划分的细分能力。对比分析了五个必要条件确定顶点集合划分的细分能力，探讨了进一步细分的方法，提出了基于必要条件的顶点划分细分算法的一般框架。使用C语言编程实现了该算法的仿真研究，并和他人的算法进行了对比分析。由于所有迭代步骤中获得的划分集合的单元要进行交集运算，不仅使得该算法具有顶点匹配关系的自适应配对特征，而且使得该算法运行在搜索空间的特殊点簇上，无须检查顶点匹配关系的全排列组合方案，从而极大地减小了搜索空间的范围。通过采用启发式剪枝技术，进一步有效地减小了搜索生成树的高度，从而保证该算法是效率非常高的穷举型搜索算法，即使在最坏情况下也能获得良好的表现，不是输入规模的指数阶或阶乘阶的函数。通过算法分析，得到以下结论：空间复杂度为O(r×n~2)，时间复杂度为O(r×n~3)。这里，r为迭代总次数。对于大多数情况，r=O(n~3)。对于最坏情况，r=O(n~h)，这里，h=1/2*log2~n。本文针对两类特殊的NP问题——哈密顿环问题和图同构问题，从判定条件、判定算法的时空复杂度的角度研究了解决这两个问题的新方法，对于判定这两个问题的程序代码的实现及算法性能的提高具有重要的现实意义和参考价值，为这两个问题的实际应用提供了高效率的解决技术。(本文来源于《华南理工大学》期刊2013-04-01）
南晋华,齐欢[2]（2010）在《图同构问题的决策神经网络模型》一文中研究指出图的同构问题是研究两个图之间相互关系范畴.这对图表面上似乎不同,但本质上完全相同.由于图的同构问题在以系统建模、电路布线等众多问题中有直接的应用,因而,吸引了不少的学者从事这方面的研究.该文意在建立一种局域连接的、模拟人脑决策思维模式的、可用于优化信息处理的神经网络模型.该文在过去建立求解图的同构问题人工神经网络模型的基础上,拟应用人脑决策局域化的思想,提出了一种新的用于图的同构问题的人工神经网络模型.该模型中增加了一个自然的约束条件,加快了运算速度.(本文来源于《计算机学报》期刊2010年02期）
图同构问题论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
图的同构问题是研究两个图之间相互关系范畴.这对图表面上似乎不同,但本质上完全相同.由于图的同构问题在以系统建模、电路布线等众多问题中有直接的应用,因而,吸引了不少的学者从事这方面的研究.该文意在建立一种局域连接的、模拟人脑决策思维模式的、可用于优化信息处理的神经网络模型.该文在过去建立求解图的同构问题人工神经网络模型的基础上,拟应用人脑决策局域化的思想,提出了一种新的用于图的同构问题的人工神经网络模型.该模型中增加了一个自然的约束条件,加快了运算速度.
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
图同构问题论文参考文献
[1].侯爱民.哈密顿环与图同构问题的理论研究及算法设计[D].华南理工大学.2013
[2].南晋华,齐欢.图同构问题的决策神经网络模型[J].计算机学报.2010