利用图论知识解决实际问题

《利用图论知识解决实际问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、淮北师范大学2013届学士学位论文利用图论知识解决实际问题的方法探究学院、专业数学科学学院数学与应用数学研究方向离散数学学生姓名杨波学号20091101179指导教师姓名刘楠楠指导教师职称讲师2013年3月25日利用图论知识解决实际问题的方法探究杨波（淮北师范大学数学科学学院，淮北，235000）摘要图论是数学的一个分支,是近年来发展迅速而又应用广泛的一门新兴学科。随着科学的进步，图论知识越来越贴近于生产和生活，所以利用图论知识来解决实际问题又成为当今的一大热点。着色、绘图、运输最短路径、集合等都与图论知识离不开。本课题将重点利用图论知识来解决实际生活、生产中的问题。本

2、文首先介绍了图的基本概念，对图论所涉及的基本知识进行简单的阐述，使读者对图论知识有一定的了解；再介绍图论中两种特殊的图形：欧拉图和哈密顿图，并用它们分析如何解决最短路问题和货郎担问题；然后介绍着色问题以及其与实际生活的联系；最后通过实例来说明图论知识在日常生产、生活中的运用。关键词图论，欧拉图，哈密顿图，最短路径，着色问题,应用ThemethodofusinggraphtheoryknowledgetosolvepracticalproblemsYangBo（CollegeofMathematicalScience,HuaibeiNormalUniversity,Hua

3、ibei,235000）AbstractGraphtheoryisabranchofmathematicsthathasbeendevelopedrapidlyandusedwidelyinrecentyears.Withtheprogressofscience,graphtheoryisincreasinglyclosetotheproductionandlife,sousingtheknowledgeofgraphtheorytosolvepracticalproblemshasbecomeafocustoday.Coloring,drawing,theshorte

4、stpathoftransportationcannotbeseparatedfromgraphtheoryknowledge.Thearticlelayspressontheusingofgraphtheorytosolvethepracticalproblemsinproductionknowledgeinreallife.Thisarticlefirstintroducesthebasicconceptofgraph,andmakeafurtherintroductiontothebasicknowledgeofgraphtheorywhichinvolvedas

5、impleelaboration,thenthereadercanhaveacertainknowledgeofgraphtheoryknowledge;Thentwokindsofspecialgraphicsarereferredto:theEuleriangraphandHamiltoniangraph,alongwiththeiranalysisofhowtosolvetheproblemoftheshortcircuitandtravelingsalesmanproblem.Thenthearticlediscussthecoloringproblemandi

6、tslinkswithreallife;Finallybyanexampletoillustratetheapplicationofgraphtheoryknowledgeindailylifeandproduction.KeywordsGraphtheory,Euleriangraph,Hamiltoniangraph,shortestpaths,coloring,application目录引言1（一）预备知识11图的基本概念12通路与回路43图的连通性64图的矩阵表示8（二）欧拉图与哈密顿图101欧拉图102哈密顿图.103最短路问题与货郎担问题.13（三）着色16

7、1点着色162边着色16（四）图论知识在实际生活、生产中的应用181哥尼斯堡七桥问题182哈密顿图的实际应用193教师如何分配课时问题20结论21参考文献21致谢23引言在现实生活中，我们会遇到很多复杂的问题，介于此我们希望用到我们所学过的数学方法去简化它，优化它和解决它。图论知识就是一个很好的工具，将实际问题化为图后，我们能清楚的观察到整个局面，方便我们进行具体的分析。所以研究和总结图的应用算法是件有意义且必要的事情。本课题将着重通过图论知识来解决实际生活、生产中所遇到的着色，最短路径，绘图等问题。通过其在实际生活中的应用，来认识图论知