【摘 要】
：
本文主要研究极大邻集搜索算法(Maximal Neighborhood Search,简记为MNS),重点考虑由这种算法在图上生成的序列和序列终点所满足的性质.论文首先分析了MNS算法与字典序广度优
论文部分内容阅读
本文主要研究极大邻集搜索算法(Maximal Neighborhood Search,简记为MNS),重点考虑由这种算法在图上生成的序列和序列终点所满足的性质.论文首先分析了MNS算法与字典序广度优先搜索(LexBFS)算法、最大势能搜索(MCS)算法以及字典序深度优先搜索(LexDFS)算法的相似性.我们用与LexBFS、MCS和LexDFS类似的方法,从弦图入手,发现MNS序列不一定是moplex删除序列,区别于已知的LexBFS、MCS和LexDFS序列都可以定义moplex删除序列.之后为了寻找图的极小分割集和极大团,考虑到MNS算法的特性,我们从指标搜索(label search)的角度入手,探索出当MNS序列中标号相邻的点的指标集满足一定条件后,我们便可以通过相邻两点中标号较晚的点的指标求得图的极小分割集,并通过相邻两点中标号较早的点和它的指标集导出图的极大团.文章中我们利用数学归纳法从不同角度证明了这种方法的正确性.同时,给出反例说明这种方法在非弦图上并不适用.最后,我们研究了MNS序列终点的性质,并证实了弦图中MNS序列终点一定属于某个molpex.然而在将结论推广到一般图上时发现非弦图上的MNS序列终点不满足这个性质.
其他文献
本文是一篇翻译实践报告,所译材料选自笔者作为天津大学东盟国家科技组织发展问题研究课题组成员编译的东盟国家科技组织英文官网资料。在共商、共建、共享理念下,东盟各国成为我国推进“一带一路”建设的重要伙伴,双方科技合作前景广阔,亟待加强。因此,对东盟各国科技组织发展现状进行调研,总结其组织架构、认证机制、治理模式并进行编译,可以有效促进双方开展科技交流与合作。本翻译实践报告共分为四部分。笔者首先概述翻译
丢番图逼近是数论研究中的一个重要分支,它起源于数的有理逼近。近年来丢番图逼近理论发展到流形上,形成了一个新的研究方向,丢番图逼近的测度理论或含参变量的丢番图逼近。
本文的内容主要分为两部分。第一部分研究内容是基于复杂网络中的最基础的两类模型；BA模型和LCD模型,它们是随机的按一定的规律和概率在每个时刻t加点加边后生成的一系列图的
G(n,p)模型表示顶点数为n,每两点之间以概率p相互独立连接的图所组成的概率空间.G(n,d)模型表示n个点,每个点的度均为d的图组成的概率空间.本文中,首先介绍了随机网络的基本
众所周知,时空滞后和非局部扩散现象在大自然界中是普遍存在的.近些年,有许多人多方面考虑了时空滞后和非局部扩散对方程的动力学行为所产生的影响,得到了一类既带有时空滞后
随着煤炭开采不断向着深部发展,巷道所受到的地应力大小逐渐增大,其围岩情况愈加复杂。许多岩层的岩性在浅埋深巷道中由于受到地应力较小,表现为坚硬或较坚硬性质,其完整性也较好。但在大埋深围岩应力条件下,这部分围岩表现为软弱岩层性质,并发生一定程度的破坏。在这样的情况下,单纯的根据传统的巷道支护计算理论进行计算得到的巷道支护方案会往往存在一定程度上的偏差,如过高的支护强度导致成本和工期的增加,过低的支护强
众所周知,Virasoro代数是结构和表示理论最简单却又极为重要的一类无限维李代数.由于它在李理论和理论物理上的重要应用,因此得到了许多数学家和物理学家的广泛关注.另一类较
通常称非线性抛物型方程为反应扩散方程,其扩散算子为经典的Laplace算子,然而,以卷积算子描述的非局部扩散算子也具有深刻的研究背景.行波解和整体解作为(非)局部扩散方程的
本文研究如下二阶积分差分方程的空间传播该模型对应的差分方程起源于描述滞后效应的种群动力学问题,理论上也来源于具有分段常数变量的泛函微分方程.该方程的显著特点是不能
数据同化方法是一种结合观测数据与状态转移模型来提高对系统状态预测的精确性的一种最优化方法,大致分为连续数据同化方法和顺序数据同化方法两大类。顺序数据同化方法也称