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

第一章绪论
二十世纪中后期,随着计算机的出现和发展,图论的研究得到广泛重视,最短路径问题是图论中的一个典范问题,,如:GIS网络分析、城市规划、,,,OPSF开放路由选择协议,每个OPSF路由器都维护一个描述自治系统拓扑结构的数据库,通过这个数据库构建最短路径树来计算路由表,,最短路径也有直接的应用:在语音识别中,一个主要的问题就是区别同音词,例如,to、two、,我们需要建一个图,顶点代表可能的单词,边连接相邻的单词,,就是对句子的最好解释.
由于最短路径问题的广泛应用,很多学者都对此进行了深入的研究,,对最短路径研究的热度依然不减,,.
第二章网络的最短路问题的基础知识
图的基本概念
(1)图
定义:一个(无向)图G 是一个有序二元组(V,E),其中是顶点集,是边集,且是一个无序二元组,.
说明:在保持图的点边关系不变的情况下,图形的位置、大小、形状都是无关紧要的.
若,则称连接与;
点和称为的顶点,称或与关联,与是邻接的顶点;
如果两条边有一个公共顶点,则称这两条边是邻接的;
(2)环
定义:两个顶点重合为一点的边称为环(如图图1中).
V1
V2
V3
V4
V5
图1
(3)重边
定义:如果有两条边的顶点是同一对顶点,则称这两条边为重边(如图1中与中有两条边相连).
(4)孤立点
定义:不与任何边关联的点称为孤立点(如图1中);
(5)无环图
定义:没有环的图称为无环图;
(6)简单图:
定义:既没有环也没有重边的图称为简单图.
设G=(V,E)是一个简单图,则显然有.
(7)完全图
定义:若上式中等号成立,则说明该图中每对顶点间恰有一条边相连,称此图为完全图.
(8)补图
定义:一个简单图的补图是与有相同顶点的简单图,且中两个点相邻当且仅当它们在中不相邻.
(9)二分图
定义:一个图G=(V,E),若存在V 的一个分划(,),使得每条边有一个顶点在中,另一个在中,则称为二分图.
(10)子图、支撑子图
定义:设有两个图,,如果,,则称为的支撑子图.
(11)点导出子图
定义:设有图G=(V,E),是的非空子集,若以为点集,以两点均在中的所有边为边集的子图称为由导出的的子图,记为,简称点导出子图.
(12)边导出子图
定义:若是的一个非空子集,则以为边集以中边的所有顶点作为点集的子图,称为由导出的的子图,记为,简称边导出子图.
(13)度:
定义:图中顶点的度为与关联的边的数目(与关联的每个环算作两条边),记为.
结论:设G=(V,E)是一个图,则,即度数为奇数的顶点有偶数个.

(1)有向图
定义:一个有向图是一个有序二元组,其中是顶点集,称为的弧集,为一个有序二元组.
称为连向的弧,为的出弧,的入弧;称为得尾,称为的头;称为的前继,.
V1
V2
V3
图2
(2)环
定义:头和尾重合的弧称为环.
(3)重弧
定义:若两条弧有相同的头和尾,则称这两条弧为重弧.
(4)简单有向图
定义:没有环和重弧的有向图称为简单有向图‘
(5)基图
定义:把有向图中每条弧用边来代替,得到一个无向图,称为得基图.
(6)完全有向图
定义:设G=(V,E)是一个简单有向图,则,若等号成立,则称这样的图为完全有向图.
(7)出度、入度
定义:有向图中顶点的出弧的数目称为的出度,记为;顶点入弧的数目称为的入度,记为.
结论:设G=(V,E)是一有向图,则


类似地可以定义有向图的子图,支撑子图,点,边导出之子图的概念.
(8)网络
定义:设是一个图,若对的每一条边都赋以一个实数,称为边的权,则连同边上的权称为一个网络,记为.
.
无向网络可以转化为有向网络,具体做法为:把无向网络中每条边代之以一对弧()和(),且两条弧的权都等于边的权.

途