网络分析的的毕业论文

《网络分析的的毕业论文》由会员分享，可在线阅读，更多相关《网络分析的的毕业论文（50页珍藏版）》请在金锄头文库上搜索。

1、网络分析的的毕业论文第一章 绪论二十世纪中后期，随着计算机的出现和发展，图论的研究得到广泛重视，最短路径问题是图论中的一个典问题，它已经被应用于众多领域.最短路径问题最直接的应用当数在地理信息领域，如：GIS网络分析、城市规划、电子导航等.在交通咨询方面，寻找交通路网中两个城市间最短的行车路线就是最短路径问题的一个典型的例子.在网络通信领域，信息包传递的路径选择问题也与最短路径问题息息相关.举个例子，OPSF开放路由选择协议，每个OPSF路由器都维护一个描述自治系统拓扑结构的数据库，通过这个数据库构建最短路径树来计算路由表，从而跟踪自治系统围到每个目标的最短路径.在图象分割问题中，最短路径也有

2、直接的应用：在语音识别中，一个主要的问题就是区别同音词，例如，to、two、too.为解决这个问题，我们需要建一个图，顶点代表可能的单词，边连接相邻的单词，边上的权代表相邻的可能行大小.这样图中的最短路径，就是对句子的最好解释.由于最短路径问题的广泛应用，很多学者都对此进行了深入的研究，也产生了一些经典的算法.近些年来，对最短路径研究的热度依然不减，并且时间复杂度降得越来越低.所以在本课题中我们将提出不仅是以前我们学习过的一些经典的算法，我们还将提出一些以前没有学习过的更有应用空间的算法.以及各算法之间的比较.最后还将把这些算法在现实中的应用最一些简单的介绍.第二章 网络的最短路问题的基础知识

3、2.1 图的基本概念（1）图定义：一个（无向）图G 是一个有序二元组（V，E），其中是顶点集，是边集，且是一个无序二元组，它表示该边连接顶点与.图1就是一个图. 说明：在保持图的点边关系不变的情况下，图形的位置、大小、形状都是无关紧要的.若，则称连接与；点和称为的顶点，称或与关联，与是邻接的顶点；如果两条边有一个公共顶点，则称这两条边是邻接的；（2）环定义：两个顶点重合为一点的边称为环(如图图1中).V1V2V3V4V5图1（3）重边定义：如果有两条边的顶点是同一对顶点，则称这两条边为重边（如图1中与中有两条边相连）.（4）孤立点定义：不与任何边关联的点称为孤立点（如图1中）；（5）无环图定义

4、：没有环的图称为无环图；（6）简单图：定义：既没有环也没有重边的图称为简单图.设G=（V，E）是一个简单图，则显然有.（7）完全图定义：若上式中等号成立，则说明该图中每对顶点间恰有一条边相连，称此图为完全图.（8）补图定义：一个简单图的补图是与有相同顶点的简单图，且中两个点相邻当且仅当它们在中不相邻.（9）二分图定义：一个图G=（V，E），若存在V 的一个分划（，），使得每条边有一个顶点在中，另一个在中，则称为二分图.（10）子图、支撑子图定义：设有两个图，如果，则称为的支撑子图.（11）点导出子图定义：设有图G=（V，E），是的非空子集，若以为点集，以两点均在中的所有边为边集的子图称为由导出

5、的的子图，记为，简称点导出子图.（12）边导出子图定义：若是的一个非空子集，则以为边集以中边的所有顶点作为点集的子图，称为由导出的的子图，记为，简称边导出子图.（13）度：定义：图中顶点的度为与关联的边的数目（与关联的每个环算作两条边），记为.结论：设G=（V，E）是一个图，则，即度数为奇数的顶点有偶数个.2.2有向图（1）有向图定义：一个有向图是一个有序二元组，其中是顶点集，称为的弧集，为一个有序二元组.称为连向的弧，为的出弧，的入弧；称为得尾，称为的头；称为的前继，称为的后继.图2就是一个有向图.V1V2V3图2（2）环定义：头和尾重合的弧称为环.（3）重弧定义：若两条弧有相同的头和尾，则

6、称这两条弧为重弧.（4）简单有向图定义：没有环和重弧的有向图称为简单有向图（5）基图定义：把有向图中每条弧用边来代替，得到一个无向图，称为得基图.（6）完全有向图定义：设G=（V，E）是一个简单有向图，则，若等号成立，则称这样的图为完全有向图.（7）出度、入度定义：有向图中顶点的出弧的数目称为的出度，记为；顶点入弧的数目称为的入度，记为.结论：设G=（V，E）是一有向图，则 类似地可以定义有向图的子图，支撑子图，点，边导出之子图的概念.（8）网络定义：设是一个图，若对的每一条边都赋以一个实数，称为边的权，则连同边上的权称为一个网络，记为.同样可以定义有向网络.在此主要讨论网络上的各种优化问题.

7、无向网络可以转化为有向网络，具体做法为：把无向网络中每条边代之以一对弧（）和（），且两条弧的权都等于边的权.2.3连通性（1） 途径、迹、路定义：设有图 G=（V，E），如果它的某些顶点与边可以排成一个非空的有限交错序列，这里该途径中边互不相同，则称为迹；如果顶点互不相同，则称它为路.显然路必为迹，但反之未必.（2） 闭路径定义：如果某途径至少含一条边，且起点与终点重合，则称它为一条闭途径.类似可定义闭迹和回路（又称圈）.注意：若为简单图，则两个顶点间边若存在必是唯一的，故由到的一条途径可以用顶点序列表示.（3） 连通图：定义：图中若存在一条从顶点到的途径，则称与是连通的.如果图中任何两个顶点

8、都是连通的，则称是连通图.例如，完全图是连通的.二分图，则只要，中有一个大于1，则一定不是连通图.（4） 连通子图定义：如果是的子图，且是连通的，则称为的连通子图.（5） 极通子图定义：如果为的连通子图，且不存在连通子图，使是的子图.图的极通子图又称为的连通分支.（6） 有向途径定义：设有一个有向图，中某些顶点与弧组成的非空有限序列这里，且，则称它为从到的有向途径.类似可定义有向迹，有向路，有向闭途径，有向闭迹，有向回路（有向圈）.当是简单有向图时，从到的一条有向途径可简记为（）.（7） 强连通定义：中若既存在一条从顶点到的有向途径，又存在从到的有向途径，则称和是强连通的.如果中任意两顶点都是

9、强连通的，则称是强连通的.（8） 强连通分支定义：的极大强连通子图称为强连通分支.注：若强连通，则恰有一个强连通分支.结论：若为有个连通分支的简单无向图，则的邻接矩阵为准对角矩阵若为有个强连通分支的简单有向图，则的邻接矩阵为准上三角矩阵2.4割集（1） 割边定义：设有图，是的一条边，如果从中删去，使它的连通分支数量增加1，则称是的割边.显然，的一条边是割边当且仅当该边不包含在的任何闭迹中.（2） 边割定义：设是的一个非空子集，记，如果，且从中删去这些边后，的连通分支至少增加1，则称是的一个边割.（3） 割集定义：若是一个边割，且的任何真子集都不是边割，则称它为极小边割，的极小边割又称为割集.结

10、论：任给图，设是图的圈，是图的割集，用表示的边集.如果，那么.（4） 弧割定义：设是一个有向图，记，如果，则从中删去这些弧以后，的强连通分支数至少增加1，称它为的一个弧割.的极小弧割称为有向割集.2.5最短路问题定义：所谓最短路径是指如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条有向路径使得沿此路径上各弧的权值总和达到最小.第三章 网络的最短路问题的算法研究3.1最短路问题的提出某旅客要从乘飞机前往奥地利的萨尔斯堡，因为他害怕乘飞机，所以要选择一条航线，使得在空中飞行的时间尽可能的少.问题是如何选择航线以达到要求.为此构造一个无向网络总可以化成有向网络，

11、故下面只讨论有向网络的最短路问题.设是一有向网络，为中一条有向路，称为路的权或路长.现寻找网络中自某一指定顶点到另一指定顶点的最短有向路.3.2 Bellman最短路方程设有一个有向网络，.若用表示自顶点到顶点的最短有向路长，用表示弧（）的长度，若，则定义，则对一切有且当且仅当弧在自顶点到顶点的最短有向路上.因为所有均表示自到的最短路长，因此这些最短路必有最后一条弧（），且该有向路上自到的一段也是最短路，故有Bellman最短路方程：即自点到各点最短路长度必满足Bellman最短路方程.反过来，Bellman最短路方程的解是自点到其余各点最短路的长度.3.3无负回路网络的最短有向路的Ford算

12、法3.3.1 Ford算法的基本思想Ford算法的思想是逐次逼近，每次逼近求出网络从到其余各顶点的带某种约束的最短路，这里的约束是路中弧数.第一次逼近是从到其他任意顶点由一条弧组成的所有路中找一条最短路，记其长度为;第二次逼近是从到由不多于两条弧组成的所有路中找一条最短路，记其长度为.一般地，第次逼近是从到由不多于条弧组成的路中找一条最短的，记其长度为.因为中自到的最短路至多含个顶点， 条弧，所以最多次逼近即可. 即为中自到的最短路长.3.3.2 Ford算法的步骤为方便起见，定义.第一步 置，.第二步 令.第三步 若，停止;否则令，返回第二步.3.3.3实例 求如下图所示网络中从顶点到其余各

13、点的最短路.V3V2V6V1V5V4解 求解过程如下:因此从到的最短路径分别为，路长分别为1，2，-3，0，2.3.4求正权网络中有向最短路的Dijkstra算法3.4.1 Dijkstra算法的基本思想对网络中每个顶点赋以一个标号，用来记录从顶点到该顶点的最短路的长度（此时称为永久标号）或最短路长度的上界（此时称为暂时标号）.算法开始时，只有顶点被赋予永久标号，其它顶点被赋予暂时标号.一般地，算法在被暂时标号的顶点中寻找一个顶点，其暂时标号最小，然后将赋予永久标号，且对其余暂时标号的顶点按方式修正其标号.算法在所有顶点均被赋予永久标号终止.3.4.2 Dijkstra算法的理论依据（1） 对

14、于中任一顶点，其永久标号是从顶点到该顶点的最短路的长度.（2） 对于中任一顶点，其暂时标号是从顶点出发，只经过中顶点到达该顶点的最短路的长度.3.4.3 Dijkstra算法的算法步骤最短路径问题是指在一个赋权图的两个指定节点 和 之间找出一条具有最小权的路.Dijkstra 算法是一个解最短路径问题的算法，这个算法不仅可以找到最短的，路径而且可以给出从到图中所有节点的最短路径.其基本步骤如下:(1) 设，对所有的节点来说，设，并将标号为0， ，为和w之间的权值(距离).(2)按照每个未标号的节点w计算， ，表示点t 到点w 之间的权值(距离) .若被修改了说明在当前得到的 到w 的最优路径上t 和w 相邻用记录下来在所有 中选择一个最小的 即，未标号.将s 标号为， 表示节点到s的最优路径的长度为且 与s 相邻.(3) 若终点v 已标号，则停止.得到一条从到v 的最优路径，否则，转向(2)再计算.3.4.4 Dijkstra算法的应用举例G以具体实例说明Dijkstra 算法的具体应用.例1. 利用Dijkstra 算法求图1 中节点A 到其它各节点的最优路径.K 20 2.9 3.2D 18N 4.4 3.5 3.2 4.5B 16HE Y