图论期末论文

1.引言图论是数学的一个分支，并门是组合数学和应用数学的一部分。它以图做为研究对彖，而图是由若干 节点和节点Z间的边所构成的图型。在图论中，图往往是某个具体现实生活中问题的数学抽象，可以说， 图屮的节

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