资源描述：
《哈密顿图的判定与应用【文献综述】》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、毕业设计文献综述信息与计算科学哈密顿图的判定与应用图论(graphictheory)是一门既古老又年轻的学科.它诞生于18世纪上半叶.到19世纪下半叶这个领域才发展成为数学的一个系统的分支,直到20世纪上半叶,这门学科才有自己的著作出现.自20世纪下半叶开始,随着计算机科学与技术的发展,图的理论研究和应用研究才得到迅速广泛的重视,图论作为一个数学的分支,才真正确立了自己的地位.哈密顿(爱尔兰科学家)在1859年提出一个名叫“周游世界”游戏问题是:能否遍历正12面体的每个顶点一次且一次后回到原地.由此引申出哈密顿图的定义:如果图上有一条经过图所用
2、顶点一次且仅一次的回路,则称此回路为哈密顿回路,具有哈密顿回路的图称为哈密顿图.哈密顿图具有六个领域:哈密顿圈,H连通,泛圈,点泛圈,边泛圈,泛连通.哈密顿图是有哈密顿圈的图.至今没有一个像欧拉图的充要条件那样的“非平凡的”(不是定义的同义反复)关于哈密顿图、哈密顿通路的充分必要条件,但关于他们的充分性和必要性分别有一些研究成果.而哈密顿图不光在金字塔图、扇面蜂巢图及马图上有体现它性质的研究,且在四正则连环图和彼得森中有它独特的应用.而且哈密顿图在哈密顿通路、哈密顿轨、多哈密顿轨问题上也有很多细致的研究和应用.1984年时在连续10年排名加拿大
3、第一大学的范更华教授得到名垂青史的“范定理”:2连通阶图的距离是2的任意两点均有,则是有圈,当时是哈密顿图.当然,关于如此著名的范定理,各国不少专家也对范定理企求做出改进发展.1987年Wojda院士和欧洲最古老的著名大学之一的法国奥大的运筹学科创建奠基人Benhocine教授2人合作仅局部推广上面范定理.又如法国Benhocine教授1977年发表在法国科学院学报的哈密顿图论文就一直有国际影响,但他至今仅有25篇数学论文且18篇是哈密顿图的,他是排名哈密顿图研究前30名大师之一.哈密顿图已经历了一个多世纪的跋涉,容易攀登的时代已经过去了,其进
4、展已非常不容易,如此即使是世界级的大师泰斗,不论你多么聪明利害都好,面对的下一个问题猜想都永远是相关学科的全世界的专家经过多年仍不能解决的,就是想做点进展都非常不容易,每一篇论文都是超越最权威大师的成果.哈密顿图的难如两个权威说“非常不容易”.但它却具有重大历史意义以及广泛而重要的应用价值.现国际数学联盟主席是哈密顿图权威,并且琼州大学赵克文和美国权威等合作改进耶鲁大学Ore院士等大师权威的代表性结果已在“哈密顿图”居世界领先.在国内,宁宣熙和宁安琪提出了哈密顿圈自组织算法的实证研究结果和其在哈密顿图判定上的应用,介绍了SOA算法在大约1200
5、0个规模不同()的一般任意图中构造哈密顿圈的实证研究结果,验证了SOA算法的可靠性和时间的多项式性.在此基础上论证了SOA算法用于判断一般任意图是否为哈密顿图的可行性,并用一些实例进行了实证研究.在阻塞流理论的研究中,利用网络最小阻塞流与哈密顿轨之间的关系建立了哈密顿轨问题的无环最小支撑流模型.通过这个模型可以把一步内构造无环最小支撑流这一数学难题分解成分别在多项式时间内完成的两个阶段,从而为解决这一数学难题找到了新的思路,开发研制了在一般任意图中构造哈密顿圈的自组织算法(或SOA算法).在文献,全面详细地介绍了作者经过10多年潜心研究这一算法
6、的理论及进行12000余例实证研究的结果.到目前为止尚未遇到反例.由于不少学者根据NPC理论认定这是绝对不可能的,因此作者只好通过大量的实证研究来显示这一多项式算法存在的可能性.况且,作者进行这项研究的目的并不是为了解决计算复杂性理论中NP是否等于P的问题,而是为学术研究和工程应用提供一种在一般图中构造哈密顿圈的实用有效工具.即便有人能找到反例,说明SOA算法只不过是像线性规划单纯形算法那样,是一个实用的好算法,应当说这也是一个很幸运的结果.因为有了它,不但可以在用相关定理(如范定理或者其它更新的定理)判定存在哈密顿圈的一般图中构造出至少一条具
7、体的哈密顿圈,也可以对超出这些定理范围之外的一般图进行是否是哈密顿图的判定,这岂不也是一项有实用价值的成果.如果这些研究结果还能对数学家们在解决哈密顿图判定的理论研究上有所启迪和帮助,那么这项研究就更有意义了.回溯法是一种按照深度优先的策略从根结点开始搜索解空间树的算法,该算法可以用来求出问题的全部解,也可以在求出问题的一个解之后停止对问题的求解,即只求该问题是否有解.哈密顿通路就是判断图中是否存在一条通过所有顶点一次且仅一次的路径.宁夏大学数学计算机学院的刘向娇博士在他的《用回溯法求哈密顿通路》论文中论述了用回溯法来求解一个任意的图中是否存在
8、一条哈密顿通路的问题,并用具体的算法来实现它.算法搜索至解空间树的任一结点时,总是先判断该结点是否肯定不包含问题的解.如果肯定不包含,则跳过对以该结点
