网络规划设计理论基础

《网络规划设计理论基础》由会员分享，可在线阅读，更多相关《网络规划设计理论基础（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)相对应，则称v

3、i, vj是ek的端点，记为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

4、,e4,e6是相邻边。,图4.2 图G,4.1.1 图的概念,一个图可以用几何图形来表示，但一个图所对应的几何图形不是唯一的。 不难看出，图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都

5、对应一个无序节点对（vi, vj），（vi,vj）=（vj, vi）。如图4.3所示。,图4.3 无向图,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称为权值。对于电路图，若节点为电路中的点，边为元件，则节点的权值可以为电压和电阻，边的权值为电流。对于通信网而言，节点可代表交换局，权值可以为造价

6、或容量等，边代表链路，权值可以为长度，造价等，如图4.5所示。,图4.4 有向图,图4.5 有权图,4.1.1 图的概念,自环：若与一个边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(v

8、1)=4。,图4.6 自环示意图,4.1.1 图的概念,边序列：有限条边的一种串序排列称为边序列，边序列中的各条边是首尾相连的，如图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)：既无重复边，又无重复节点

9、的边序列叫做径。在径中，每条边和每个节点都只出现一次。如图4.7 中(e1,e2,e3)即为一条径。在一条径中，除了起点和终点的节点的度数为1外，其他节点的度数都是2。,图4.7 边序列,链和径是不一样的，链中可以有重复的节点，而径中不能出现重复的节点，链中各节点的度数不定，而径中各节点度数是有规律的。,4.1.1 图的概念,回路(circuit)：起点和终点重合的径称为回路（或称为圈），回路是每个节点度数均为2的连通图，如图4.7中（e2,e3,e4）是一回路。由定义可知，回路必为连通图。,图4.7 边序列,4.1.1 图的概念,连通图：设图G=（V,E），若图中任意两个节点之间至少存在一条

10、路径，则称图G为连通图，否则称G为非连通图。,3图的连通性,在图4.8中，（a）为一连通图，（b）为一非连通图。,图4.8 连通图与非连通图,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

11、是G的子图，写成G G；若V V，E E，则称G是G的真子图，写成G G ；若V=V，E E则称G是G的生成子图。 最大连通子图：若图G是图G的一个连通子图，但再加上一个属于原图G的任何一个其他元素，图G就失去了连通性，成为非连通图，则图G叫图G的最大连通子图。,4.1.1 图的概念,从子图的定义可以看出，每个图都是它自己的子图。从原来的图中适当地去掉一些边和节点后得到子图。如果子图中不包含原图的所有边就是原图的真子图，若包含原图的所有节点的子图就是原图的生成子图。如图4.10中，（b）是（a）的真子图，（c）是（a）的生成子图，也是真子图。,图4.10 图与子图,4.1 图论基础,4.1.1

12、 图的概念 4.1.2 图的矩阵表示,4.1.2 图的矩阵表示,图的最直接的表示方法是用几何图形，且这种方法已经被广泛地应用。 但这种表示在数值计算和分析时有很大缺点，因此需借助于矩阵表示。这些矩阵是与几何图形一一对应的，即由图形可以写出矩阵，由矩阵也能画出图形。这样画出的图形可以不一样，但在拓扑上是一致的，也就是满足图的抽象定义。用矩阵表示的最大优点是可以存入计算机，并进行所需的运算。,4.1.2 图的矩阵表示,由节点与节点之间的关系确定的矩阵称为邻接矩阵。它的行和列都与节点相对应，因此对于一个有n个节点，m条边的图G，其邻接矩阵是一个nn的方阵，方阵中的每一行和每一列都与相应的节点对应，记

13、作C(G)=cijnn。,1.邻接矩阵,4.1.2 图的矩阵表示,cij对于有向图： cij对于无向图：,4.1.2 图的矩阵表示,邻接矩阵C 有如下特点： （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 图

14、的矩阵表示,4.1.2 图的矩阵表示,解：图4.11(a)的邻接矩阵为,图4.11(b)的邻接矩阵为,4.1.2 图的矩阵表示,对于无向简单图，邻接矩阵是对称的，且对角线上的元素全为零。 对于有向简单图，即没有自环和同方向并行边的有向图，对角线元素也为零，但邻接矩阵不一定对称。,4.1.2 图的矩阵表示,设G为有权图，而且是具有n个节点的简单图，其权值矩阵为,2权值矩阵,4.1.2 图的矩阵表示,无向简单图的权值矩阵是对称的，对角线元素全为零。 有向简单图的权值矩阵不一定对称，但对角线元素也全为零。,4.1.2 图的矩阵表示,图4.12和图4.13的权值矩阵W(G1)和W(G2)分别为：,图4

15、.12 无向图G1,图4.13 有向图G2,第四章 网络规划设计理论基础,4.1 图论基础 4.2 树 4.3 路径选择算法 4.4 网络流量分配及其算法 4.5 通信网的可靠性,4.2 树,4.2.1 树的概念及性质 4.2.2 图的生成树及其求法 4.2.3 最小生成树算法,4.2.1 树的概念及性质,任何两节点间有且只有一条径的图称为树，树中的边称为树枝（branch）。若树枝的两个节点都至少与两条边关联，则称该树枝为树干；若树枝的一个节点仅与此边关联，则称该树枝为树尖，并称该节点为树叶。若指定树中的一个点为根，则称该树为有根树 。,1定义,4.2.1 树的概念及性质,图4.14所示为一

16、棵树，v1为树根，e1，e6等为树干，e7，e4，e11等为树尖，v6，v7，v8，v10等为树叶。,图4.14 树,4.2.1 树的概念及性质,树是无环的连通图，但增加一条边便可以得到一个环。任何两节点间有径的图一定是连通图，而只有一条径就不能有环。 树是最小连通图，即去掉树中的任何一条边就成为非连通图，丧失了连通性。 若树有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的生成树上的边组成树枝集。生成树之外的边称为连枝，连枝的边集称为连枝集或称为树补