网络规划设计理论基础.ppt
《网络规划设计理论基础.ppt》由会员分享,可在线阅读,更多相关《网络规划设计理论基础.ppt(137页珍藏版)》请在三一办公上搜索。
1、第四章 网络规划设计理论基础,通信网的拓扑结构在通信网设计中是一个很重要的问题,它不但影响网的造价和维护费用,而且对网络的可靠性和网络的控制及规划起着重要的作用。传统的网都是转接式的,包括电路转接和信息转接,是由交换节点和传输线路构成。从数学模型来说这是一个图论的问题。在通信网的规划、设计和维护中,可靠性是一项重要的性能指标。,第四章 网络规划设计理论基础,4.1 图论基础 4.2 树4.3 路径选择算法4.4 网络流量分配及其算法4.5 通信网的可靠性,4.1 图论基础,4.1.1 图的概念4.1.2 图的矩阵表示,4.1.1 图的概念,图论是专门研究人们在自然界和社会生活中遇到的包含某种二
2、元关系的问题或系统。它把这种问题或系统抽象为点和线的集合,用点和线相互连接的图来表示,图4.1就是这样一个图,通常称为点线图。,图4.1 图的概念,图的概念,4.1.1 图的概念,设有节点集V=v1,v2,vn和边集E=e1,e2,em,当存在关系R,使VVE成立时,则说由节点集V和边集E组成图G,记为G=(V,E)。关系R可以说成对任一边ek,有V中的一个节点对(vi,vj)与之对应。图G中的V集可任意给定,而E集只是代表V中的二元关系。对viV,vjV,当且仅当vi对vj存在某种关系时(如邻接关系)才有某一个ek E。如果有一条边ek与节点对(vi,vj)相对应,则称vi,vj是ek的端点
3、,记为ek=(vi,vj),称点vi,vj与边ek关联,而称vi与vj为相邻节点。若有两条边与同一节点关联,则称这两条边为相邻边。,1.图的定义,4.1.1 图的概念,例4.1 图4.2中V=v1,v2,v3,v4 E=e1,e2,e3,e4,e5,e6其中e1=(v1,v2),e2=(v1,v3),e3=(v2,v4),e4=(v2,v3),e5=(v3,v4),e6=(v1,v4)。故可将图4.2记为G=(V,E)。图中v1与e1,e2,e6关联,v1与v2,v3,v4是相邻节点,e1与e2,e3,e4,e6是相邻边。,图4.2 图G,4.1.1 图的概念,一个图可以用几何图形来表示,但一
4、个图所对应的几何图形不是唯一的。不难看出,图4.2表示的图与图4.1表示的图是相同的图G,说明一个图只由它的节点集V、边集E和点与边的关系所确定,而与节点的位置和边的长度及形状无关。图4.1和图4.2只是一个图G的两种不同的几何表示方法。,4.1.1 图的概念,节点:表示物理实体,用vi表示。边:节点间的连线,表示两节点间存在连接关系,用eij表示。,2图的相关概念,无向图:设图G=(V,E),当vi对vj存在某种关系R等价于vj对vi存在某种关系R,则称G为无向图。即图G中的任意一条边ek都对应一个无序节点对(vi,vj),(vi,vj)=(vj,vi)。如图4.3所示。,图4.3 无向图,
5、4.1.1 图的概念,有向图:设图G=(V,E),当vi对vj存在关系R不等价于vj对vi存在关系R,则称G为有向图。即图G中的任意一条边都对应一个有序节点对(vi,vj),(vi,vj)(vj,vi)。如图4.4所示。有权图:设图G=(V,E),如果对它的每一条边ek或对它的每个节点vi赋以一个实数pk,则称图G为有权图或加权图,pk称为权值。对于电路图,若节点为电路中的点,边为元件,则节点的权值可以为电压和电阻,边的权值为电流。对于通信网而言,节点可代表交换局,权值可以为造价或容量等,边代表链路,权值可以为长度,造价等,如图4.5所示。,图4.4 有向图,图4.5 有权图,4.1.1 图的
6、概念,自环:若与一个边er相关联的两个节点是同一个节点,则称边er为自环。重边:在无向图中与同一对节点关联的两条或两条以上的边称为重边。在有向图中与同一对节点关联且方向相同的两条或两条以上的边称为重边。没有自环和重边的图称为简单图。如图4.6(a)中,与边e1所关联的两个节点是同一个节点,这种边就为自环;而与v2、v4相关联的边有两条,即e6和e7,这就是重边,重边的重数也可为3或更多。图4.6(b)中的e6和e7虽也同时与v2、v4相关联,但箭头方向不同,不能称为重边。在实际问题中,重边常可合并成一条边。对于一条无向边可画成两条方向相反的有向边,使有向图中没有无向边,也可将与同一对节点相关联
7、的两条有向边合并成一条无向边。,图4.6 自环示意图,4.1.1 图的概念,节点的度数:与某节点相关联的边数可定义为该节点的度数,记为d(vi)。如图4.6(a)中d(v2)=4,d(v3)=2,d(v1)=4。若为有向图,用d+(vi)表示离开或从节点vi射出的边数,即节点vi的出度,用d-(vi)表示进入或射入节点vi的边数即节点vi的入度,而节点vi的度数表示为d(vi)=d+(vi)+d-(vi)。如图4.6(b)中,d+(v1)=3,d-(v1)=1,d(v1)=4。,图4.6 自环示意图,4.1.1 图的概念,边序列:有限条边的一种串序排列称为边序列,边序列中的各条边是首尾相连的,
8、如图4.7中(e1,e2,e3,e4,e5,e6,e3)就是一个边序列。在边序列中,某条边是可以重复出现的,节点也是可以重复出现的。,图4.7 边序列,链(chain):没有重复边的边序列叫做链。在链中每条边只能出现一次。起点和终点不是同一节点的链叫开链。起点和终点重合的链叫闭链。通常所说的链指的是开链。链中边的数目称为链的长度。如图4.7中(e2,e3,e4)为闭链,而(e1,e2,e3,e6)为开链。,4.1.1 图的概念,径(path):既无重复边,又无重复节点的边序列叫做径。在径中,每条边和每个节点都只出现一次。如图4.7 中(e1,e2,e3)即为一条径。在一条径中,除了起点和终点的
9、节点的度数为1外,其他节点的度数都是2。,图4.7 边序列,链和径是不一样的,链中可以有重复的节点,而径中不能出现重复的节点,链中各节点的度数不定,而径中各节点度数是有规律的。,4.1.1 图的概念,回路(circuit):起点和终点重合的径称为回路(或称为圈),回路是每个节点度数均为2的连通图,如图4.7中(e2,e3,e4)是一回路。由定义可知,回路必为连通图。,图4.7 边序列,4.1.1 图的概念,连通图:设图G=(V,E),若图中任意两个节点之间至少存在一条路径,则称图G为连通图,否则称G为非连通图。,3图的连通性,在图4.8中,(a)为一连通图,(b)为一非连通图。,图4.8 连通
10、图与非连通图,4.1.1 图的概念,环路:回路间不重边的并称为环路。闭链和回路都是环路,但环路不一定是闭链和回路。闭链和回路是连通的,而环路不一定连通。,如图4.9中,(e1,e2,e6,e5,e4,e3)是环路,是回路(e1,e2,e3)与回路(e4,e5,e6)的不重边的并,它们有一个公共点v3,是连通的。环路中每个节点的度数均为偶数。,图4.9 环路,4.1.1 图的概念,子图、真子图和生成子图:设有图G=(V,E),G=(V,E)V V,E E,则称G是G的子图,写成G G;若V V,E E,则称G是G的真子图,写成G G;若V=V,E E则称G是G的生成子图。最大连通子图:若图G是图
11、G的一个连通子图,但再加上一个属于原图G的任何一个其他元素,图G就失去了连通性,成为非连通图,则图G叫图G的最大连通子图。,4.1.1 图的概念,从子图的定义可以看出,每个图都是它自己的子图。从原来的图中适当地去掉一些边和节点后得到子图。如果子图中不包含原图的所有边就是原图的真子图,若包含原图的所有节点的子图就是原图的生成子图。如图4.10中,(b)是(a)的真子图,(c)是(a)的生成子图,也是真子图。,图4.10 图与子图,4.1 图论基础,4.1.1 图的概念4.1.2 图的矩阵表示,4.1.2 图的矩阵表示,图的最直接的表示方法是用几何图形,且这种方法已经被广泛地应用。但这种表示在数值
12、计算和分析时有很大缺点,因此需借助于矩阵表示。这些矩阵是与几何图形一一对应的,即由图形可以写出矩阵,由矩阵也能画出图形。这样画出的图形可以不一样,但在拓扑上是一致的,也就是满足图的抽象定义。用矩阵表示的最大优点是可以存入计算机,并进行所需的运算。,4.1.2 图的矩阵表示,由节点与节点之间的关系确定的矩阵称为邻接矩阵。它的行和列都与节点相对应,因此对于一个有n个节点,m条边的图G,其邻接矩阵是一个nn的方阵,方阵中的每一行和每一列都与相应的节点对应,记作C(G)=cijnn。,1.邻接矩阵,4.1.2 图的矩阵表示,cij对于有向图:cij对于无向图:,4.1.2 图的矩阵表示,邻接矩阵C 有
13、如下特点:(1)当图中无自环时,C 阵的对角线上的元素都为 0。若有自环,则对角线上对应的相应元素为1。(2)有向图中,C 阵中的每行上1的个数为该行所对应的节点的射出度数d+(vi),每列上的1的个数则为该列所对应的节点的射入度数d-(vi);无向图中,每行或每列上1的个数则为该节点的总度数d(vi)。当某节点所对应的行和列均为零时说明该节点为孤立节点。,4.1.2 图的矩阵表示,例4.2 求图4.11(a),(b)的邻接矩阵。,图4.11 图的矩阵表示,4.1.2 图的矩阵表示,解:图4.11(a)的邻接矩阵为,图4.11(b)的邻接矩阵为,4.1.2 图的矩阵表示,对于无向简单图,邻接矩
14、阵是对称的,且对角线上的元素全为零。对于有向简单图,即没有自环和同方向并行边的有向图,对角线元素也为零,但邻接矩阵不一定对称。,4.1.2 图的矩阵表示,设G为有权图,而且是具有n个节点的简单图,其权值矩阵为,2权值矩阵,4.1.2 图的矩阵表示,无向简单图的权值矩阵是对称的,对角线元素全为零。有向简单图的权值矩阵不一定对称,但对角线元素也全为零。,4.1.2 图的矩阵表示,图4.12和图4.13的权值矩阵W(G1)和W(G2)分别为:,图4.12 无向图G1,图4.13 有向图G2,第四章 网络规划设计理论基础,4.1 图论基础 4.2 树4.3 路径选择算法4.4 网络流量分配及其算法4.
15、5 通信网的可靠性,4.2 树,4.2.1 树的概念及性质4.2.2 图的生成树及其求法4.2.3 最小生成树算法,4.2.1 树的概念及性质,任何两节点间有且只有一条径的图称为树,树中的边称为树枝(branch)。若树枝的两个节点都至少与两条边关联,则称该树枝为树干;若树枝的一个节点仅与此边关联,则称该树枝为树尖,并称该节点为树叶。若指定树中的一个点为根,则称该树为有根树。,1定义,4.2.1 树的概念及性质,图4.14所示为一棵树,v1为树根,e1,e6等为树干,e7,e4,e11等为树尖,v6,v7,v8,v10等为树叶。,图4.14 树,4.2.1 树的概念及性质,树是无环的连通图,但
16、增加一条边便可以得到一个环。任何两节点间有径的图一定是连通图,而只有一条径就不能有环。树是最小连通图,即去掉树中的任何一条边就成为非连通图,丧失了连通性。若树有m条边及n个节点,则有m=n-1,即有n个节点的树共有n-1个树枝。除了单点树外,任何一棵树中至少有两片树叶。,2性质,4.2 树,4.2.1 树的概念及性质4.2.2 图的生成树及其求法4.2.3 最小生成树算法,4.2.2 图的生成树及其求法,设G是一个连通图,T是G的一个子图且是一棵树,若T包含G的所有节点,则称T是G的一棵生成树,也称支撑树。只有连通图才有生成树;反之,有生成树的图必为连通图。图G的生成树上的边组成树枝集。生成树
17、之外的边称为连枝,连枝的边集称为连枝集或称为树补。如果在生成树上加一条连枝,便会形成一个回路。若图G本身不是树,则G的生成树不止一个,而连通图至少有一棵生成树。连通图G的生成树T的树枝数称为图G的阶。如果图G有n个节点,则它的阶是(G)=n-1。,1图的生成树,4.2.2 图的生成树及其求法,具有n个节点、m条边的连通图,生成树T有n-1条树枝和m-n+1条连枝。连枝集的连枝数称为图G的空度,记为,当G有m条边时,有(G)=|G-T|=m-n+1 显然有 m=+,4.2.2 图的生成树及其求法,图的阶表示生成树的大小,取决于G 中的节点数。图的空度表示生成树覆盖该图的程度,越小,覆盖度越高,=
18、0表示图G就是树。另一方面,空度也反映图G的连通程度,越大,连枝数越多,图的连通性越好,=0表示图G有最低连通性,即最小连通图。,4.2.2 图的生成树及其求法,破圈法:拆除图中的所有回路并使其保持连通,就能得到G的一棵生成树。避圈法:在有n个点的连通图G中任选一条边(及其节点);选取第二、三条边,使之不与已选的边形成回路;直到选取完n-1条边且不出现回路,结束。,2生成树的求法,4.2.2 图的生成树及其求法,例4.3 分别用破圈法和避圈法选择图4.15(a)的一棵树。,图4.15(a),解:破圈法:如图4.15所示,选择回路(v1,v3,v4),去掉e1;选择回路(v1,v2,v3),去掉
19、e3;选择回路(v2,v3,v5),去掉e6;最后选择回路(v3,v4,v6,v5),去掉e9依次得到图4.15(b)-(e),其中(e)为(a)的一棵生成树。避圈法:依次选取五条边e3,e4,e7,e9,e8,每一条边均不与已选边形成回路,见图4.16,最后得到G的又一棵生成树(e)。,4.2.2 图的生成树及其求法,图4.15 破圈法示意图,4.2.2 图的生成树及其求法,图4.16 避圈法示意图,4.2 树,4.2.1 树的概念及性质4.2.2 图的生成树及其求法4.2.3 最小生成树算法,4.2.3 最小生成树算法,最小生成树:如果连通图G本身不是一棵树,则它的生成树就不止一棵。如果为
20、图G加上权值,则各个生成树的树枝权值之和一般不相同,其中权值之和最小的那棵生成树为最小生成树。最小生成树一般是在两种情况下提出的,一种是有约束条件下的最小生成树,另一种是无约束条件下的最小生成树。,4.2.3 最小生成树算法,Kruskal算法将连通图G中的所有边按权值的非减次序排列;选取权值最小的边为树枝,再按的次序依次选取不与已选树枝形成回路的边为树枝。如有几条这样的边权值相同则任选其中一条;对于有n个点的图直到n-1条树枝选出,结束。这种算法的复杂性主要决定于把各边排列成有序的队列。,1无约束条件的情况,4.2.3 最小生成树算法,写出图G的权值矩阵;由点v1开始,在行1中找出最小元素w
21、1j;在行1和行j中,圈去列1和列j的元素,并在这两行余下的元素中找出最小元素,如wjk(如有两个均为最小元素可任选一个);在行1、行j和行k中,圈去列1、列j和列k的元素,并在这三行余下的元素中找出最小元素;直到矩阵中所有元素均被圈去,即找到图G的一棵最小生成树。,2.Prim算法,4.2.3 最小生成树算法,例4.4 要建设连接如图4.17所示的七个城镇的线路网,任意两个城镇间的距离见表4.1,请用P算法找出线路费用最小的网路结构图(设线路费用与线路长度成正比)。,表4.1 各城镇间的距离(km),图4.17 七个城市的地图,4.2.3 最小生成树算法,解:这个问题可抽象为用图论求最小生成
22、树的问题,首先列出权值矩阵,小元素为3,重复上述过程,依次找到7,8,8,将这些最小元素对应的边和节点全部画出就可得到一棵最小生成树,如图4.18所示。,在第一行中找出最小元素5,圈去第1行和第3行中第1列和第3列的元素,在这两行余下的元素中找到最小元素7,再圈去第1行、第3行和第4行中第1列、第3列和第4列的元素,从这3行余下的元素中找到最,4.2.3 最小生成树算法,所以,费用最小的网路结构网路总长度L为 L=3+5+7+7+8+8=38 km,图4.18 最小费用网络结构图,4.2.3 最小生成树算法,在设计通信网的网路结构时,经常会提出一些特殊的要求,如某交换中心或某段线路上的业务量不
23、能过大,任意两点间经过转接的次数不能过多等,这类问题可归结为求有约束条件的最小生成树的问题。关于有约束条件的最小生成树的求法目前并没有一般的有效算法,而且不同的约束条件,算法也将有区别。这里,我们只介绍一种常用的解决有约束条件的生成树的方法,即穷举法。穷举法就是先把图中的所有生成树穷举出来,再按条件筛选,最后选出最短的符合条件的生成树。显然这是一种最直观的也是最繁杂的方法,虽然可以得到最佳解,但计算量往往很大。,2有约束条件的最小生成树,第四章 网络规划设计理论基础,4.1 图论基础 4.2 树4.3 路径选择算法4.4 网络流量分配及其算法4.5 通信网的可靠性,4.3 路径选择算法,4.3
24、.1 狄克斯特拉(Dijkstra)算法4.3.2 Warshall-Floyd算法4.3.3 第K条最短路径选择问题,4.3.1 狄克斯特拉(Dijkstra)算法,已知图G=(V,E),将其节点集分为两组:置定节点集Gp和未置定节点集G-Gp。其中Gp内的所有置定节点,是指定点vs到这些节点的路径为最短(即已完成最短路径的计算)的节点。而G-Gp内的节点是未置定节点,即vs到未置定节点距离是暂时的,随着算法的下一步将进行不断调整,使其成为最短径。在调整各未置定节点的最短径时,是将Gp中的节点作为转接点。具体地说,就是将Gp中的节点作为转接点,计算(vs,vj)的径长(vjG-Gp),若该次
25、计算的径长小于上次的值,则更新径长,否则,径长不变。计算后取其中径长最短者,之后将vj划归到Gp中。当(G-Gp)最终成为空集,同时Gp=G,即求得vs到所有其他节点的最短路径。,1D算法原理,4.3.1 狄克斯特拉(Dijkstra)算法,:表示vs与其他节点的距离。在Gp中,wi表示上一次划分到Gp中的节点vi到vs的最短路径。在G-Gp中,表示从vs到vj 仅经过Gp中的节点作为转接点所求得的该次的最短路径的长度。如果vs与vj不直接相连,且无置定节点作为转接点,则令。,4.3.1 狄克斯特拉(Dijkstra)算法,图4.19 D算法流程图,2D算法实现流程,4.3.1 狄克斯特拉(D
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 网络 规划 设计 理论基础
链接地址:https://www.31ppt.com/p-6194584.html