【硕士论文】哈密尔顿图在实际中的应用.pdf

《【硕士论文】哈密尔顿图在实际中的应用.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、山西大学硕士学位论文哈密尔顿图在实际中的应用姓名：燕建梁申请学位级别：硕士专业：基础数学指导教师：李胜家20060601摘要摘要到目前为止，哈密尔顿图的非平凡的充分必要条件尚不清楚，事实上，这是图论中还没解决的主要问题之一，但哈密尔顿图在实际问题中，应用又非常广泛，因此哈密尔顿图一直受到图论界以及运筹学学科研究人员的大力关注。本文主要讨论了HamiIton图的相关知识及其应用。第～章：简单介绍了Hamiiton图的产生及发展过程。第二、三章：在给出Hamilton图的有关概念的基础上，讨论Hamilton图存在的必要条件和充分条件。第四章：介绍并讨论了Hami

2、iron图在实际中的应用——旅行货郎问题，用搜索方法得出了有关最优解。第五章：介绍了1998年全国大学生数学建模竞赛题《灾情巡视路线》，给出了比较好的解决方法。关键词：哈密尔顿图；必要条件；充分条件；旅游货郎问题灾情巡视路线哈密尔顿图的应用ABSTRACTUptonow,thesufficientconditionsandnecessaryconditionsofthenontrivialfortheHamiltongrapharestillunclear．Infact，itisoneofthemajorunsolvedproblemsingraphtheor

3、y，butitiswidelyusedinmanyrealapplications．ThispaperdiscussestherelatedconditionsandapplicationsfortheHamiltongraphChapter1introducestheoriginoftheHamiltongraphanditsevolvement．Chapter2-3introducestherelatedconceptsoftheHamiltongraph，andfurtherdiscussesitssufficientconditionsandneces

4、saryconditionsrespectively．Chapter4discussesoneofthemajorapplicationsoftheHamiltongraph⋯一一Thetravelingsalesmanproblem，andproposesasearchingalgorithmthatsolvesthebestsolutionproblem．Chapter5introduces“Theproblemofmakinganinspectiontourfortheconditionofadisaster'’inthemodelingcompetit

5、ionofmathematicsforthenationalcollegein1998andgivesagoodsolutiontothisproblemKeywords：Hamiltongraph；sufficientcondition；necessarycondition；Thetravelingsalesmanproblem；DisasterConsiderrevising2引言图论是一门既古老又年轻的学科。随着科学技术的蓬勃发展，它的应用已经渗透到自然科学、社会科学的各个领域。利用它可以解决很多实际问题。对于图沦中的欧拉(Euler)图以及与之有关的邮

6、递员问题等已经有了很好的解决方法，然而哈密尔顿(Hamiiron)图以及与之有关的旅游货郎问题一直悬而未决。哈密尔顿(Hamiiron)图理论有着重要的理论意义和实际意义，许多图论以及运筹学学科研究人员都进行着深入的研究。大部分图论及其应用书上都给出Hamilton图的有关概念，一些文献上给出了HamiIton图存在的必要条件和个别充分条件，但都不完善。本文第一章简单介绍了Hamilton图的产生及发展过程。第二章在给出Hamilton图的有关概念的基础上讨论Hamilton图存在的必要条件和充分条件。第三章介绍并讨论了Hamiiron图在世纪中的应用——旅游

7、货郎问题，用搜索方法得出了有关最优解的问题。第四章：介绍了1998年全国大学生数学建模竞赛题《灾情巡视路线》问题，给出了比较好的解决方法目前，图论的理论与方法在计算机科学、运筹学、电网络分析、化学、物理以及社会科学等方面起着很重要的作用：同时，对数学竞赛与数学建模及其应用起指导作用；利用图论的理论与方法，可以解决很多实际问题。本文起一个抛砖引玉的作用，希望更多的数学爱好者了解并关注此问题，以便更好地为实际服务，解决更多的实际问题。哈密尔顿图的应用第一章哈密尔顿图的产生哈密尔顿(Hamiiron)是爱尔兰的一位数学家和天文学家。他的一生是多姿多彩的，自从哈密尔顿

8、发现“四元数”之后，他又发现了另外一种