陈丽萍图论作业

《陈丽萍图论作业》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图论及其应用论文题目：重庆歌乐山任意景点间最短路径问题2013-2014学年第一学期指导教师蒲兴成科目图论及其应用姓名陈丽萍学号S130131008专业电子与通信工程2013年12月9日重庆歌乐山任意景点间最短路径问题摘要：从300多年前的诞生以来，图论以它描述和解决问题直观有效等特点，成为了人们研究的重要方法，在实际中也得到广泛应用。本文简单介绍了图论的发展与特点，阐述了任意两点间最短路径问题及其算法。并采用Floyd-Warshall算法来解决重庆歌乐山任意景点间最短路径问题，介绍算法的思想、过程，最后用C+

2、+实现。通过运行比较，结果与理论一致，任意两点间最短路径问题。【关键字】任意的最短路径Floyd-Warshall算法导游图C++TheproblemofQixinggeleshanshortestpathbetweenanytwopointsonFloyd-WarshallAbstract：Sincethebirthofgraphtheory300yearsago,ithasbecomeanimportantresearchmethodwithitsintuitiveandeffectivecharacteri

3、stics.Ithasalsobewidelyusedinpractical.Thispaperbrieflydescribesthedevelopmentandcharacteristicsofgraphtheory，andexplaintheproblemofshortestpathbetweenanytwopointsanditsalgorithmalso.Moreover，thepaperuseFloyd-WarshallalgorithmtosolveTheproblemofQixinggeleshan

4、shortestpathbetweenanytwopoints.Atthesametime,ittheideaprocessofthealgorithmandfinallyimplementitbyC++.Bycomparingthetheoreticalandrunningresults，wecanachievethetarget.【KeyWords】anytwopointsshortestpathFloyd-WarshallalgorithmtourmapC++一．绪论1736年瑞士著名的天才数学家欧拉提出了

5、著名的哥尼斯堡七桥问题，这是历史上第一篇图论的论文，它的发表标志着图论作为一门科学诞生了。在19世纪，许多关于图论的重要结论就已经得出，但是图论引起广大学者的注意并得以广泛接受和传播是在20世纪20年代以后。图论的产生和发展经历了二百多年的历史，大体上可分为三个阶段：第一阶段是从1736年到19世纪中叶。当时的图论问题是盛行的迷宫问题和游戏问题。最有代表性的工作是著名数学家L.Euler于1736年解决的哥尼斯堡七桥问题(KonigsbergSevenBridgesProblem)。第二阶段是从19世纪中叶到19

6、36年。图论主要研究一些游戏问题：迷宫问题、博弈问题、棋盘上马的行走线路问题。一些图论中的著名问题如四色问题(1852年)和Hamilton环游世界问题(1856年)也大量出现。同时出现了以图为工具去解决其它领域中一些问题的成果。1847年德国的克希霍夫(G.R.Kirchoff)将树的概念和理论应用于工程技术的电网络方程组的研究。1857年英国的凯莱(A.Cayley)也独立地提出了树的概念，并应用于有机化合物的分子结构的研究中。1936年匈牙利的数学家哥尼格(D.Konig)写出了第一本图论专著《有限图与无限

7、图的理论》(TheoryofdirectedandUndirectedGraphs)。标志着图论作为一门独立学科。第三阶段是1936年以后。由于生产管理、军事、交通运输、计算机和通讯网络等方面的大量问题的出现，大大促进了图论的发展。特别是电子计算机的大量应用，使大规模问题的求解成为可能。实际问题如电网络、交通网络、电路设计、数据结构以及社会科学中的问题所涉及到的图形都是很复杂的，需要计算机的帮助才有可能进行分析和解决。目前图论在物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、社会科学及经济管理等

8、几乎所有学科领域都有应用。二．图论的基础知识2.1图的定义设是有序二元组，如果满足以下条件：（1）是非空有限集；（2）是中不同元素的非有序对偶组成的集合；则称G为一个简单的无向图。2.2构成图论中的图有三个要素：点——抽象表示具体事物，既没有大小，又没有位置区别边——反映事物之间有联系，不考虑长度和形状方向——指明起点及终点，表示事物间的关系特征2.3图的一些基本概念我