资源描述：
《图论期末论文》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、1.引言图论是数学的一个分支，并门是组合数学和应用数学的一部分。它以图做为研究对彖，而图是由若干节点和节点Z间的边所构成的图型。在图论中，图往往是某个具体现实生活中问题的数学抽象，可以说，图屮的节点代表着牛活屮的某些特定事物，而节点Z间的边则代衣着节点Z间的特定联系。图论这门学科需要解决的就是如何利用数学知识去解决它们之间的关系。图论最早起源于1736年著名的柯尼斯堡七桥问题山。这个问题的内容是：在柯尼斯堡的普莱格尔河上冇七座桥将河中的岛屿与河岸连接起來。问题是要从这四块陆地屮任何一块开始，通过
2、每一朋桥正好一次，最示再回到起始点。然而人们无数次的尝试解决却都没有成功。总到1736年，欧拉解决了这个问题。他用抽像分析法将这个问题化为世界上第一个图论问题：即把每一块陆地用一个点來代替，将每一座桥用联接相应的两个点的一条边來代替，从而得到了一个“图雹最终，欧拉成功证明了这个问题是无解的，并且推广了这个问题的意义，给出了对于一个给定的图可以某种方式走遍的判定法则。这就是后來的欧拉通路、欧拉回路以及欧拉图问题。于是，欧拉成为了图论学的创始人。从那以后开始的几百年间，图论开始了飞速的发展。虽然图论
3、研究的是点和边之间所构成图的问题，但其应用领域还是十分广阔的。图论的应用不仅仅局限于数学问题和计算机领域，它同时还涵盖了交通管理、通信领域、社会学筹诸多其他研究领域。而最短路径问题是图论应用中的基木问题。最短路径顾名思义就是在所有的路径中找出一条距离最短的有效路径。实际上，这里所指的“距离”不仅仅是指地理意义上的距离，还可以引申到时间、费用、等其他度量单位上面。本文中，以重庆地铁为研究对彖，利用图论知识解决在搭乘重庆地铁时的最短路径问题。可以说，最短路径问题再交通网络结构的分析以及交通路线的选择
4、中都冇重要的应用价值。此外，最短路径问题一直是计算机科学、地理信息学、交通管理学等学科小一个研究的热点问题。图的着色是指对图的每个节点指定一种颜色，使得相邻的节点的颜色不相同。着色问题在实际屮有很多的应用，比如可以解决化学药品的储藏问题，电视频道分配问题以及考试安排问题等。重庆市是一座拥有三千多年历史并且举世闻名的历史文化名城，是巴渝文化的发祥地。其坐落于长江与嘉陵江的交汇处，四而环山，并被美丽的江水所环抱。同吋，重庆也是我国最大的直辖市。对于来这儿旅行的旅客或是刚來重庆上学的学住來说，如何在最
5、短的时问内以及最经济的方式浏览“山城”美景，品尝“山城”苦名的小吃、火锅是一个十分重要的问题。事实表明，充分利用好重庆的地铁交通系统可以在短时间内游遍重庆的知名景点和风景区，并R搭乘地铁可以大大缩短旅行时间。通过对于《图论及其应川》这门课程的学习后，我们对以将这个问题转化成为一个图论中的数学问题来看待，于是，就对以利用在图论中所学习和学握的相关数学知识，对该问题进行抽象成图论中的最短路径问题以得到很好的解决。图论中关丁最短路径问题的解决主要是依靠Dijkstra算法，Floyd算法以及Warsh
6、ell算法等算法。所需耍乘处或者换成的地铁站数即可看出是图屮每条边的权重。木文研究的目的是为了通过图论知识找出可以浏览“山城”景点的最短旅游路径以及点着色问题。2.图论基本概念2.1图的定义图就是一个有序三元组G=＜V(G),E(G),cp(G)＞,其中：(1)V(G)={v1,v2,…，vn}且V(G)H0,则称V(G)为顶点集,其元素叫做图的顶点;(2)E(G)={el,e2,…，en},称为边集,其元素叫做图的边；(3)0(G)；E-VxV是从边集E到顶点集V的有序或者无序对集合的影射，称
7、为关联函数。2.2无向图和有向图如果图G中连接某两个不同顶点间的边是有方向的，则称该边为有向边。有向边用有序对＜Vi,Vj＞表示，其小Vi表示源点，Vj表示终点。如果图G中所有边都是有向边，则称图G为有向图。如果连接某两个不同顶点间的边是没有方向的，则称该边为无向边。无向边用无序对(Vi,Vj)表示。如果图G中的所有边都是无向边，则称图G为无向图。2.3关联和度关联指的是图中顶点与边之间的关系。设Vi和Vj是一条边的两个顶点，如果ViHVj,则该边关联顶点一次；若Vi=Vj,即构成了环，关联次数
8、为2次。对于无向图中，与顶点Vi相关联的边的个数称为顶点Vi的度。对于冇向图中，存在入度和出度两个概念。入度是指冇向图中以顶点Vi为终点的边的数冃。出度是指有向图中以顶点Vi为源点的边的数冃。2.4路径在无向图GvV,E＞屮,从顶点Vi到Vj的一条路径是一个顶点序列：(Vi,Vl,V2„„Vn,Vj),则称这个序列为从顶点iV到Vj的一•条路径。如果是有向图，则路径也是有向的，路径的长度是指路径上的边或弧的数目。如果序列中第一个顶点和最后一个顶点相同的路径称为回路或环。如果序列中顶点不重复岀现的
