最短路径问题网络分析毕业论文.docx

最短路径问题网络分析毕业论文.docx第一章绪论
二十世纪中后期，随着计算机的出现和发展，图论的研究得到广泛重视，最 短路径问题是图论中的一个典范问题， 最直接的应用当数在地理信息领域，女口： GIS网络分析、城市规划、电子导航等. 在交通咨询方面，寻找交通路网中两个城市间最短的行车路线就是最短路径问题 的一个典型的例子•在网络通信领域，信息包传递的路径选择问题也与最短路径 ，OPSF开放路由选择协议，每个OPSF路由器都维护一 个描述自治系统拓扑结构的数据库，通过这个数据库构建最短路径树来计算路由 表，，最短 路径也有直接的应用：在语音识别中，一个主要的问题就是区别同音词，例如， to、two、too•为解决这个问题，我们需要建一个图，顶点代表可能的单词，边连 接相邻的单词，边上的权代表相邻的可能行大小•这样图中的最短路径，就是对 句子的最好解释.
由于最短路径问题的广泛应用，很多学者都对此进行了深入的研究，也产生 ，对最短路径研究的热度依然不减，并且时间复杂 的算法， 之间的比较•最后还将把这些算法在现实中的应用最一些简单的介绍.
第二章网络的最短路问题的基础知识
1图的基本概念
（1） 图
定义：一个（无向）图G是一个有序二元组（V, E）,其中V = {Vl,v2,...,vn}是顶 点集，E = {e. }是边集，且切是一个无序二元组{vpv2},它表示该边连接顶点匕与 v厂图1就是一个图.
说明：在保持图的点边关系不变的情况下，图形的位置、大小、形状都是无关 紧要的.
若勺={v,,v;},则称etj连接V,.与Vj ；
点匕和Vy称为夠的顶点，称匕或片与夠关联，匕与片是邻接的顶点；
如果两条边有一个公共顶点，则称这两条边是邻接的；
（2） 环
定义：如果有两条边的顶点是同一对顶点，则称这两条边为重边（如图1中片与 叫中有两条边相连）.
孤立点
定义：不与任何边关联的点称为孤立点(如图1中》5)；
无环图
定义：没有环的图称为无环图；
简单图：
定义：既没有环也没有重边的图称为简单图.
设匸(V, E)是一个简单图，则显然有
1 1 2
完全图
定义：若上式中等号成立，则说明该图中每对顶点间恰有一条边相连，称此图为 完全图.
补图
定义：一个简单图的补图厂是与G有相同顶点的简单图，且厂中两个点相邻当 且仅当它们在G中不相邻.
C9)二分图
定义：一个图G= (V, E),若存在V的一个分划(％, %)，使G得每条边有一 个顶点在％中，另一个在％中，则称G为二分图.
CIO)子图、支撑子图
定义：设有两个图G：=(匕，耳)，心1,2,如果叫匸％，E^E2,则称G]为G?的 支撑子图.
点导出子图
定义：设有图G= (V, E), %是V的非空子集，若以％为点集，以两点均在％中
的所有边为边集的子图称为由％导出的G的子图，记为GM],简称点导出子图.
边导出子图
定义：若呂是E的一个非空子集，则以呂为边集以呂中边的所有顶点作为点集 的子图，称为由巴导出的G的子图，记为G[E}],简称边导出子图.
C13)度：
定义：图G中顶点v的度为与v关联的边的数目(与v关联的每个环算作两条边),
记为dG(v).
结论：设匸(V, E)是一个图，则£rfc(v) = 2|E|,即度数为奇数的顶点有偶数 vgV
个.

有向图
定义：一个有向图G是一个有序二元组(y,A),其中V = {V1,v2,...,vn］是顶点集，
A = {aij}称为G的弧集，陶为一个有序二元组.
称知为匕连向Vj的弧，陶为匕的出弧，Vj的入弧；匕称为勺得尾，Vj称为4了的
头；匕称为Vy的前继，1］.
环
定义：头和尾重合的弧称为环.
重弧
定义：若两条弧有相同的头和尾，则称这两条弧为重弧.
简单有向图
定义：没有环和重弧的有向图称为简单有向图'
基图
定义：把有向图G中每条弧(v；,v7)用边{VpVj来代替，得到一个无向图，称为G 得基图.
完全有向图
定义：设匸(V, E)是一个简单有向图，则|A|<|V|(|V|-1),若等号成立，则称 这样的图为完全有向图.
出度、入度
定义：有向图G中顶点v的出弧的数目称为v的出度，记为工4*0)；顶点v入 vgV
弧的数目称为V的入度，记为dc~(v).
结论：设匸(V, E)是一有向图，贝U