第11章 通信网理论分析

《第11章 通信网理论分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第11章　通信网理论分析11.1图论基础11.2最短路径算法11.3排队论基础11.4电路交换网分析11.5分组交换数据网分析11.6下一代网络性能分析11.7多址接入系统的分析11.8传输网性能分析11.1图论基础11.1.1网络和图1．图的定义设有端集：V= {v1，v2，…，vn}边集：E= {e1，e2，…，em}当边集E是端集V中两个元产生关系R时，则V和E组成图G，即G= {V，E}由上述定义可知，图G中的V集可任意给定，而E集只是代表V集中两个元的关系。当Vi对Vj有某种关系R，为邻接关系er时有：er∈E，每一个e

2、r所对应的两个端Vi和Vj称为与er有关联的端，存在er的两个端称为邻接端。根据端间关系的性质，可分为有向图和无向图，当Vi对Vj有某种关系等价于Vj对Vi有某种关系，就称该图为无向图，反之则称为有向图。图是集合V及其关系集E的综合{V，E}，集合论中的许多概念都可以移植过来。若图A的端集和边集分别是图G的端集和边集的子集，则图A是图G的子图，表示为AG若AG但A≠G，则称A是G的真子图；若AG，A，则必有A=G。且G2．图的运算设A，B为任意集合。A∪B称为A与B的并集（unionset），定义为A∪B= {x

3、x∈A∨x∈B

4、}∪称为并运算。A∩B称为A与B的交集（intersectionset），定义为A∩B= {x

5、x∈A∧x∈B}∩称为交运算。A−B称为A与B的差集（differenceset），定义为A−B= {x

6、x∈A∧xB}−称为差运算。A−称为A的补集（complementset），定义为A− =U−A= {xxA}−称为补运算，它是一元运算，是差运算的特例。说明图的运算的示意图如图11.1所示。图11.1图的运算（1）并图设图Ga、Gb如图10.1（a）和（b）所示，Gc如图10.1（c）所示。从图中看出，Gc中的端集和边

7、集分别是Ga和Gb中的端集和边集的并，称图Gc是Ga和Gb的并图。记为Gc=Ga∪Gb对于边集和端集则有Vc=Va∪VbE=Ea∪Eb（2）交图Gd如图10.1（d）所示，则Gd是Ga和Gb的交图，Gb是Ga和Gb的公共部分，同时有Vd=Va∩VbEd=Ea∩Eb（3）差图Ge如图10.1（e）所示，这是从Ga中去掉Ga和Gb的共有边和共有端，但保留未去掉的边关联的端。Ge是Ga和Gb的差图。记为Ge=Ga～Gb（4）环和图Gf如图10.1（f）所示，这是从Ga∪Gb中去掉Ga和Gb的共有边。Gf是Ga和Gb的环和图。记为Gf=G

8、aGb一般来说存在Ga～Gb=Ga−Ga∩Gb若Ga∩Gb=f=空图，则Ga∪Gb=Ga+Gb，称为它们的直和。若GbGa=Ga−Gb，称为它们的直差。11.1.2图的矩阵表示射出边射入边1．图的关联阵表示关联阵是表达图的端与边的关联性的矩阵。若图含有m条边，n个端，则图的关联阵A0是行数为端数，列数为边数的n×m阵，A0= [aij]n×m对于无向图则有对于有向图而言，则有关联矩阵计算用书如图11.2所示，对于如图11.2所示的有向图，其关联矩阵可表示为：图11.2关联矩阵计算用图从图的关联矩阵可以进一步来计算图的生成树的数量。

9、连通图的生成树的数量可以用以下公式来表示：（11.1）式中A是连通图的关联矩阵，AT是A阵的转置。即此图有生成树21棵。以上所讨论的图为有向图，对于无向图，可以在图上任意加箭头，得到相应的有向图，这样就可求得无向图的生成树的数目。以图11.2为例，关联阵A为式（11.1）所示，生成树数目可以由上式算得：2．图的邻接阵的表示图也可以用端与端之间的关系矩阵，即邻接阵来表示，邻接阵的行和列都与图的端相对应。对于一个有几个端的图，邻接阵是一个n×n的方阵，即其中对于图11.2所示的有向图，其邻接阵为（11.2）对于无向图，则有cij=ei

10、j因此，无向图的邻接阵是一个对称阵。1．树和生成树树是图论中一个十分重要的概念，在网络的组播，路由选择中都有着广泛的应用，下面说明树的定义以及树的求法。树定义为一个不包括环路的连通图，它具有以下性质。①树是无环的连通图，当对于任何不同的节点i和j都有一个从i到j的路由时，图是连通图。②树是最小的连通图，即树中去掉任一边就成为非连通图，失去了连通性，所以是最小的连通图。③若树有m条边及n个端，则有m=n−1这可用数学归纳法来证明。因此，树可定义为有n个端，n−1条边的连通图。树的例子如图11.3所示。图11.3树的例子生成树是树中的

11、重要一类，下面说明它们的定义。设T是连通图G的子图。TG，若T含有G的所有端，则称T是G的生成树，也就是说生成树是覆盖连通图所有端的树。只有连通图才有生成树，反之，有生成树的图必然是连通图。对于图中的某一生成树而言，生成树上的边称为树枝，非树枝的边