通信网理论与应用-第4章.ppt

第四章 网络规划设计理论基础 通信网的拓扑结构在通信网设计中是一个很重要的问题，它不但影响网的造价和维护费用，而且对网络的可靠性和网络的控制及规划起着重要的作用。 传统的网都是转接式的，包括电路转接和信息转接，是由交换节点和传输线路构成。从数学模型来说这是一个图论的问题。 在通信网的规划、设计和维护中，可靠性是一项重要的性能指标。 第四章 网络规划设计理论基础 4.1 图论基础 4.2 树 4.3 路径选择算法 4.4 网络流量分配及其算法 4.5 通信网的可靠性 4.1 图论基础 4.1.1 图的概念 4.1.2 图的矩阵表示 4.1.1 图的概念 图论是专门研究人们在自然界和社会生活中遇到的包含某种二元关系的问题或系统。它把这种问题或系统抽象为点和线的集合，用点和线相互连接的图来表示，图4.1就是这样一个图，通常称为点线图。 4.1.1 图的概念 设有节点集V={v1,v2,…,vn}和边集E={e1,e2,…,em}，当存在关系R，使V×V→E成立时，则说由节点集V和边集E组成图G，记为G=（V,E）。 关系R可以说成对任一边ek，有V中的一个节点对(vi,vj)与之对应。 图G中的V集可任意给定，而E集只是代表V中的二元关系。对vi∈V ,vj∈V, 当且仅当vi对vj存在某种关系时（如邻接关系）才有某一个ek ∈E。如果有一条边ek与节点对(vi,vj)相对应，则称vi, vj是ek的端点，记为ek =(vi , vj)，称点vi , vj与边ek关联，而称vi与vj为相邻节点。若有两条边与同一节点关联，则称这两条边为相邻边。 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.1.1 图的概念 一个图可以用几何图形来表示，但一个图所对应的几何图形不是唯一的。 不难看出，图4.2表示的图与图4.1表示的图是相同的图G，说明一个图只由它的节点集V、边集E和点与边的关系所确定，而与节点的位置和边的长度及形状无关。 图4.1和图4.2只是一个图G的两种不同的几何表示方法。 4.1.1 图的概念 节点：表示物理实体，用vi表示。 边：节点间的连线，表示两节点间存在连接关系，用eij表示。 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.1.1 图的概念 自环：若与一个边er相关联的两个节点是同一个节点,则称边er为自环。 重边：在无向图中与同一对节点关联的两条或两条以上的边称为重边。在有向图中与同一对节点关联且方向相同的两条或两条以上的边称为重边。没有自环和重边的图称为简单图。 如图4.6（a）中，与边e1所关联的两个节点是同一个节点，这种边就为自环；而与v2、v4相关联的边有两条，即e6和e7，这就是重边，重边的重数也可为3或更多。图4.6(b)中的e6和e7虽也同时与v2、v4相关联，但箭头方向不同，不能称为重边。在实际问题中，重边常可合并成一条边。对于一条无向边可画成两条方向相反的有向边，使有向图中没有无向边，也可将与同一对节点相关联的两条有向边合并成一条无向边。 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。