购买

¥20.0

加入VIP
  • 专属下载券
  • 上传内容扩展
  • 资料优先审核
  • 免费资料无限下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 哈密尔顿图的判定及应用学士学位毕业论文

哈密尔顿图的判定及应用学士学位毕业论文.doc

哈密尔顿图的判定及应用学士学位毕业论文

不系舟红枫
2019-01-24 0人阅读 举报 0 0 0 暂无简介

简介:本文档为《哈密尔顿图的判定及应用学士学位毕业论文doc》,可适用于高等教育领域

本科毕业设计(论文)哈密尔顿图的判定及应用JudgementandapplicationofHamiltongraph毕业设计(论文)原创性声明和使用授权说明原创性声明本人郑重承诺:所呈交的毕业设计(论文)是我个人在指导教师的指导下进行的研究工作及取得的成果。尽我所知除文中特别加以标注和致谢的地方外不包含其他人或组织已经发表或公布过的研究成果也不包含我为获得及其它教育机构的学位或学历而使用过的材料。对本研究提供过帮助和做出过贡献的个人或集体均已在文中作了明确的说明并表示了谢意。作者签名:     日 期:     ​​​​​​​​​​​​指导教师签名:     日  期:     使用授权说明本人完全了解大学关于收集、保存、使用毕业设计(论文)的规定即:按照学校要求提交毕业设计(论文)的印刷本和电子版本学校有权保存毕业设计(论文)的印刷本和电子版并提供目录检索与阅览服务学校可以采用影印、缩印、数字化或其它复制手段保存论文在不以赢利为目的前提下学校可以公布论文的部分或全部内容。作者签名:     日 期:     ​​​​​​​​​​​​学位论文原创性声明本人郑重声明:所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名:日期:年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定同意学校保留并向国家有关部门或机构送交论文的复印件和电子版允许论文被查阅和借阅。本人授权    大学可以将本学位论文的全部或部分内容编入有关数据库进行检索可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。涉密论文按学校规定处理。作者签名:日期:年月日导师签名:日期:年月日注意事项设计(论文)的内容包括:)封面(按教务处制定的标准封面格式制作))原创性声明)中文摘要(字左右)、关键词)外文摘要、关键词)目次页(附件不统一编入))论文主体部分:引言(或绪论)、正文、结论)参考文献)致谢)附录(对论文支持必要时)论文字数要求:理工类设计(论文)正文字数不少于万字(不包括图纸、程序清单等)文科类论文正文字数不少于万字。附件包括:任务书、开题报告、外文译文、译文原文(复印件)。文字、图表要求:)文字通顺语言流畅书写字迹工整打印字体及大小符合要求无错别字不准请他人代写)工程设计类题目的图纸要求部分用尺规绘制部分用计算机绘制所有图纸应符合国家技术标准规范。图表整洁布局合理文字注释必须使用工程字书写不准用徒手画)毕业论文须用A单面打印论文页以上的双面打印)图表应绘制于无格子的页面上)软件工程类课题应有程序清单并提供电子文档装订顺序)设计(论文))附件:按照任务书、开题报告、外文译文、译文原文(复印件)次序装订指导教师评阅书指导教师评价:一、撰写(设计)过程、学生在论文(设计)过程中的治学态度、工作精神□优□良□中□及格□不及格、学生掌握专业知识、技能的扎实程度□优□良□中□及格□不及格、学生综合运用所学知识和专业技能分析和解决问题的能力□优□良□中□及格□不及格、研究方法的科学性技术线路的可行性设计方案的合理性□优□良□中□及格□不及格、完成毕业论文(设计)期间的出勤情况□优□良□中□及格□不及格二、论文(设计)质量、论文(设计)的整体结构是否符合撰写规范?□优□良□中□及格□不及格、是否完成指定的论文(设计)任务(包括装订及附件)?□优□良□中□及格□不及格三、论文(设计)水平、论文(设计)的理论意义或对解决实际问题的指导意义□优□良□中□及格□不及格、论文的观念是否有新意?设计是否有创意?□优□良□中□及格□不及格、论文(设计说明书)所体现的整体水平□优□良□中□及格□不及格建议成绩:□优□良□中□及格□不及格(在所选等级前的□内画“√”)指导教师:(签名)单位:(盖章)年月日评阅教师评阅书评阅教师评价:一、论文(设计)质量、论文(设计)的整体结构是否符合撰写规范?□优□良□中□及格□不及格、是否完成指定的论文(设计)任务(包括装订及附件)?□优□良□中□及格□不及格二、论文(设计)水平、论文(设计)的理论意义或对解决实际问题的指导意义□优□良□中□及格□不及格、论文的观念是否有新意?设计是否有创意?□优□良□中□及格□不及格、论文(设计说明书)所体现的整体水平□优□良□中□及格□不及格建议成绩:□优□良□中□及格□不及格(在所选等级前的□内画“√”)评阅教师:(签名)单位:(盖章)年月日教研室(或答辩小组)及教学系意见教研室(或答辩小组)评价:一、答辩过程、毕业论文(设计)的基本要点和见解的叙述情况□优□良□中□及格□不及格、对答辩问题的反应、理解、表达情况□优□良□中□及格□不及格、学生答辩过程中的精神状态□优□良□中□及格□不及格二、论文(设计)质量、论文(设计)的整体结构是否符合撰写规范?□优□良□中□及格□不及格、是否完成指定的论文(设计)任务(包括装订及附件)?□优□良□中□及格□不及格三、论文(设计)水平、论文(设计)的理论意义或对解决实际问题的指导意义□优□良□中□及格□不及格、论文的观念是否有新意?设计是否有创意?□优□良□中□及格□不及格、论文(设计说明书)所体现的整体水平□优□良□中□及格□不及格评定成绩:□优□良□中□及格□不及格教研室主任(或答辩小组组长):(签名)年月日教学系意见:系主任:(签名)年月日中国计量学院本科毕业设计(论文)哈密尔顿图的判定及应用JudgementandapplicationofHamiltongraph哈密尔顿图的判定及应用摘要:哈密尔顿图的研究是图论中不可或缺的一部分这个问题的研究已经应用到了各个领域。合理的利用哈密尔顿图的结论不仅可以节约大量的时间更可以降低发展的成本。因此很多学者致力于哈密尔顿图的问题研究也得到了很多了不起的突破。本文第一章大致叙述了哈密尔顿图的背景发展和相关知识。阐述了哈密尔顿图的研究现状和本文研究方向。第二章总结了五种哈密尔顿图的判定方法,分别介绍了狄拉克定理、奥勒定理、博萨定理和萨瓦达定理并且补充了一个判定哈密尔顿图的必要条件。第三章着重介绍了货郎担问题的起源和发展并且补充了一种树的搜索法。关键词:哈密尔顿图判定方法货郎担问题中图分类号:OJudgementandapplicationofHamiltongraphAbstract:StudyingontheHamiltongraphisanindispensablepartingraphtheory,sincethisproblemiswidelyusedinavarietyoffieldsWhentheconclusionsofHamiltiongraphareproperlyused,itnotonlycansavealotoftime,butalsocanreducethecostofdevelopmentTherefore,manyscholarsdedicatedtotheHamiltongraphproblemsandgraphandsomerelatedknowledge,introducestheresearchstatusandresearchdirectionsofHamiltongraphThesecondchaptersummarizesfivemethodsfordeterminingHamiltongraphItintroducestheDiracTheorem,OregonTheorem,BossaTheoremandSavadaTheorem,andaddsanecessaryconditionfordeterminingHamiltongraphThethirdchaptermainlyintroducestheoriginanddevelopmentofthetravelingsalesmanproblem,andaddsamethodcalledtreesearchalgorithmKeywords:HamiltongraphJudgementmethodTravelingsalesmanproblemClassification:O目次摘要:IAbstract:II目次III引言哈密尔顿图的起源研究背景和意义哈密尔顿图判定方法的发展本文的研究方向哈密尔顿图的判定哈密尔顿图的定义哈密尔顿图的集中判定方法实例解析哈密尔顿图的判定在货郎担问题中的应用货郎担问题的由来和在现实中的应用货郎担问题解决方法树的搜索法结论参考文献作者简历学位论文数据集引言在查阅了大量资料后可以发现哈密尔顿图在数学理论研究和现实应用中都具有重要的地位。哈密尔顿图的研究解决了大量的问题但是还是有很多的问题还未得到解决。其中较为著名的就是关于货郎担问题的解决方案至今还没有很好的答案。本文在综合了各种哈密尔顿图的判定方法之后尝试用多种方法去解决货郎担问题在比较后找到一种相对较好的方法也为将来的继续研究提供研究方向。哈密尔顿图的起源哈密尔顿(Hamilton)是一位出生在爱尔兰的天文学家和数学家他的一生是很丰富多彩的自从他发现“四元数”后他又发现了另一种称之为“TheIcosianCalculus”的代数系统这个系统包含有乘法和加法的运算算子但是乘法并不满足交换律(即xyyx这个规律)。他发现的这个代数系统是和正则面体有关的。于是在年他提出下列周游世界的游戏:在正十二面体的二十个顶点上依次标记伦敦、巴黎、莫斯科、华盛顿、北京、东京等世界着名大城市正十二面体的棱(边)表示连接这些城市的路线。问:能否在图中做一次旅行,从顶点到顶点,沿着边行走,经过每个城市恰好一次之后再回到出发点曾经有很多人不断追寻这个游戏的答案。可以应用拓扑的思想将这正十二面体“拉平”将会得到一个和它同构的平面图(如图)这样进行就可以将这个游戏转化为:要求必须沿着正十二面体的棱怎样才能走完正则十二面体上的所有顶点而且最后又回到起点的问题。图:哈密尔顿周游世界图从此人们将这类图称作哈密尔顿图哈密尔顿图的研究也开始慢慢建立起来。研究背景和意义哈密尔顿图是图论的重要的一部分随着数学和科学技术的蓬勃发展它的应用已经渗透到自然科学、社会科学的各个领域。然而其发展的时间并不长所以还有很多的地方有待改进。其在货郎担问题的研究上更是进几十年才受到重视然而他的应用却是非常广泛的同样的方法可以用以地震搜救粮食分派粮食运输外出旅游等类似的各个方面。不仅能降低资源浪费还可以最大化成果对于受困的群众多一分钟就可以多一分生存的希望。研究哈密尔顿图的判定不仅仅在数学和科学领域具有很高的的研究价值在现实应用中更是可以得到有价值的结果。因此本文的研究方向是很具有现实意义。哈密尔顿图判定方法的发展年英国数学家狄拉克最早提出了判定哈密尔顿图的充分条件n阶连通图G,若,则G是哈密尔顿图。为哈密尔顿图的发展奠定了基础。年后即年美国著名的图论专家奥斯坦·奥勒推广狄拉克的工作得到了更为广泛的结果奥勒定理。:对于顶点个数大于的图如果图中任意两点度的和大于或等于顶点总数那这个图一定是哈密尔顿图。年匈牙利的一个叫博萨德的少年发表了仅有一页长的论文虽然论文很短只有仅仅一页但其结果却推广了奥勒定理。有一个的图它的满足不等式那么图就是哈密尔顿图。这一结果无疑是非常具有价值的所以在当时引起了很多的关注在之后的几年中很多人都尝试改进他的工作使其有一个系统清晰的结果最后终于有一个捷克的青年数学家萨瓦达得到了比他更为完整的结论。有一个的图而且满足条件对于任何一个小于的正整数i的不等式最少有一个是成立的那么图就是哈密尔顿图。年赵俊和宋序平只研究了连通图(还遗留连通的情况)的邻域并条件的哈密尔顿连通图,得到:连通n阶图G,若,则是哈密尔顿连通图或例外图。年月广西大学计算机与信息工程学院的罗示丰提出了一种判别哈密尔顿图的新方法在文章中他具体把方法分解为步:第步:第步:找出图度数最大的顶点第步:删去以及与关联的所有边第步:,,第步:若则停止计算,否则转第步。这种方法为计算机的判别提供了一个清晰的方向。时至今日无论国内还是国外都已经发现了哈密尔顿图的巨大作用很多研究者也把目光放在了哈密尔顿图的判定问题的解决上相信不久的将来就会有更加重大的突破。本文的研究方向从哈密尔顿图的问题出现以来无数的学者进行了多方面的研究也发现了无数哈密尔顿图的性质从而对其进行判定。然而问题的复杂性让我们的研究时间还是显得非常的短暂哈密尔顿图的判定问题至今也没有一个确定的最好的方法。而根据哈密尔顿图的判定条件的不同选用的方法也不尽相同。本文主要介绍哈密尔顿图判定的狄拉克定理、奥勒定理、博萨定理、萨瓦达定理。对这些定理进行详细的介绍及实例演示。在这些演示的基础上再补充定理以完善这些定理中的缺陷。最后将这些方法应用到著名的货郎担问题上来进行应用。在本文中其他定理及应用由于篇幅原因就不一一赘述了。哈密尔顿图的判定哈密尔顿图的定义设G是一个图包含图G中的每个顶点的路就称为哈密尔顿路。通过图G中每个顶点有且仅有一次的通路就称为哈密尔顿通路。通过图G中的每个顶点有且仅有一次的回路就称为哈密尔顿回路。一个图假如含有哈密尔顿回路则这个图就是哈密尔顿图。哈密尔顿图的集中判定方法那么当我们拿到一个图的时候怎么样去判断它是不是一个哈密尔顿图呢?如果是一个顶点较少的图那么有时候我们可以通过简单的尝试和错误的方法来判定。但是当顶点较多、通路较复杂的情况下这种方法就会让我们感到焦头烂额同时准确率也会大大下降。于是很多数学家开始尝试找到一种判定哈密尔顿的充分必要条件。遗憾的是至今为止还没有一种判定的充分必要条件事实上想要找到一个完全充分适用的判定方法几乎是没有可能的。但是数学家们依然没有放弃寻找一种简单的判定哈密尔顿图的方法这就形成了图论上一个著名的哈密尔顿问题。虽然目前得到的判定方法大多是存在一些充分不必要或者必要不充分的条件但是对于平时问题的解决和简单的应用来说在很多时候还是能起到简单判定的作用。下面将解析几种相对好的方法:由于对于任意一个图来说如果它是哈密尔顿图它的基础简单图一定是哈密尔顿图所以在判定的时候我们只要考虑简单图。狄拉克定理和奥勒定理最早提出判定哈密尔顿图的是英国的数学家狄拉克。狄拉克定理需要做的是记录每个顶点X上有多少条通路记通过顶点X的通路个数为D(X)当图的每个的顶点的D(X)相当大时这个图就是哈密尔顿图。定理(狄拉克定理):对于任意给定的一个图如果这个图的顶点数而且那么这个图就是哈密尔顿图。狄拉克发现上述定理的八年后经过不断的尝试和总结著名的美国图论学家奥斯坦·奥勒继续了狄拉克的工作推广了狄拉克定理得到了一个判定哈密尔顿图的基础结论为后面的研究打开了一个方向。定理(奥勒定理):对于任意给定的一个图如果这个图的顶点数对于任意的两个顶点x、y有那么这个图一定是哈密尔顿图。博萨定理和萨瓦达定理在奥勒定理被发现以后一个叫博萨德的匈牙利少年用一篇仅有一页长的论文对奥勒定理进行了推广得到了一个重要的定理引起了数学界的广泛关注。为了能更好的理解博萨定理的结论我们可以引入一些记号:对于任意的一个图Gx,x,…,xn在这里分别表示图G的所有顶点且序列数是由小到大排列的我们用D(G)表示序列(D(x),D(x),…,D(xn)),即存在关系有D(x)≤D(x)≤…≤D(xn)。再假设有两个序列其具有相同个数的数字:X=(xx…xn)Y=(yy…yn)。我们用X≥Y表示当且仅当对于每一个i=、、…、nj=、、…、n都满足xi≥yj。例如:X=()Y=()Z=()。我们可以得到Y≥X,但是Z≥X却是错误的。然后我们定义每一个的的整数得到一个序列P(n):当n是奇数时我们可以将P(n)定义成整数列:P(n)=(,,,……)一共包含n个数。当n是偶数时我们可以将P(n)定义成整数列:P(n)=(,,,……)一共包含n个数。根据定义我们可以得到:P()=()P()=()P()=()P()=()P()=()P()=()有了上面这些基础说明我们就能很清楚的阐述博萨德的重要发现了:定理(博萨定理)任意一个的图它的D(G)满足关系式有D(G)≥P(n),那么图G就是哈密尔顿图。博萨定理解决了很大一部分的哈密尔顿图的判定问题但是依然还存在一定的问题不满足博萨定理的图不一定不是哈密尔顿图很多人不断思索如何改进很多数学家提出了很多种改进方案但是经过比较之后捷克的数学家萨瓦达的结论脱颖而出。目前为止萨瓦达定理依旧是一种较好的哈密尔顿图的判定方法。他的结论如下。定理(萨瓦达定理)任意一个的图G且D(G)=(a,a,…,an)满足鞋面的条件:对于每一个小于的整数i的两个不等式a≥ian≥ni至少有一个是成立的那么图G就一定是哈密尔顿图。补充的一个必要定理萨瓦达定理对哈密尔顿图的判定做出了很大的改进让我们又多了一种简单的方法但是依然存在哈密尔顿图不满足萨瓦达定理。这个时候我们需要用到一个哈密尔顿图的必要条件。这个条件叙述如下:定理(一个判定的必要条件):设一个无向图G=(V,E)是一个哈密尔顿图V是V的一个非空子集则有P(GV)≤|V|。其中P(GV)表示从G中删除V得到的连同分支数。这个条件的必要性可以由一下方法证明:证明:假设C是图G中的一条哈密尔顿回路。若V当中的顶点是在C上彼此相邻的顶点那么显然有:P(CV)=≤|V|()若V中的顶点是在C上存在m个互不相邻那么就有:P(CV)=m≤|V|所以无论V中的顶点在C上是相邻或是不相邻或者兼有都可以得到结论P(CV)≤|V|同时由于C是图G的生成子图所以可以得到:P(CV)≤P(GV)≤|V|一般时候定理可以用来判定一个图是非哈密尔顿图。判定哈密尔顿图的方法还有很多但是最为常用的就是上述的五种方法当然时至今日不乏有比这五种方法更为准确全面的方法但是在这里就不一一介绍了。实例解析为了能够让读者更好的了解前文介绍的几种方法下面举几个实例来进行验证。图:图G、G在上图中的两个图G、G可以简单的应用定理(狄拉克定理)得到G中的每个顶点x都有D(x)=而n=所以有D(x)=≥=。同样图G中任何一个顶点都有D(x)=而n=所以有D(x)=≥=。由此可以判定图G、G是哈密尔顿图。这两个图的判定同样可以应用奥勒定理进行判定在图G中任意两点x、y有D(x)D(y)=≥在图G中任意两点x、y有D(x)D(y)=≥同样可以判定图G、G是哈密尔顿图。图:图G、G为了更好的体现博萨定理和萨瓦达定理的优越性可以使用图G来进行比较。应用狄拉克定理时明显n=且D(x)=≤=n不能判定它是哈密尔顿图。同样使用奥勒定理时min(D(x)D(y))=≤=n也不能判定。但是简单的观察就可以发现图G是一个哈密尔顿图。这个时候我们就可以用博萨定理进行判定。根据博萨定理有D(G)=()而P()=()根据比较就有D(G)≥P()从而可以得到图G是哈密尔顿图。同样也可以根据萨瓦达定理来进行判定因为n=所以小于n的i有i=、。当i=时a=≥=i成立当i=时an=≥=ni成立同样可以判定图G是哈密尔顿图。然而博萨定理和萨瓦达定理同样是不完善的这一点图G给我们作出了很好的例子。在应用博萨定理时D(G)=()P()=()此时我们是不能说D(G)≥P()的没办法判定G是哈密尔顿图。萨瓦达定理也对这个问题表示无能为力在图G中n=所以小于n的正整数i=、、。当i=时a=≥=i不成立an=≥=ni不成立此时违反萨瓦达定理所以也不能判定G是哈密尔顿图。然而简单观察后就可以发现图G是一个哈密尔顿图所以博萨定理和萨瓦达定理是有一定的缺陷的。图G为我们的进一步研究提供了方向让我们能够不断的深入。相信在不久的将来会有一种简单的方法可以帮助我们得出结论。哈密尔顿图的判定在货郎担问题中的应用货郎担问题的由来和在现实中的应用货郎担问题是由德国的著名数学家肯·蒙那哥在年提出来的年来一直是哈密尔顿图的应用中的最典型的例子无数人对其进行废寝忘食的研究。这个问题可以表述为:假设一个售货员需要在n个城市之间进行销售现在我们已经知道了这n个城市中任意的两个城市之间的距离现在售货员需要选择一条路线使得从出发的城市开始经过其他的城市有且仅有一次最后回到出发点问这个售货员应该怎么样选择路线呢。将上述的问题进行数学提炼后所求的问题可以转化为在一个加附了权值的完全图中寻找一个权值最小的哈密尔顿回路。看似简单但实际上却是非常复杂的问题至今任何一种简化的解决方法都能够带来无法想象的价值。因为生活中需要遇到货郎担问题的地方实在是太多了例如:()当我们外出旅游的时候提前安排好路程最短的路线不仅可以节省交通上的成本还可以得到更多的时间来参观。()当地震等天灾发生时我们需要组建搜救队伍对受灾区域进行救援在受灾程度相近的情况下安排合适的搜救路线不仅可以挽回很多的经济损失更重要的是可以挽救更多的生命。()再假设当我们出差坐飞机时由于各地的情况不同导致各个地方之间的价格会不一样。我们选择合适的城市顺序可以让我们得到大幅度的节约成本。为公司创造更多的利润。这类的问题还有很多而这些问题都可以归结为货郎担问题。所以货郎担问题的研究是与生活直接相关的是非常具有现实意义的。货郎担问题解决方法那么到底应该怎样去解决货郎担问题呢遗憾的是直到目前为止虽然无数人为止奋斗也得到了一些正确的结论但是还是没有一种能够简单的解决哈密尔顿图的方法。美国的《管理科学》中有一篇讨论“货郎担问题”的文章该文中提到:人类由于他的计算能力的限制在解决货郎担问题上并不好。所以现在人们对于这个问题的研究已经开始借助电子计算机来进行实现。年月日《纽约时报》上出现了一篇很有影响力的文章它的标题为《苏联的发现震动数学界》这篇文章虽然有一定的夸大成分存在但是他所说的把货郎担问题的解决和计算机联系起来的思想确实没有错的。年广西大学计算机与信息工程学院的罗示丰提出了用计算机判定哈密尔顿图的方法。虽然这个方法还未应用到货郎担问题的解决上但是却也坚定了很多人继续往这个方向研究的信心在不久的将来这个问题一定可以获得更大的突破。德国是一个非常严谨的国家德国的波恩大学的一位数学家很好的发挥了这一特点当他知道西德有个有铁路穿过的城市后就准备找到一个最短路程的回路应该怎么样去跑。他费尽心血从铁路局找到了准确的城市间铁路的长度把整个问题变成了一个有个变数个方程及个不等式的线性规划问题人类的大脑已经对这样的问题表示无能为力了最后不得不用电子计算机去算才得到了最短的回路是公里。结果见图。图:西德个城市最短路线图树的搜索法那么在一般情况下我们可以借用什么方法来解决货郎担问题呢?在这里介绍一种较为简单的方法树的搜索法。为了更好的理解这个方法在这里我们举一个例子加以说明:设共有A、B、C、D、E五个城市我们需要从A出发经过B、C、D、E四个城市有且仅有一次最后再回到A。A、B、C、D、E五座城市之间的距离由下表进行表出:表:五个城市之间的距离表ABCDBCDE图:五个城市之间的连通情况我们选择从点A出发先写A()表示最初没有出发路线是的路程长度是然后我们可以列出下一步可能到达的城市分别由B、C、D、E可以得到四个节点为AB()、AC()、AD()、AE()。见图。图:树的搜索法第一步现在我们可以看到由城市B可能到达的城市有C、D、E把节点AB()划掉我们可以得到三个新的节点ABC()、ABD()、ABE()后面的、、分别表示BC、BD、BE的长度以此类推我们还可以得到的新节点有ACB()、ACD()、ACE()、ADB()、ADC()、ADE()、AEB()、AEC()、AED()九个节点。见图。图:树的搜索法第二步根据上述法则继续推广就可以知道假设是ABC的路径那么到达C城以后就只剩下了两种可能路径:ABCDEA和ABCEDA于是我们划掉节点ABC()得到两个新的节点ABCDEA()和ABCEDA()。以此类推我们可以得到其他的二十二个节点ABDCEA()、ABDECA()、ABECDA()、ABEDCA()、ACBDEA()、ACBEDA()、ACDBEA()、ACDEBA()、ACEBDA()、ACEDBA()、ADBCEA()、ADBECA()、ADCBEA()、ADCEBA()、ADEBCA()、ADECBA()、AEBCDA()、AEBDCA()、AECBDA()、AECDBA()、AEDBCA()、AEDCBA()。见图。图:树的搜索法第三步根据图我们可以发现在个城市之间我们一共可以得到二十四条回路其中最短的两条为ABEDCA()和ACDEBA()。由此我们得到了在五个城市之间销售的最佳路线。做完这全部的工作后我们回过头去看这个方法可以发现在最后一步的计算时一部分的工作是可以省略的。比如当我们找到第一条回路ABCDEA时我们可以知道这条路径的长度是那么在之后的计算中一旦发现路径的长度明显大于或者上一层的节点的数值已经大于了那么我们直接可以用“≥”来代替具体的数值。当计算到ABEDCA这条路径时我们发现数值是那么之后的数值如明显大于那么久可以用“≥”来替代这样可以节省一定的计算时间加快得出结果的速度。在上面方法展示的过程中我们可以发现这样的搜索方法在地点数量较少的时候还比较试用一旦地点数量达到十个那么我们的计算量将变的吓人甚至可以说是超过了人脑的计算能力我们会感到十分的繁琐。如果十个地点还可以勉强算出来那么地点数量达到个或者个呢?那时候的计算量是我们无法想象的而这种情况对于像中国这样的大国来说是非常现实的问题。这个时候我们就不得不借助计算机的力量。计算机到底可以提升多少的计算速度呢?一个例子能够很好的说明问题:在美国工作的华籍数学家LinShen及HongSaman等人在年的时候用电子计算器计算得到了一个有关于个城市的货郎担问题。这个问题一旦化成线性规划问题那么就要处理有个变数的方程式及不等式人脑对于这样的问题虽然不能说完全不能解决但是所需要的时间将是难以想象的。而当时的LinShen等人借助了一台IBM的式的电子计算机后仅用了分钟就得到了一个最优解纳闷对于电子技术日新月异的今天我们可能需要的时间已经不足一分钟。两者互相对比让我们不得不承认以后的发展方向将更多的借助计算机技术。结论哈密尔顿图相可以应用的范围已经越来越广阔从工业铺路到农业灌溉航空路线到海底勘探从国家的发展到公司的运输都可以用到哈密尔顿图的知识。哈密尔顿图的研究已经显得越来越重要在效率第一的当今社会恰当的应用哈密尔顿图的研究结果可以可以大大提高工作的效率和节约发展成本为可持续发展提供不可或缺的支持。本文借鉴总结了大量前人的结论着重介绍了哈密尔顿图判定上的五种方法和结论并初步对这五种方法的应用范围进行了分类。在哈密尔顿图的应用方面着重介绍了货郎担问题的研究。在解决方法上又介绍了树的搜索法同时也说明了解决方法的未来发展方向。参考文献DiracGASometheoremsonabstractgraphsJProcLondonMathSoc,:。FaudreeRJ,GouldRJ,JacobsonMS,etalNeighborgraphsJArsCombinatoria,,:。赵俊,宋序平最小度与Hamilton连通图J扬州大学学报,,:。尹家洪,邻集并与hamiltonian性J,东南大学学报,,。陈显强,吴集林,论哈密尔顿图的判定问题,科学技术与工程报年第期。罗示丰,判别哈密尔顿图的新方法J,广西科学院学报,年月第十七卷第期。赵克文,新的充分条件和哈密尔顿图J,中国工程科学,年月第卷第期。FanGHNewsufficientconditionsforcyclesingraphsJJCombinTheorySerB,:~。于言坤哈密尔顿图的矩阵判定法吉林教育学院学报(下旬)陈德钦、赵克文,哈密尔顿图的邻域交和邻域并条件,科学技术与工程,年月第卷第期。赵克文,曾克扬,一个充分条件和Hamilton连通图,应用科学学报,年月第卷 第期。赵克文对连通n阶图某些结果的改进J吉林大学自然科学学报,,:。LiqunPua,HungLinFub,HaoShencMaximalsetsofHamiltoncyclesinDnJscienceDirect。BJackson,Longpathsandcyclesinorientedgraphs,JGraphTheory()–。耿素云,屈婉玲离散数学基础,北京大学出版社,年月第版。罗示丰两图同构的判别准则及其复杂性计算机科学,,()专辑:~。钱颂迪等,《运筹学》,清华大学出版社~。魏权龄等,《运筹学通论》,中国人民大学出版社。徐俊明,《图论及其应用》,中国科技大学出版社。王树禾,《图论及其算法》,中国科技大学出版社。李修睦,《图论导引》,华中工学院出版社。卢开澄等《,图论及其应用》,清华大学出版社。作者简历徐杰一村男出生与年月浙江省宁波市余姚市人年月至年月就读于中国计量学院。在校期间获得社会工作奖学金三次校军训积极分子校亮点网优秀部长。关键词*密级*中图分类号*UDC哈密尔顿图判定方法货郎担问题公开O论文赞助学位授予单位*学位授予单位代码*学位类别*学位级别*中国计量学院理学学士论文题名*哈密尔顿图的判定及应用论文语种*并列题名*无简体中文作者姓名*徐杰一村学号*培养单位名称*培养单位代码*培养单位地址邮编中国计量学院浙江省杭州下沙高教园区学源街学科专业*研究方向*学制*学位授予年*信息与计算科学年论文提交日期*导师姓名*陈琴职称*讲师评阅人答辩委员会主席*答辩委员会成员电子版论文提交格式文本(√)图像()视频()音频()多媒体()其他()推荐格式:applicationmswordapplicationpdf电子版论文出版(发布者)电子版论文出版(发布)地权限声明论文总页数*注:共项其中带“*”为必填数据。毕业设计(论文)原创性声明和使用授权说明原创性声明本人郑重承诺:所呈交的毕业设计(论文)是我个人在指导教师的指导下进行的研究工作及取得的成果。尽我所知除文中特别加以标注和致谢的地方外不包含其他人或组织已经发表或公布过的研究成果也不包含我为获得及其它教育机构的学位或学历而使用过的材料。对本研究提供过帮助和做出过贡献的个人或集体均已在文中作了明确的说明并表示了谢意。作者签名:     日 期:     ​​​​​​​​​​​​指导教师签名:     日  期:     使用授权说明本人完全了解大学关于收集、保存、使用毕业设计(论文)的规定即:按照学校要求提交毕业设计(论文)的印刷本和电子版本学校有权保存毕业设计(论文)的印刷本和电子版并提供目录检索与阅览服务学校可以采用影印、缩印、数字化或其它复制手段保存论文在不以赢利为目的前提下学校可以公布论文的部分或全部内容。作者签名:     日 期:     ​​​​​​​​​​​​学位论文原创性声明本人郑重声明:所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名:日期:年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定同意学校保留并向国家有关部门或机构送交论文的复印件和电子版允许论文被查阅和借阅。本人授权    大学可以将本学位论文的全部或部分内容编入有关数据库进行检索可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。涉密论文按学校规定处理。作者签名:日期:年月日导师签名:日期:年月日毕业设计(论文)原创性声明和使用授权说明原创性声明本人郑重承诺:所呈交的毕业设计(论文)是我个人在指导教师的指导下进行的研究工作及取得的成果。尽我所知除文中特别加以标注和致谢的地方外不包含其他人或组织已经发表或公布过的研究成果也不包含我为获得及其它教育机构的学位或学历而使用过的材料。对本研究提供过帮助和做出过贡献的个人或集体均已在文中作了明确的说明并表示了谢意。作者签名:     日 期:     ​​​​​​​​​​​​指导教师签名:     日  期:     使用授权说明本人完全了解大学关于收集、保存、使用毕业设计(论文)的规定即:按照学校要求提交毕业设计(论文)的印刷本和电子版本学校有权保存毕业设计(论文)的印刷本和电子版并提供目录检索与阅览服务学校可以采用影印、缩印、数字化或其它复制手段保存论文在不以赢利为目的前提下学校可以公布论文的部分或全部内容。作者签名:     日 期:     ​​​​​​​​​​​​学位论文原创性声明本人郑重声明:所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名:日期:年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定同意学校保留并向国家有关部门或机构送交论文的复印件和电子版允许论文被查阅和借阅。本人授权    大学可以将本学位论文的全部或部分内容编入有关数据库进行检索可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。涉密论文按学校规定处理。作者签名:日期:年月日导师签名:日期:年月日指导教师评阅书指导教师评价:一、撰写(设计)过程、学生在论文(设计)过程中的治学态度、工作精神□优□良□中□及格□不及格、学生掌握专业知识、技能的扎实程度□优□良□中□及格□不及格、学生综合运用所学知识和专业技能分析和解决问题的能力□优□良□中□及格□不及格、研究方法的科学性技术线路的可行性设计方案的合理性□优□良□中□及格□不及格、完成毕业论文(设计)期间的出勤情况□优□良□中□及格□不及格二、论文(设计)质量、论文(设计)的整体结构是否符合撰写规范?□优□良□中□及格□不及格、是否完成指定的论文(设计)任务(包括装订及附件)?□优□良□中□及格□不及格三、论文(设计)水平、论文(设计)的理论意义或对解决实际问题的指导意义□优□良□中□及格□不及格、论文的观念是否有新意?设计是否有创意?□优□良□中□及格□不及格、论文(设计说明书)所体现的整体水平□优□良□中□及格□不及格建议成绩:□优□良□中□及格□不及格(在所选等级前的□内画“√”)指导教师:(签名)单位:(盖章)年月日评阅教师评阅书评阅教师评价:一、论文(设计)质量、论文(设计)的整体结构是否符合撰写规范?□优□良□中□及格□不及格、是否完成指定的论文(设计)任务(包括装订及附件)?□优□良□中□及格□不及格二、论文(设计)水平、论文(设计)的理论意义或对解决实际问题的指导意义□优□良□中□及格□不及格、论文的观念是否有新意?设计是否有创意?□优□良□中□及格□不及格、论文(设计说明书)所体现的整体水平□优□良□中□及格□不及格建议成绩:□优□良□中□及格□不及格(在所选等级前的□内画“√”)评阅教师:(签名)单位:(盖章)年月日教研室(或答辩小组)及教学系意见教研室(或答辩小组)评价:一、答辩过程、毕业论文(设计)的基本要点和见解的叙述情况□优□良□中□及格□不及格、对答辩问题的反应、理解、表达情况□优□良□中□及格□不及格、学生答辩过程中的精神状态□优□良□中□及格□不及格二、论文(设计)质量、论文(设计)的整体结构是否符合撰写规范?□优□良□中□及格□不及格、是否完成指定的论文(设计)任务(包括装订及附件)?□优□良□中□及格□不及格三、论文(设计)水平、论文(设计)的理论意义或对解决实际问题的指导意义□优□良□中□及格□不及格、论文的观念是否有新意?设计是否有创意?□优□良□中□及格□不及格、论文(设计说明书)所体现的整体水平□优□良□中□及格□不及格评定成绩:□优□良□中□及格□不及格(在所选等级前的□内画“√”)教研室主任(或答辩小组组长):(签名)年月日教学系意见:系主任:(签名)年月日学位论文原创性声明本人郑重声明:所呈交的学位论文是本人在导师的指导下进行的研究工作所取得的成果。尽我所知除文中已经特别注明引用的内容和致谢的地方外本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体均已在文中以明确方式注明并表示感谢。本人完全意识到本声明的法律结果由本人承担。学位论文作者(本人签名):年月日学位论文出版授权书本人及导师完全同意《中国博士学位论文全文数据库出版章程》、《中国优秀硕士学位论文全文数据库出版章程》(以下简称“章程”)愿意将本人的学位论文提交“中国学术期刊(光盘版)电子杂志社”在《中国博士学位论文全文数据库》、《中国优秀硕士学位论文全文数据库》中全文发表和以电子、网络形式公开出版并同意编入CNKI《中国知识资源总库》在《中国博硕士学位论文评价数据库》中使用和在互联网上传播同意按“章程”规定享受相关权益。论文密级:□公开□保密(年月至年月)(保密的学位论文在解密后应遵守此协议)作者签名:导师签名:年月日年月日独创声明本人郑重声明:所呈交的毕业设计(论文)是本人在指导老师的指导下独立进行研究工作所取得的成果成果不存在知识产权争议。尽我所知除文中已经注明引用的内容外本设计(论文)不含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体均已在文中以明确方式标明。本声明的法律后果由本人承担。 作者签名:二〇一〇年九月二十日 毕业设计(论文)使用授权声明本人完全了解滨州学院关于收集、保存、使用毕业设计(论文)的规定。本人愿意按照学校要求提交学位论文的印刷本和电子版同意学校保存学位论文的印刷本和电子版或采用影印、数字化或其它复制手段保存设计(论文)同意学校在不以营利为目的的前提下建立目录检索与阅览服务系统公布设计(论文)的部分或全部内容允许他人依法合理使用。(保密论文在解密后遵守此规定) 作者签名:二〇一〇年九月二十日致谢时间飞逝大学的学习生活很快就要过去在这四年的学习生活中收获了很多而这些成绩的取得是和一直关心帮助我的人分不开的。首先非常感谢学校开设这个课题为本人日后从事计算机方面的工作提供了经验奠定了基础。本次毕业设计大概持续了半年现在终于到结尾了。本次毕业设计是对我大学四年学习下来最好的检验。经过这次毕业设计我的能力有了很大的提高比如操作能力、分析问题的能力、合作精神、严谨的工作作风等方方面面都有很大的进步。这期间凝聚了很多人的心血在此我表示由衷的感谢。没有他们的帮助我将无法顺利完成这次设计。首先我要特别感谢我的知道郭谦功老师对我的悉心指导在我的论文书写及设计过程中给了我大量的帮助和指导为我理清了设计思路和操作方法并对我所做的课题提出了有效的改进方案。郭谦功老师渊博的知识、严谨的作风和诲人不倦的态度给我留下了深刻的印象。从他身上我学到了许多能受益终生的东西。再次对周巍老师表示衷心的感谢。其次我要感谢大学四年中所有的任课老师和辅导员在学习期间对我的严格要求感谢他们对我学习上和生活上的帮助使我了解了许多专业知识和为人的道理能够在今后的生活道路上有继续奋斗的力量。另外我还要感谢大学四年和我一起走过的同学朋友对我的关心与支持与他们一起学习、生活让我在大学期间生活的很充实给我留下了很多难忘的回忆。最后我要感谢我的父母对我的关系和理解如果没有他们在我的学习生涯中的无私奉献和默默支持我将无法顺利完成今天的学业。四年的大学生活就快走入尾声我们的校园生活就要划上句号心中是无尽的难舍与眷恋。从这里走出对我的人生来说将是踏上一个新的征程要把所学的知识应用到实际工作中去。回首四年取得了些许成绩生活中有快乐也有艰辛。感谢老师四年来对我孜孜不倦的教诲对我成长的关心和爱护。学友情深情同兄妹。四年的风风雨雨我们一同走过充满着关爱给我留下了值得珍藏的最美好的记忆。在我的十几年求学历程里离不开父母的鼓励和支持是他们辛勤的劳作无私的付出为我创造良好的学习条件我才能顺利完成完成学业感激他们一直以来对我的抚养与培育。最后我要特别感谢我的导师赵达睿老师、和研究生助教熊伟丽老师。是他们在我毕业的最后关头给了我们巨大的帮助与鼓励给了我很多解决问题的思路在此表示衷心的感激。老师们认真负责的工作态度严谨的治学精神和深厚的理论水平都使我收益匪浅。他无论在理论上还是在实践中都给与我很大的帮助使我得到不少的提高这对于我以后的工作和学习都有一种巨大的帮助感谢他耐心的辅导。在论文的撰写过程中老师们给予我很大的帮助帮助解决了不少的难点使得论文能够及时完成这里一并表示真诚的感谢。unknownunknownunknownunknownunknownunknownunknownunknownunknownunknownunknownunknownunknownunknownunknownunknownunknownunknownunknownunknownunknownunknownunknownunknownunknownunknownunknownunknownunknownunknownunknownunknownunknownunknownunknownunknownunknown

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

评分:

/40

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利