网络规划设计理论基础.ppt

《网络规划设计理论基础.ppt》由会员分享，可在线阅读，更多相关《网络规划设计理论基础.ppt（137页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第四章第四章 网络规划设计理论基础网络规划设计理论基础通信网的通信网的拓扑结构拓扑结构在通信网设计中是一个很重要在通信网设计中是一个很重要的问题，它不但影响网的的问题，它不但影响网的造价造价和和维护费用维护费用，而且，而且对网络的对网络的可靠性可靠性和网络的和网络的控制及规划控制及规划起着重要的起着重要的作用。作用。传统的网都是转接式的，包括电路转接和信息转传统的网都是转接式的，包括电路转接和信息转接，是由接，是由交换节点交换节点和和传输线路传输线路构成。从数学模型构成。从数学模型来说这是一个来说这是一个图论图论的问题。的问题。在通信网的规划、设计和维护中，在通信网的规划、设计和维护中，可靠性

2、可靠性是一项是一项重要的性能指标。重要的性能指标。第四章 网络规划设计理论基础4.1 图论基础图论基础 4.2 树树4.3 路径选择算法路径选择算法4.4 网络流量分配及其算法网络流量分配及其算法4.5 通信网的可靠性通信网的可靠性4.1 图论基础4.1.1 图的概念图的概念4.1.2 图的矩阵表示图的矩阵表示4.1.1 图的概念 图论图论是专门研究人们在是专门研究人们在自然界和社会生活中遇自然界和社会生活中遇到的包含某种二元关系到的包含某种二元关系的问题或系统。它的问题或系统。它把这把这种问题或系统抽象为点种问题或系统抽象为点和线的集合，用点和线和线的集合，用点和线相互连接的图来表示相互连接

3、的图来表示，图图4.1就是这样一个图，就是这样一个图，通常称为通常称为点线图点线图。图图4.1 4.1 图的概念图的概念v图的概念图的概念4.1.1 图的概念设有节点集设有节点集V V=v v1 1,v v2 2,v vn n 和边集和边集E E=e e1 1,e e2 2,e em m，当存，当存在关系在关系R R，使，使V VV VE E成立时，则说成立时，则说由节点集由节点集V V和边集和边集E E组成组成图图G G，记为，记为G G=（V V,E E）。）。关系关系R R可以说成对任一边可以说成对任一边e ek k，有，有V V中的一个节点对中的一个节点对(v vi i,v vj j)

4、与与之对应。之对应。图图G G中的中的V V集可任意给定，而集可任意给定，而E E集只是代表集只是代表V V中的中的二元关系。对二元关系。对v vi iV V,v vj jV V,当且仅当当且仅当v vi i对对v vj j存在某种关存在某种关系时（如邻接关系）才有某一个系时（如邻接关系）才有某一个e ek k E E。如果有一条边。如果有一条边e ek k与节点对与节点对(v vi i,v vj j)相对应，则称相对应，则称v vi i,v vj j是是ekek的的端点端点，记为，记为e ek k =(v vi i,v vj j)，称点，称点v vi i,v vj j与边与边e ek k关联

5、关联，而称，而称v vi i与与v vj j为为相邻节相邻节点点。若有两条边与同一节点关联，则称这两条边为。若有两条边与同一节点关联，则称这两条边为相邻边相邻边。1.1.图的定义图的定义4.1.1 图的概念例例4.14.1 图图4.24.2中中V V=v v1,1,v v2,2,v v3,3,v v4 4 E E=e e1,1,e e2,2,e e3,3,e e4,4,e e5,5,e e66其中其中e e1=(1=(v v1,1,v v2),2),e e2=(2=(v v1,1,v v3),3),e3=(e3=(v v2,2,v v4)4)，e e4=(4=(v v2,2,v v3),3),

6、e e5=(5=(v v3,3,v v4),4),e e6=(6=(v v1,1,v v4)4)。故可将图故可将图4.24.2记为记为G G=(=(V V,E E)。图中图中v v1 1与与e e1,1,e e2,2,e e6 6关联关联,v v1 1与与v v2,2,v v3,3,v v4 4是是相邻节点相邻节点,e e1 1与与e e2,2,e e3,3,e e4,4,e e6 6是相邻边是相邻边。图图4.2 4.2 图图G G4.1.1 图的概念一个图可以用几何图形来表示，但一个图所对应的几何一个图可以用几何图形来表示，但一个图所对应的几何图形不是唯一的。图形不是唯一的。不难看出，图不难

7、看出，图4.24.2表示的图与图表示的图与图4.14.1表示的图是相同的图表示的图是相同的图G G，说明，说明一个图只由它的节点集一个图只由它的节点集V V、边集、边集E E和点与边的关系和点与边的关系所确定，而与节点的位置和边的长度及形状无关所确定，而与节点的位置和边的长度及形状无关。图图4.14.1和图和图4.24.2只是一个图只是一个图G G的两种不同的几何表示方法。的两种不同的几何表示方法。4.1.1 图的概念节点：节点：表示物理实体，用表示物理实体，用v vi i表示。表示。边：边：节点间的连线，表示两节点间存在连接关系，用节点间的连线，表示两节点间存在连接关系，用e eijij表示

8、。表示。2 2图的相关概念图的相关概念无向图：无向图：设图设图G G=(=(V V,E E)，当，当v vi i对对v vj j存在某种关系存在某种关系R R等价于等价于v vj j对对v vi i存在某种关系存在某种关系R R，则称，则称G G为无向图。即图为无向图。即图G G中的任意中的任意一条边一条边e ek k都对应一个无序节都对应一个无序节点对（点对（v vi i,v vj j），（），（v vi i,v vj j）=（v vj j,v vi i）。如图）。如图4.34.3所示。所示。图图4.3 4.3 无向图无向图 4.1.1 图的概念有向图：有向图：设图设图G G=(=(V V,

9、E E)，当，当vivi对对vjvj存存在关系在关系R R不等价于不等价于vjvj对对vivi存在关系存在关系R R,则称则称G G为为有向图有向图。即图。即图G G中的任意一条中的任意一条边都对应一个有序节点对（边都对应一个有序节点对（vivi,vjvj），），（vivi，vjvj）（vjvj，vivi）。如图）。如图4.44.4所所示。示。有权图：有权图：设图设图G G=(=(V V,E E)，如果对它的，如果对它的每一条边每一条边ekek或对它的每个节点或对它的每个节点vivi赋以赋以一个实数一个实数pkpk，则称图，则称图G G为为有权图有权图或或加权加权图图，pkpk称为称为权值权值

10、。对于。对于电路图电路图，若节，若节点为电路中的点，边为元件，则节点点为电路中的点，边为元件，则节点的权值可以为电压和电阻，边的权值的权值可以为电压和电阻，边的权值为电流。对于为电流。对于通信网通信网而言，节点可代而言，节点可代表交换局，权值可以为造价或容量等，表交换局，权值可以为造价或容量等，边代表链路，权值可以为长度，造价边代表链路，权值可以为长度，造价等，如图等，如图4.54.5所示。所示。图图4.4 4.4 有向图有向图 图图4.5 4.5 有权图有权图4.1.1 图的概念自环：自环：若与一个边若与一个边erer相关联的两个节点是同一个节点相关联的两个节点是同一个节点,则称边则称边er

11、er为为自环自环。重边：重边：在在无向图无向图中与同一对节点关联的两条或两条以上的边称中与同一对节点关联的两条或两条以上的边称为为重边重边。在。在有向图有向图中与同一对节点关联且方向相同的两条或中与同一对节点关联且方向相同的两条或两条以上的边称为两条以上的边称为重边重边。没有自环和重边的图称为。没有自环和重边的图称为简单图简单图。如图如图4.64.6（a a）中，与边）中，与边e e1 1所关联的两个节点是同一个节点，这所关联的两个节点是同一个节点，这种边就为种边就为自环自环；而与；而与v v2 2、v v4 4相关联的边有两条，即相关联的边有两条，即e e6 6和和e e7 7，这就是这就是

12、重边重边，重边的重数也可为，重边的重数也可为3 3或更多。图或更多。图4.6(b)4.6(b)中的中的e e6 6和和e e7 7虽也同时与虽也同时与v v2 2、v v4 4相关联，但箭头方向不同，不能称为重相关联，但箭头方向不同，不能称为重边。在实际问题中，重边常可合并成一条边。边。在实际问题中，重边常可合并成一条边。对于一条无向对于一条无向边可画成两条方向相反的有向边，使有向图中没有无向边，边可画成两条方向相反的有向边，使有向图中没有无向边，也可将与同一对节点相关联的两条有向边合并成一条无向边也可将与同一对节点相关联的两条有向边合并成一条无向边。图图4.6 4.6 自环示意图自环示意图

13、4.1.1 图的概念节点的度数：节点的度数：与某节点相关联的边数可定义与某节点相关联的边数可定义为该节点的为该节点的度数度数，记为记为d d(v vi)。如图。如图4.6(a)4.6(a)中中d d(v v2 2)=4,)=4,d d(v v3 3)=2,)=2,d d(v v1 1)=4)=4。若为有向图，用。若为有向图，用d d+(v vi i)表示离开或从节点表示离开或从节点v vi i射出的边数射出的边数,即节点即节点v vi i的的出度出度，用，用d d-(v vi i)表示进入或射入节点表示进入或射入节点v vi i的的边数即节点边数即节点v vi i的的入度入度，而节点，而节点v

14、 vi i的度数表示为的度数表示为d d(v vi i)=)=d d+(v vi i)+)+d d-(v vi i)。如图。如图4.6(b)4.6(b)中，中，d d+(v v1 1)=3,)=3,d d-(v v1 1)=1,)=1,d d(v v1 1)=4)=4。图图4.6 4.6 自环示意图自环示意图 4.1.1 图的概念边序列：边序列：有限条边的一种串序排列称为边序列，边序列中有限条边的一种串序排列称为边序列，边序列中的各条边是首尾相连的，如图的各条边是首尾相连的，如图4.74.7中中（e e1,1,e e2,2,e e3,3,e e4,4,e e5,5,e e6,6,e e3 3）

15、就是一个边序列。）就是一个边序列。在边序列中，在边序列中，某条边是可以重复出现的，节点也是可以重复出现的某条边是可以重复出现的，节点也是可以重复出现的。图图4.7 4.7 边序列边序列链链(chain)(chain)：没有重复边的边序没有重复边的边序列叫做链。在链中每条边只能出列叫做链。在链中每条边只能出现一次。起点和终点不是同一节现一次。起点和终点不是同一节点的链叫点的链叫开链开链。起点和终点重合。起点和终点重合的链叫的链叫闭链闭链。通常所说的链指的通常所说的链指的是开链是开链。链中边的数目称为链的。链中边的数目称为链的长度。如图长度。如图4.74.7中（中（e2,e3,e4e2,e3,e4

16、）为闭链，而（为闭链，而（e1,e2,e3,e6e1,e2,e3,e6）为）为开链。开链。4.1.1 图的概念径径(path)(path)：既无重复边，又无既无重复边，又无重复节点的边序列叫做径。重复节点的边序列叫做径。在在径中，每条边和每个节点都只径中，每条边和每个节点都只出现一次出现一次。如图。如图4.7 4.7 中中(e e1,1,e e2,2,e e3)3)即为一条径。即为一条径。在一在一条径中，除了起点和终点的节条径中，除了起点和终点的节点的度数为点的度数为1 1外，其他节点的度外，其他节点的度数都是数都是2 2。图图4.7 4.7 边序列边序列v链和径是不一样的，链和径是不一样的，

17、链中可以有重复的节点，而径中不能链中可以有重复的节点，而径中不能出现重复的节点，链中各节点的度数不定，而径中各节点出现重复的节点，链中各节点的度数不定，而径中各节点度数是有规律的度数是有规律的。4.1.1 图的概念回路回路(circuit)(circuit)：起点起点和终点重合的径称为回和终点重合的径称为回路（或称为圈），路（或称为圈），回路回路是每个节点度数均为是每个节点度数均为2 2的连通图的连通图，如图，如图4.74.7中中（e e2,2,e e3,3,e e4 4）是一回路。）是一回路。由定义可知，由定义可知，回路必为回路必为连通图连通图。图图4.7 4.7 边序列边序列4.1.1 图

18、的概念连通图：连通图：设图设图G G=（V V,E E），若图中任意两个节点之间至少），若图中任意两个节点之间至少存在一条路径，则称图存在一条路径，则称图G G为连通图，否则称为连通图，否则称G G为非连通图。为非连通图。3 3图的连通性图的连通性 在图在图4.84.8中，（中，（a a）为一连通图，（）为一连通图，（b b）为一非连通图。）为一非连通图。图图4.8 4.8 连通图与非连通图连通图与非连通图4.1.1 图的概念环路：环路：回路间不重边的并称为环路。回路间不重边的并称为环路。闭链和回路都是环路，闭链和回路都是环路，但环路不一定是闭链和回路。闭链和回路是连通的，而环但环路不一定是闭

19、链和回路。闭链和回路是连通的，而环路不一定连通路不一定连通 。如图如图4.94.9中，（中，（e e1 1,e e2 2,e e6 6,e e5 5,e e4 4,e e3 3）是环路，是回路（）是环路，是回路（e e1 1,e e2 2,e e3 3）与回路）与回路(e e4 4,e e5 5,e e6 6)的不重边的并，它们有一个公共点的不重边的并，它们有一个公共点v v3 3，是连通的。，是连通的。环路中每个节点的度数均为偶数。环路中每个节点的度数均为偶数。图图4.9 4.9 环路环路4.1.1 图的概念子图、真子图和生成子图子图、真子图和生成子图：设有图设有图G G=（V V,E E）

20、，），GG=(=(VV,EE)V VV V，E E E E，则称，则称GG是是G G的的子图子图，写成，写成G GG G；若；若V VV V，E EE E，则称，则称GG是是G G的的真子图真子图，写成，写成G GG G ；若若VV=V V，E EE E则称则称GG是是G G的的生成子图生成子图。最大连通子图：最大连通子图：若图若图GG是图是图G G的一个连通子图，的一个连通子图，但再加上一个属于原图但再加上一个属于原图G G的任何一个其他元素，图的任何一个其他元素，图GG就失去了连通性，成为非连通图，则图就失去了连通性，成为非连通图，则图GG叫叫图图G G的最大连通子图。的最大连通子图。4.

21、1.1 图的概念从子图的定义可以看出，从子图的定义可以看出，每个图都是它自己的子图每个图都是它自己的子图。从原来。从原来的图中适当地去掉一些边和节点后得到子图。的图中适当地去掉一些边和节点后得到子图。如果子图中不如果子图中不包含原图的所有边就是原图的真子图，若包含原图的所有节包含原图的所有边就是原图的真子图，若包含原图的所有节点的子图就是原图的生成子图点的子图就是原图的生成子图。如图。如图4.104.10中，（中，（b b）是（）是（a a）的真子图，（的真子图，（c c）是（）是（a a）的生成子图，也是真子图。）的生成子图，也是真子图。图图4.10 4.10 图与子图图与子图4.1 图论基

22、础4.1.1 图的概念图的概念4.1.2 图的矩阵表示图的矩阵表示4.1.2 图的矩阵表示图的最直接的表示方法是用几何图形，且这种方图的最直接的表示方法是用几何图形，且这种方法已经被广泛地应用。法已经被广泛地应用。但这种表示在数值计算和分析时有很大缺点，因但这种表示在数值计算和分析时有很大缺点，因此需借助于此需借助于矩阵矩阵表示。这些矩阵是与几何图形一表示。这些矩阵是与几何图形一一对应的，即一对应的，即由图形可以写出矩阵，由矩阵也能由图形可以写出矩阵，由矩阵也能画出图形画出图形。这样画出的图形可以不一样，但在拓。这样画出的图形可以不一样，但在拓扑上是一致的，也就是满足图的抽象定义。扑上是一致的

23、，也就是满足图的抽象定义。用矩用矩阵表示的最大优点是可以存入计算机，并进行所阵表示的最大优点是可以存入计算机，并进行所需的运算需的运算。4.1.2 图的矩阵表示由节点与节点之间的关系确定的矩阵称为由节点与节点之间的关系确定的矩阵称为邻接矩阵邻接矩阵。它的。它的行和列都与节点相对应，因此行和列都与节点相对应，因此对于一个有对于一个有n n个节点，个节点，m m条边条边的图的图G G，其邻接矩阵是一个，其邻接矩阵是一个n nn n的方阵，方阵中的每一行的方阵，方阵中的每一行和每一列都与相应的节点对应和每一列都与相应的节点对应，记作，记作C C(G G)=)=c cijij nnnn。1.1.邻接矩

24、阵邻接矩阵4.1.2 图的矩阵表示cij对于对于有向图有向图：cij对于对于无向图无向图：4.1.2 图的矩阵表示邻接矩阵邻接矩阵C C 有如下特点：有如下特点：（1 1）当图中）当图中无自环时无自环时，C C 阵的对角线上的元素都为阵的对角线上的元素都为 0 0。若有自环若有自环，则对角线上对应的相应元素为，则对角线上对应的相应元素为1 1。（2 2）有向图中有向图中，C C 阵中的每行上阵中的每行上1 1的个数为该行所的个数为该行所对应的节点的射出度数对应的节点的射出度数d d+(v vi i)，每列上的，每列上的1 1的个数的个数则为该列所对应的节点的射入度数则为该列所对应的节点的射入度

25、数d d-(v vi i)；无向图无向图中中，每行或每列上，每行或每列上1 1的个数则为该节点的总度数的个数则为该节点的总度数d d(v vi i)。当某节点所对应的行和列均为零时说明该。当某节点所对应的行和列均为零时说明该节点为孤立节点。节点为孤立节点。4.1.2 图的矩阵表示例例4.2 求图4.11（a），（b）的邻接矩阵。图图4.11 4.11 图的矩阵表示图的矩阵表示4.1.2 图的矩阵表示解解：图图4.11(a)4.11(a)的邻接矩阵为的邻接矩阵为 图图4.11(b)4.11(b)的邻接矩阵为的邻接矩阵为4.1.2 图的矩阵表示对于无向简单图，对于无向简单图，邻接矩阵是对称的，且对

26、邻接矩阵是对称的，且对角线上的元素全为零角线上的元素全为零。对于有向简单图，即没有自环和同方向并行对于有向简单图，即没有自环和同方向并行边的有向图，边的有向图，对角线元素也为零，但邻接对角线元素也为零，但邻接矩阵不一定对称矩阵不一定对称。4.1.2 图的矩阵表示设设G G为有权图，而且是具有为有权图，而且是具有n n个节点的简单图，其权值矩个节点的简单图，其权值矩阵为阵为2 2权值矩阵权值矩阵4.1.2 图的矩阵表示无向简单图的权值矩阵是对称的，对角线元无向简单图的权值矩阵是对称的，对角线元素全为零素全为零。有向简单图的权值矩阵不一定对称，但对角有向简单图的权值矩阵不一定对称，但对角线元素也全

27、为零线元素也全为零。4.1.2 图的矩阵表示图4.12和图4.13的权值矩阵W(G1)和W(G2)分别为：图图4.12 4.12 无向图无向图G1G1 图图4.13 4.13 有向图有向图G2G2 第四章 网络规划设计理论基础4.1 4.1 图论基础图论基础 4.2 4.2 树树4.3 4.3 路径选择算法路径选择算法4.4 4.4 网络流量分配及其算法网络流量分配及其算法4.5 4.5 通信网的可靠性通信网的可靠性4.2 树4.2.1 4.2.1 树的概念及性质树的概念及性质4.2.2 4.2.2 图的生成树及其求法图的生成树及其求法4.2.3 4.2.3 最小生成树算法最小生成树算法 4.

28、2.1 树的概念及性质任何两节点间有且只有一条径的图称为任何两节点间有且只有一条径的图称为树树，树中的边称为树中的边称为树枝树枝（branchbranch）。若树枝的）。若树枝的两个节点都至少与两条边关联，则称该树两个节点都至少与两条边关联，则称该树枝为枝为树干树干；若树枝的一个节点仅与此边关；若树枝的一个节点仅与此边关联，则称该树枝为联，则称该树枝为树尖树尖，并称该节点为，并称该节点为树树叶叶。若指定树中的一个点为。若指定树中的一个点为根根，则称该树，则称该树为为有根树有根树 。1 1定义定义4.2.1 树的概念及性质图图4.144.14所示为一棵所示为一棵树树，v v1 1为为树根树根，e

29、 e1 1，e e6 6等等为为树干树干，e e7 7，e e4 4，e e1111等为等为树尖树尖，v v6 6，v v7 7，v v8 8，v v1010等为等为树叶树叶。图4.14 树4.2.1 树的概念及性质树是无环的连通图，但增加一条边便可以得到一树是无环的连通图，但增加一条边便可以得到一个环个环。任何两节点间有径的图一定是连通图，而。任何两节点间有径的图一定是连通图，而只有一条径就不能有环。只有一条径就不能有环。树是最小连通图树是最小连通图，即去掉树中的任何一条边就成，即去掉树中的任何一条边就成为非连通图，丧失了连通性。为非连通图，丧失了连通性。若树有若树有m m条边及条边及n n

30、个节点，则有个节点，则有m m=n n-1-1，即有，即有n n个节个节点的树共有点的树共有n n-1-1个树枝。个树枝。除了单点树外，任何一棵树中至少有两片树叶除了单点树外，任何一棵树中至少有两片树叶。2 2性质性质4.2 树4.2.1 4.2.1 树的概念及性质树的概念及性质4.2.2 4.2.2 图的生成树及其求法图的生成树及其求法4.2.3 4.2.3 最小生成树算法最小生成树算法 4.2.2 图的生成树及其求法设设G G是一个连通图，是一个连通图，T T是是G G的一个子图且是一棵树，的一个子图且是一棵树，若若T T包含包含G G的所有节点，则称的所有节点，则称T T是是G G的一棵

31、的一棵生成树生成树，也，也称称支撑树支撑树。只有连通图才有生成树；反之，有生成树的图必为连通图只有连通图才有生成树；反之，有生成树的图必为连通图。图图G G的生成树上的边组成的生成树上的边组成树枝集树枝集。生成树之外的边称为。生成树之外的边称为连枝连枝，连枝的边集称为连枝的边集称为连枝集连枝集或称为或称为树补树补。如果在生成树上加一如果在生成树上加一条连枝，便会形成一个回路。若图条连枝，便会形成一个回路。若图G G本身不是树，则本身不是树，则G G的生的生成树不止一个，而连通图至少有一棵生成树成树不止一个，而连通图至少有一棵生成树。连通图连通图G G的生成树的生成树T T的树枝数称为图的树枝数

32、称为图G G的的阶阶。如果图。如果图G G有有n n个节个节点，则它的阶点，则它的阶是是(G G)=)=n n-1-1。1 1图的生成树图的生成树4.2.2 图的生成树及其求法具有具有n n个节点、个节点、m m条边的连通图，生成树条边的连通图，生成树T T有有n n-1-1条条树枝和树枝和m-nm-n+1+1条连枝。条连枝。连枝集的连枝数称为图连枝集的连枝数称为图G G的的空度空度，记为，记为，当，当G G有有m m条边时，有条边时，有 (G)=|G-T|=(G)=|G-T|=m-nm-n+1 +1 显然有显然有 m m=+=+4.2.2 图的生成树及其求法图的阶图的阶表示表示生成树的大小生

33、成树的大小，取决于，取决于G G 中的节点中的节点数。数。图的空度表示图的空度表示生成树覆盖该图的程度生成树覆盖该图的程度，越小，越小，覆盖度越高，覆盖度越高，=0=0表示图表示图G G就是树。另一方面，空就是树。另一方面，空度度也反映也反映图图G G的连通程度的连通程度，越大，连枝数越多，越大，连枝数越多，图的连通性越好，图的连通性越好，=0=0表示图表示图G G有最低连通性，即有最低连通性，即最小连通图。最小连通图。4.2.2 图的生成树及其求法破圈法：破圈法：拆除图中的所有回路并使其保持连通，拆除图中的所有回路并使其保持连通，就能得到就能得到G G的一棵生成树。的一棵生成树。避圈法：避圈

34、法：在有在有n n个点的连通图个点的连通图G G中任选一条边（及中任选一条边（及其节点）；选取第二、三其节点）；选取第二、三条边，使之不与已选条边，使之不与已选的边形成回路；直到选取完的边形成回路；直到选取完n n-1-1条边且不出现回路，条边且不出现回路，结束。结束。2 2生成树的求法生成树的求法4.2.2 图的生成树及其求法例例4.34.3 分别用破圈法和避圈法选择图分别用破圈法和避圈法选择图4.154.15（a a）的一）的一棵树。棵树。图图4.154.15（a a）解：解：破圈法破圈法：如图：如图4.154.15所示，选择所示，选择回路（回路（v v1,1,v v3,3,v v4 4）

35、，去掉），去掉e e1 1；选；选择回路（择回路（v v1,1,v v2,2,v v3 3），去掉），去掉e e3 3；选择回路（选择回路（v v2,2,v v3,3,v v5 5）,去掉去掉e e6 6；最后选择回路（最后选择回路（v v3,3,v v4,4,v v6,6,v v5 5），），去掉去掉e e9 9依次得到图依次得到图4.154.15（b b）-（e e），），其中（其中（e e）为（）为（a a）的一棵生成树。）的一棵生成树。避圈法避圈法：依次选取五条边：依次选取五条边e e3,3,e e4,4,e e7,7,e e9,9,e e8 8，每一条边均不与，每一条边均不与已选边形

36、成回路，见图已选边形成回路，见图4.164.16，最后，最后得到得到G G的又一棵生成树（的又一棵生成树（e e）。）。4.2.2 图的生成树及其求法图图4.15 4.15 破圈法示意图破圈法示意图4.2.2 图的生成树及其求法 图图4.16 4.16 避圈法示意图避圈法示意图4.2 树4.2.1 4.2.1 树的概念及性质树的概念及性质4.2.2 4.2.2 图的生成树及其求法图的生成树及其求法4.2.3 4.2.3 最小生成树算法最小生成树算法 4.2.3 最小生成树算法最小生成树：最小生成树：如果连通图如果连通图G G本身不是一棵树，则它本身不是一棵树，则它的生成树就不止一棵。如果为图的

37、生成树就不止一棵。如果为图G G加上权值，则各加上权值，则各个生成树的树枝权值之和一般不相同，其中权值个生成树的树枝权值之和一般不相同，其中权值之和最小的那棵生成树为之和最小的那棵生成树为最小生成树最小生成树。最小生成树一般是在两种情况下提出的，一种是最小生成树一般是在两种情况下提出的，一种是有约束条件下的最小生成树有约束条件下的最小生成树，另一种是，另一种是无约束条无约束条件下的最小生成树件下的最小生成树。4.2.3 最小生成树算法Kruskal算法算法将连通图将连通图G G中的所有边按权值的非减次序排列；中的所有边按权值的非减次序排列；选取权值最小的边为树枝，再按选取权值最小的边为树枝，再

38、按的次序依次的次序依次选取不与已选树枝形成回路的边为树枝。如有选取不与已选树枝形成回路的边为树枝。如有几条这样的边权值相同则任选其中一条；几条这样的边权值相同则任选其中一条；对于有对于有n n个点的图直到个点的图直到n-n-1 1条树枝选出，结束。条树枝选出，结束。这种算法的复杂性主要决定于把各边排列成有这种算法的复杂性主要决定于把各边排列成有序的队列。序的队列。1 1无约束条件的情况无约束条件的情况 4.2.3 最小生成树算法写出图写出图G G的权值矩阵；的权值矩阵；由点由点v v1 1开始，在行开始，在行1 1中找出最小元素中找出最小元素w w1 1j j；在行在行1 1和行和行j j中，

39、圈去列中，圈去列1 1和列和列j j的元素，并在这的元素，并在这两行余下的元素中找出最小元素，如两行余下的元素中找出最小元素，如w wjkjk（如有（如有两个均为最小元素可任选一个）；两个均为最小元素可任选一个）；在行在行1 1、行、行j j和行和行k k中，圈去列中，圈去列1 1、列、列j j和列和列k k的元的元素，并在这三行余下的元素中找出最小元素；素，并在这三行余下的元素中找出最小元素；直到矩阵中所有元素均被圈去，即找到图直到矩阵中所有元素均被圈去，即找到图G G的一的一棵最小生成树。棵最小生成树。2.Prim2.Prim算法算法 4.2.3 最小生成树算法 例例4.44.4 要建设连

40、接如图要建设连接如图4.174.17所示的七个城镇的线路所示的七个城镇的线路网，任意两个城镇间的距离见表网，任意两个城镇间的距离见表4.14.1，请用，请用P P算法找算法找出线路费用最小的网路结构图（设线路费用与线路出线路费用最小的网路结构图（设线路费用与线路长度成正比）。长度成正比）。C2C3C4C5C6C7C1859121412C291517811C379117C431710C5810C69表表4.1 4.1 各城镇间的距离（各城镇间的距离（kmkm）图4.17 七个城市的地图4.2.3 最小生成树算法 解解：这个问题可抽象为用图论求最小生成树的问题，首先这个问题可抽象为用图论求最小生成

41、树的问题，首先列出权值矩阵列出权值矩阵 小元素为小元素为3 3，重复上述过程，依次找到，重复上述过程，依次找到7 7，8 8，8 8，将这，将这些最小元素对应的边和节点全部画出就可得到一棵最些最小元素对应的边和节点全部画出就可得到一棵最小生成树，如图小生成树，如图4.184.18所示。所示。在第一行中找出最小元素在第一行中找出最小元素5 5，圈去第，圈去第1 1行和第行和第3 3行中第行中第1 1列和第列和第3 3列的元素，在这两列的元素，在这两行余下的元素中找到最小元行余下的元素中找到最小元素素7 7，再圈去第，再圈去第1 1行、第行、第3 3行行和第和第4 4行中第行中第1 1列、第列、第

42、3 3列和列和第第4 4列的元素，从这列的元素，从这3 3行余下行余下的元素中找到最的元素中找到最4.2.3 最小生成树算法所以，费用最小的网路结构网路总长度所以，费用最小的网路结构网路总长度L L为为 L L=3+5+7+7+8+8=38 km=3+5+7+7+8+8=38 km图图4.18 4.18 最小费用网络结构图最小费用网络结构图4.2.3 最小生成树算法在设计通信网的网路结构时，经常会提出一些特殊的要求，在设计通信网的网路结构时，经常会提出一些特殊的要求，如某交换中心或某段线路上的业务量不能过大，任意两点如某交换中心或某段线路上的业务量不能过大，任意两点间经过转接的次数不能过多等，

43、这类问题可归结为求有约间经过转接的次数不能过多等，这类问题可归结为求有约束条件的最小生成树的问题。束条件的最小生成树的问题。关于有约束条件的最小生成树的求法目前并没有一般的有关于有约束条件的最小生成树的求法目前并没有一般的有效算法，而且不同的约束条件，算法也将有区别。这里，效算法，而且不同的约束条件，算法也将有区别。这里，我们只介绍一种常用的解决有约束条件的生成树的方法，我们只介绍一种常用的解决有约束条件的生成树的方法，即穷举法。即穷举法。穷举法就是先把图中的所有生成树穷举出来，再按条件筛穷举法就是先把图中的所有生成树穷举出来，再按条件筛选，最后选出最短的符合条件的生成树。选，最后选出最短的符

44、合条件的生成树。显然这是一种最显然这是一种最直观的也是最繁杂的方法，虽然可以得到最佳解，但计算直观的也是最繁杂的方法，虽然可以得到最佳解，但计算量往往很大。量往往很大。2 2有约束条件的最小生成树有约束条件的最小生成树第四章 网络规划设计理论基础4.1 4.1 图论基础图论基础 4.2 4.2 树树4.3 4.3 路径选择算法路径选择算法4.4 4.4 网络流量分配及其算法网络流量分配及其算法4.5 4.5 通信网的可靠性通信网的可靠性4.3 路径选择算法4.3.1 4.3.1 狄克斯特拉（狄克斯特拉（DijkstraDijkstra）算法）算法4.3.2 Warshall-Floyd4.3.

45、2 Warshall-Floyd算法算法4.3.3 4.3.3 第第K K条最短路径选择问题条最短路径选择问题4.3.1 狄克斯特拉（Dijkstra）算法已知图已知图G G=(=(V V,E E)，将其节点集分为两组：置定节点集，将其节点集分为两组：置定节点集G Gp p和未置定节点集和未置定节点集G G-G Gp p。其中。其中G Gp p内的所有置定节点，是指内的所有置定节点，是指定点定点v vs s到这些节点的路径为最短（即已完成最短路径的到这些节点的路径为最短（即已完成最短路径的计算）的节点。而计算）的节点。而G-GG-Gp p内的节点是未置定节点，即内的节点是未置定节点，即v vs

46、 s到到未置定节点距离是暂时的，随着算法的下一步将进行不未置定节点距离是暂时的，随着算法的下一步将进行不断调整，使其成为最短径。在调整各未置定节点的最短断调整，使其成为最短径。在调整各未置定节点的最短径时，是将径时，是将G Gp p中的节点作为转接点。具体地说，就是将中的节点作为转接点。具体地说，就是将G Gp p中的节点作为转接点，计算（中的节点作为转接点，计算（v vs s,v vj j）的径长（）的径长（v vj jG G-G Gp p），若该次计算的径长小于上次的值，则更新径长，），若该次计算的径长小于上次的值，则更新径长，否则，径长不变。计算后取其中径长最短者，之后将否则，径长不变。

47、计算后取其中径长最短者，之后将v vj j划归到划归到G Gp p中。当（中。当（G G-G Gp p）最终成为空集，同时）最终成为空集，同时G Gp p=G=G，即，即求得求得v vs s到所有其他节点的最短路径。到所有其他节点的最短路径。1 1D D算法原理算法原理4.3.1 狄克斯特拉（Dijkstra）算法 ：表示表示vs与其他节点的距离。与其他节点的距离。在在Gp中，中，wi表示上一次划分到表示上一次划分到Gp中的节点中的节点vi到到vs的最短路径。的最短路径。在在G-Gp中，表示从中，表示从vs到到vj 仅经过仅经过Gp中的节中的节点作为转接点所求得的该次的最短路径的点作为转接点所

48、求得的该次的最短路径的长度。长度。如果如果vs与与vj不直接相连，且无置定节点作为不直接相连，且无置定节点作为转接点，则令转接点，则令 。4.3.1 狄克斯特拉（Dijkstra）算法图4.19 D算法流程图2 2D D算法实现流程算法实现流程4.3.1 狄克斯特拉（Dijkstra）算法 例例4.5 用用D算法求图算法求图4.20中中v1到其他各节点的最短到其他各节点的最短路径。路径。图图4.20 D4.20 D算法例题图算法例题图4.3.1 狄克斯特拉（Dijkstra）算法 解解：计算过程及结果列于表：计算过程及结果列于表4.24.2及表及表4.34.3中。最终路径中。最终路径图如图图如

49、图4.214.21所示。所示。表表4.2 D4.2 D算法计算过程算法计算过程4.3.1 狄克斯特拉（Dijkstra）算法图图4.21 v14.21 v1到其他各节点的最短路径到其他各节点的最短路径表表4.3v14.3v1到其他各节点的最短路径和径长到其他各节点的最短路径和径长4.3 路径选择算法4.3.1 4.3.1 狄克斯特拉（狄克斯特拉（DijkstraDijkstra）算法）算法4.3.2 Warshall-Floyd4.3.2 Warshall-Floyd算法算法4.3.3 4.3.3 第第K K条最短路径选择问题条最短路径选择问题4.3.2 Warshall-Floyd算法F算法

50、使用算法使用距离矩阵距离矩阵和和路由矩阵路由矩阵。距离矩阵距离矩阵是一个是一个n n矩阵，以图矩阵，以图G的的n个节点为行和列。个节点为行和列。记为记为W=wij n n，wij表示图表示图G中中vi和和vj两点之间的路径两点之间的路径长度。长度。路由矩阵路由矩阵是一个是一个n n矩阵，以图矩阵，以图G的的n个节点为行和列。个节点为行和列。记为记为R=rij n n，其中，其中rij表示表示vi至至vj经过的转接点（中间经过的转接点（中间节点）。节点）。F算法的思路是首先写出初始的算法的思路是首先写出初始的W阵和阵和R阵，接着按顺序阵，接着按顺序依次将节点集中的各个节点作为中间节点，计算此点距