简谈图论期末论文

《简谈图论期末论文》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、简谈图论期末论文简谈图论期末论文导读：最典型的两种求解最短路径算法分别是Dijkstra算法和Floyd算法，其中Dijkstra算法适用于计算指定顶点之间的最短路径，而Floyd算法适用于计算一个图或者X中所有顶点间的最短路径。3.2最短路径算法3.2.1Dijkstra算法Dijkstra算法又称为标号法，是1959年由荷兰计算机科学家E.W.Dijkstra提出的关于最短路径的搜索算法。该算法是图论在重庆地铁中的应用1.引言图论是数学的一个分支，并且是组合数学和应用数学的一部分。它以图做为研究对象，而图是由若干节点和节点之间的边所构成的图型。在图论中，图

2、往往是某个具体现实生活中问题的数学抽象，可以说，图中的节点代表着生活中的某些特定事物，而节点之间的边则代表着节点之间的特定联系。图论这门学科需要解决的就是如何利用数学知识去解决它们之间的关系。图论最早起源于1736年著名的柯尼斯堡七桥问题[1]。这个问题的内容是：在柯尼斯堡的普莱格尔河上有七座桥将河中的岛屿与河岸连接起来。问题是要从这四块陆地中任何一块开始，通过每一座桥正好一次，最后再回到起始点。然而人们无数次的尝试解决却都没有成功。直到1736年，欧拉解决了这个问题。他用抽像分析法将这个问题化为世界上第一个图论问题：即把每一块陆地用一个点来代替，将每一座桥用

3、联接相应的两个点的一条边来代替，从而得到了一个“图”。最终，欧拉成功证明了这个问题是无解的，并且推广了这个问题的意义，给出了对于一个给定的图可以某种方式走遍的判定法则。这就是后来的欧拉通路、欧拉回路以及欧拉图问题。于是，欧拉成为了图论学的创始人。从那以后开始的几百年间，图论开始了飞速的发展。虽然图论研究的是点和边之间所构成图的问题，但其应用领域还是十分广阔的。图论的应用不仅仅局限于数学问题和计算机领域，它同时还涵盖了交通管理、通信领域、社会学等诸多其他研究领域。而最短路径问题是图论应用中的基本问题。最短路径顾名思义就是在所有的路径中找出一条距离最短的有效路径。

4、实际上，这里所指的“距离”不仅仅是指地理意义上的距离，还可以引申到时间、费用、等其他度量单位上面。本文中，以重庆地铁为研究对象，利用图论知识解决在搭乘重庆地铁时的最短路径问题。可以说，最短路径问题再交通X络结构的分析以及交通路线的选择中都有重要的应用价值。此外，最短路径问题一直是计算机科学、地理信息学、交通管理学等学科中一个研究的热点问题。图的着色是指对图的每个节点指定一种颜色，使得相邻的节点的颜色不相同。着色问题在实际中有很多的应用，比如可以解决化学药品的储藏问题，电视频道分配问题以及考试安排问题等。重庆市是一座拥有三千多年历史并且举世闻名的历史文化名城,是

5、巴渝文化的发祥地。其坐落于长江与嘉陵江的交汇处，四面环山，并被美丽的江水所环抱。同时，重庆也是我国最大的直辖市。对于来这儿旅行的旅客或是刚来重庆上学的学生来说，如何在最短的时间内以及最经济的方式浏览“山城”美景，品尝“山城”著名的小吃、火锅是一个十分重要的问题。事实表明，充分利用好重庆的地铁交通系统可以在短时间内游遍重庆的知名景点和风景区，并且搭乘地铁可以大大缩短旅行时间。通过对于《图论及其应用》这门课程的学习后，我们可以将这个问题转化成为一个图论中的数学问题来看待，于是，就可以利用在图论中所学习和掌握的相关数学知识，对该问题进行抽象成图论中的最短路径问题以得

6、到很好的解决。图论中关于最短路径问题的解决主要是依靠Dijkstra算法，Floyd算法以及Warshell算法等算法。所需要乘坐或者换成的地铁站数即可看出是图中每条边的权重。本文研究的目的是为了通过图论知识找出可以浏览“山城”景点的最短旅游路径以及点着色问题。1图论在重庆地铁中的应用2.图论基本概念2.1图的定义图就是一个有序三元组G=<V(G)，E(G)，?(G)>，其中：（1）V(G)={v1，v2，?，vn}且V(G)≠?，则称V(G)为顶点集，其元素叫做图的顶点；（2）E(G)={e1，e2，?，en}，称为边集，其元素叫做图的边；（3）

7、?(G)；E→V×V是从边集E到顶点集V的有序或者无序对集合的影射，称为关联函数。2.2无向图和有向图如果图G中连接某两个不同顶点间的边是有方向的，则称该边为有向边。有向边用有序对<Vi,Vj>表示,其中Vi表示源点，Vj表示终点。如果图G中所有边都是有向边，则称图G为有向图。如果连接某两个不同顶点间的边是没有方向的，则称该边为无向边。无向边用无序对(Vi,Vj)表示。如果图G中的所有边都是无向边，则称图G为无向图。2.3关联和度关联指的是图中顶点与边之间的关系。设Vi和Vj是一条边的两个顶点，如果Vi≠Vj，则该边关联顶点一次；若Vi=Vj，即构

8、成了环，关联次数为2次。对于无向图中，