通信网络基础第一章.ppt

《通信网络基础第一章.ppt》由会员分享，可在线阅读，更多相关《通信网络基础第一章.ppt（82页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 第第1章章 通信网络概论及数学基础通信网络概论及数学基础2 1.3 通信网络中的数学基础通信网络中的数学基础 1.3.1 随机过程的基本概念随机过程的基本概念1.3.2 Poisson过程过程1.3.3 马尔可夫链马尔可夫链1.3.4 图论基础图论基础3 1.3 通信网络中的数学基础通信网络中的数学基础为为了了定定量量地地描描述述通通信信网网络络的的运运行行过过程程、设设计计通通信信网网络络的的体体系系结结构构和和评评估估通通信信网网络络容容量量、时时延延和和服服务务质质量量等等，我我们们需需要要了了解解网网络络中中每每个个链链路路、节节点点、交交换换机机/路路由由器器，用用户户终终端端等

2、等设设备备的的输输入入输出业务流的输出业务流的行为特征行为特征和和处理过程处理过程。AEFDCB A(t)C(t)D(t)B(t)描述这些行为特征和处理过程的描述这些行为特征和处理过程的基本数学基础是基本数学基础是随机过程随机过程和和排队论排队论，描述网络结构的基本方法是描述网络结构的基本方法是图论图论。本。本节主要讨论常用的随机过程和图论基节主要讨论常用的随机过程和图论基础，在第三章中将详细讨论排队论的础，在第三章中将详细讨论排队论的基本内容。基本内容。4 1.3.1 随机过程的基本概念（随机过程的基本概念（1 1）随机过程随机过程是用来描述在一个观察区间内某一实体（是用来描述在一个观察区间

3、内某一实体（壶壶口瀑布水的流量、食堂中的人数口瀑布水的流量、食堂中的人数）的随机行为。）的随机行为。tttX(t)X(t)X(t)(1)(2)(n)例如例如:在通信系统中的噪声就是一个典型的随机过程。在通信系统中的噪声就是一个典型的随机过程。(n台性能完全相同的通信接收机的输出如下图。台性能完全相同的通信接收机的输出如下图。)5 1.3.1 随机过程的基本概念（随机过程的基本概念（2 2）随机过程是随机过程是随机变量随机变量概念在概念在时间域时间域上的延伸。直观地讲，上的延伸。直观地讲，随机过程是时间随机过程是时间t的的函数的集合函数的集合，在任一个观察时刻，随，在任一个观察时刻，随机过程的取

4、值是一个随机变量。或者说，机过程的取值是一个随机变量。或者说，依赖于时间参依赖于时间参数数t的随机变量所构成的总体称为随机过程的随机变量所构成的总体称为随机过程。tttX(t)X(t)X(t)(1)(2)(n)t1X(t1)t2X(t2)6 1.3.1 随机过程的基本概念（随机过程的基本概念（3 3）设设X(t)是一个随机过程，则可以从两个方面来描述是一个随机过程，则可以从两个方面来描述X(t)的特征：的特征：一是一是在任意时刻在任意时刻t1，随机变量随机变量X(t1)的统计特征的统计特征，如一维分布函，如一维分布函数，概率密度函数，均值和方差等。数，概率密度函数，均值和方差等。二是二是同一随

5、机过程在不同时刻同一随机过程在不同时刻t1和和t2对应的随机变量对应的随机变量X(t1)和和X(t2)的相关特性的相关特性，如多维联合分布函数、相关函数、协方差，如多维联合分布函数、相关函数、协方差矩阵等。矩阵等。tttX(t)X(t)X(t)(1)(2)(n)t1X(t1)t2X(t2)7 1.3.1 随机过程的基本概念（随机过程的基本概念（4 4）随机过程随机过程X(t)的的一维分布函数一维分布函数，定义为，定义为 （1-1）式中式中P表示概率。表示概率。如如果果Ft(x)对对x的的微微分分存存在在，则则X(t)的的一一维维概概率率密密度度函函数数定义为定义为 （1-2）8 1.3.1 随

6、机过程的基本概念（随机过程的基本概念（5 5）通通常常一一维维分分布布函函数数不不能能完完全全描描述述随随机机过过程程的的特特征征，需需要要采采用用n维维联联合合分分布布函函数数。对对于于给给定定的的n个个时时刻刻t1，t2，tn，随随机机变变量量X(t1)，X(t2)，X(tn)的的联联合分布函数为：合分布函数为：（1-3）若若 则随机过程则随机过程X(t)的的均值函数均值函数为为 （1-4）9 1.3.1 随机过程的基本概念（随机过程的基本概念（6 6）若对任给的时刻若对任给的时刻t1和和t2，如下列函数如下列函数 （1-5）存在，则称存在，则称CX(t1,t2)为为X(t)的的协方差函数

7、协方差函数；（1-6）为为X(t)的的方差函数方差函数。10 1.3.1 随机过程的基本概念（随机过程的基本概念（7 7）若若对对任任给给的的时时间间t1和和t2，RX(t1,t2)=)=E E X(t1)X(t2)存存在，则在，则 RX(t1,t2)为为X(t)的的自相关函数自相关函数。协方差函数，自相关函数、均值函数有下列关系：协方差函数，自相关函数、均值函数有下列关系：（1-7）11 1.3.1 随机过程的基本概念（随机过程的基本概念（8 8）下面介绍几类典型的随机过程：下面介绍几类典型的随机过程：1.独立随机过程独立随机过程2.马尔可夫马尔可夫(Markov)过程过程 3独立增量过程独

8、立增量过程 4平隐随机过程平隐随机过程 5 Poisson过程过程 6 马尔可夫链马尔可夫链12 1.独立随机过程独立随机过程 设设有有一一个个随随机机过过程程X(t)，如如果果对对任任意意给给定定的的时时刻刻t1，t2，tn，随随机机变变量量X(t1),X(t2),X(tn)是是相相互互独独立立的，也就是其的，也就是其n维分布函数可以表示为：维分布函数可以表示为：t1 t2 t3 tn-2 tn-1 tnX(t)t（1-8）则则称称X(t)是是独独立立随随机机过过程程。该该过过程程的的特特点点是是任任意意一一时时刻的状态与其他任何时刻的状态无关。刻的状态与其他任何时刻的状态无关。13 2.马

9、尔可夫马尔可夫(Markov)过程过程(1)(1)设有设有X(t)一个随机过程，如果对于一个任意的时间序一个随机过程，如果对于一个任意的时间序列：列：t1 t2 t0)所处的状所处的状态与该过程在态与该过程在t0时刻之前的状态无关。时刻之前的状态无关。式（式（1-9）右端的条件分布函数可以写成：）右端的条件分布函数可以写成：（1-10）该式称为马氏过程的该式称为马氏过程的转移概率转移概率。15 3独立增量过程独立增量过程 设设X(t2)-X(t1)=X(t1,t2)是随机过程是随机过程X(t)在时间间隔在时间间隔 t1,t2)上的增量，如果对于时间上的增量，如果对于时间t的任意的任意n个值个值

10、0 0 t1 t2 tn，增量增量X(t1,t2),X(t2,t3),X(tn-1,tn)是是相相互独立互独立的，则称的，则称X(t)为为独立增量过程独立增量过程。该过程的该过程的特点特点是：在任一时间间隔上是：在任一时间间隔上,随机过程状态随机过程状态的改变并不影响未来任一时间间隔上状态的改变。可的改变并不影响未来任一时间间隔上状态的改变。可以证明独立增量过程是一种特殊的马尔可夫过程。以证明独立增量过程是一种特殊的马尔可夫过程。t1 t2 t3 tn-2 tn-1 tnX(t)tX(t1)X(t2)X(t3)X(tn-2)X(tn-1)X(tn)X(t1,t2)X(t2,t3)X(tn-2,

11、tn-1)X(tn-1,tn)16 4平隐随机过程平隐随机过程(1)(1)如果对于时间如果对于时间t的任意的任意n个值个值t1，t2，tn和任意实数和任意实数，随机过程，随机过程X(t)的的n维分布函数满足关系式：维分布函数满足关系式：（1-11）则称则称X(t)为为平稳随机过程平稳随机过程或简称为平稳过程。或简称为平稳过程。该过程的该过程的特点特点是随机过程的统计特性不随时间的平移而是随机过程的统计特性不随时间的平移而变化。变化。t1 t2 t3 tn-2 tn-1 tnX(t)tt1+t2+t3+tn-2+tn-1+tn+17 4平隐随机过程平隐随机过程(2)(2)按照上述定义的随机过程通

12、常称为按照上述定义的随机过程通常称为严（狭义）平稳过程严（狭义）平稳过程。在实际应用中，我们更关心这样一类过程：其在实际应用中，我们更关心这样一类过程：其 （称为二阶矩过程），且满足下列条件：（称为二阶矩过程），且满足下列条件：1）均值均值为常量（与时间为常量（与时间t无关）；无关）；2）对于任意时刻）对于任意时刻s和和t，其其相关函数相关函数满足满足 ，即相关函数仅与时差即相关函数仅与时差t-s有关，而与有关，而与s,t的取值无关；的取值无关；称这类过程为称这类过程为宽（广义）平稳过程宽（广义）平稳过程。在实际应用中所指。在实际应用中所指的随机过程通常是宽平稳过程。的随机过程通常是宽平稳过程

13、。18 各态历经性各态历经性(1)(1)为了说明各态历经性，在时间轴上定义下列两种平均：为了说明各态历经性，在时间轴上定义下列两种平均：（1-12）（1-13）为随机过程的为随机过程的时间均值时间均值和和时间相关函数时间相关函数。-T 0 +Ttt19 各态历经性各态历经性(2)(2)如果如果X(t)是一个平稳过程，如果是一个平稳过程，如果=EX(t)=mx依概率依概率1成立（即对所有样本都成成立（即对所有样本都成立），则称随机过程立），则称随机过程X(t)的的均值具有各态历经均值具有各态历经性性；如果如果=EX(t)X(t+)=Rx()依概率依概率1成立，则称过程成立，则称过程X(t)的的自

14、相关函数具有自相关函数具有各态历经性；各态历经性；如果如果X(t)的均值和自相关函数都具有各态历经性，的均值和自相关函数都具有各态历经性，则称则称X(t)是（宽）各态历经过程是（宽）各态历经过程，或者说，或者说X(t)是各是各态历经的。态历经的。20 1.3.2 Poisson过程过程(1)(1)在日常生活中，如果我们观察顾客进入商店、银行或在日常生活中，如果我们观察顾客进入商店、银行或其它公共服务场所的过程，我们发现如果把一位顾客其它公共服务场所的过程，我们发现如果把一位顾客的到达看成一个的到达看成一个“随机点随机点”，则这是一个源源不断出现，则这是一个源源不断出现随机点的过程随机点的过程。

15、在这一过程中任一段时间内到达的顾。在这一过程中任一段时间内到达的顾客数也是随机的。客数也是随机的。这类描述到达顾客数及其特征的过程通常称为这类描述到达顾客数及其特征的过程通常称为计数过计数过程。程。如果我们考察一个交换局中如果我们考察一个交换局中电话呼叫到达电话呼叫到达（人们拨打电（人们拨打电话的行为中拿起电话并拨出对方号码的动作称为一次电话的行为中拿起电话并拨出对方号码的动作称为一次电话呼叫到达）的过程也具有类似的特征。话呼叫到达）的过程也具有类似的特征。21 1.3.2 Poisson过程过程(2)(2)设一个随机过程为设一个随机过程为A(t),t 0的的取值为非负整数取值为非负整数，如果

16、该过程满足下列条件，则称该过程为到达率为如果该过程满足下列条件，则称该过程为到达率为 的的Poisson(泊松泊松)过程过程。(1)A(t)是一个是一个计数过程计数过程，它表示在，它表示在0,t）区间内到达区间内到达的用户总数，的用户总数，A(0)=0,A(t)的的状态空间状态空间为为0,1,2,。如图如图1-12所示。任给两个时刻所示。任给两个时刻s和和t，且，且s d 1 1，并仅当，并仅当n n为为d d的整倍时有的整倍时有则状态则状态i i是有周期性的。是有周期性的。非周期性如果马氏链中没有一个状态是有周期性的，则称该马氏链为非周期的。本课程仅考虑本课程仅考虑非周期不可约非周期不可约的

17、马氏链。的马氏链。44 1.3.3 马尔可夫链马尔可夫链(12)(12)对于马氏链，其对于马氏链，其状态的稳态概率状态的稳态概率定义为：如果有定义为：如果有 （1-27）则称概率分布则称概率分布 是马氏链的是马氏链的稳态分布稳态分布。对于概率分布有对于概率分布有 。稳稳态态概概率率反反映映了了系系统统达达到到稳稳态态后后，系系统统处处于于某某一一状状态态的的可能性（概率）。可能性（概率）。45 1.3.3 马尔可夫链马尔可夫链(13)(13)稳态分布稳态分布可以表示为：可以表示为：（1-28）即过程从初始状态即过程从初始状态X0=i 出发，最终转移到状态出发，最终转移到状态Xn=j的的概率。显

18、然与初始状态概率。显然与初始状态X0=i无关。无关。稳态分布稳态分布也可以表示为：（以概率也可以表示为：（以概率1成立）成立）（1-29）因此因此pj表示该过程中访问状态表示该过程中访问状态j的时间比例或频率，且该的时间比例或频率，且该频率与初始状态无关。频率与初始状态无关。46 1.3.3 马尔可夫链马尔可夫链(14)(14)该该式式称称为为全全局局平平衡衡方方程程(Global balance equations)。它它表表示示在在稳稳态态情情况况下下，从从一一个个状状态态j转转移移出出去去的的频频率率（式式（1-30）左左边边）等等于于转转移移进进入入状状态态j的的频频率率（式式（1-3

19、0）的的右右边边）。该该方方程程提提供供给给我我们们一一种种典典型型的的求求解解稳稳态态概概率率分布的方法。分布的方法。由于由于 ，则结合式（，则结合式（1-27）有）有 （1-30）47 1.3.3 马尔可夫链马尔可夫链(15)(15)例例1.2（续续）求随机游走过程的稳态概率。）求随机游走过程的稳态概率。在在例例1.2中中我我们们已已知知各各种种状状态态的的转转移移概概率率矩矩阵阵，设设状状态态a5,a4,a3,a2,a1的的稳稳态态概概率率为为p5,p4,p3,p2和和p1，则则我们根据式（我们根据式（1-27）可得稳态概率的方程为：）可得稳态概率的方程为：48 1.3.3 马尔可夫链马

20、尔可夫链(16)(16)例例1.2（续续）求随机游走过程的稳态概率。）求随机游走过程的稳态概率。由于由于 是稳态概率分布，则有是稳态概率分布，则有 （1-32）求求解解式式(1-31)和和式式(1-32)组组成成的的方方程程组组，得得稳稳态态概概率分布为：率分布为：（1-33）49 生灭（生灭（birth-death）过程过程(1)(1)在实际中，我们经常遇到这样一类特殊的马氏过程：在实际中，我们经常遇到这样一类特殊的马氏过程：仅有相邻状态的转移，而没有其它状态的转移（即如仅有相邻状态的转移，而没有其它状态的转移（即如果果 ，则，则 ），如图），如图1-15所示。这一所示。这一类过程通常称为类

21、过程通常称为生灭（生灭（birth-death）过程过程。50 生灭（生灭（birth-death）过程过程(2)(2)它它表表示示一一个个群群体体（动动物物、生生物物等等）总总数数为为n的的特特殊殊状状态态转转移移过过程程。该该群群体体总总数数的的状状态态转转移移只只有有三三种种可可能能：或或者者从从n增增加加一一个个（群群体体出出生生一一个个），或或者者从从n减减少少一一个个（死死亡亡一一个个），或或者者群群体体的的总总数数n保保持持不不变变。而而其其它它所所有有可可能能的的转转移移相相对对前前三三种种转转移移都都是是高高阶阶无无穷穷小小，因因而而可可以以忽忽略略不不计计。该该群群体体状状

22、态态的的转转移移概概率率取取决决于于群群体体的的总数总数n（状态）。状态）。51 生灭（生灭（birth-death）过程过程(3)(3)令令 ，则应用式（，则应用式（1-30）可得：）可得：（1-35）它表示在稳态的情况下，从它表示在稳态的情况下，从状态状态n转移到状态转移到状态n+1的频的频率等于从状态率等于从状态n+1转移到状态转移到状态n的频率的频率，或在状态转移，或在状态转移图中设置一个虚拟的平面（图图中设置一个虚拟的平面（图1-15中的虚线），则进中的虚线），则进入该平面的频率等于退出该平面的频率，即该平面是入该平面的频率等于退出该平面的频率，即该平面是系统的一个稳定点。系统的一个

23、稳定点。52 生灭（生灭（birth-death）过程）过程(2)令状态空间为令状态空间为，详细平衡方程详细平衡方程53 生灭（生灭（birth-death）过程）过程(3)详细平衡方程详细平衡方程 local balance equations求解稳态概率求解稳态概率54 1.3.3 马尔可夫链马尔可夫链(16)(16)上式可推广到一个更一般的形式：上式可推广到一个更一般的形式：（1-36）该等式称为该等式称为详细平衡方程详细平衡方程（detailed balance equation）。）。如果对于一个过程，有式（如果对于一个过程，有式（1-36）成立，则意味着有式）成立，则意味着有式（1

24、-30）全局平衡方程存在。但并不是任何马尔可夫链）全局平衡方程存在。但并不是任何马尔可夫链都必须有式（都必须有式（1-36）成立。但在很多实际应用中，式）成立。但在很多实际应用中，式（1-36）是成立的。因此实际中，我们可以先假设式）是成立的。因此实际中，我们可以先假设式（1-36）成立，然后通过它们求解稳态概率）成立，然后通过它们求解稳态概率 pj,j。如果求得的结果满足如果求得的结果满足 ，则求得的分布，则求得的分布 pj,j就是满足式（就是满足式（1-27）的稳态分布。）的稳态分布。55 生灭（生灭（birth-death）过程过程(4)(4)例例1.3 设一个特殊的生灭过程的状态转移概

25、率为设一个特殊的生灭过程的状态转移概率为 试求其稳态分布。试求其稳态分布。解：解：利用式（利用式（1-35）（或假设式（）（或假设式（1-36）成立）有：）成立）有：从而有：从而有：式中式中 经过递推得：经过递推得：56 生灭（生灭（birth-death）过程过程(5)(5)显然只有在显然只有在 的情况下，才可能有下式成立。的情况下，才可能有下式成立。从而可得从而可得 。进而可得：。进而可得：综上可得，在综上可得，在 的情况下，该生灭过程的稳态分的情况下，该生灭过程的稳态分布为布为57 1.3.4 图论基础图论基础 在通信网络中，许多问题的描述都是基于图论的，因在通信网络中，许多问题的描述都

26、是基于图论的，因此，我们下面对图论的一些基本概念进行讨论。其实此，我们下面对图论的一些基本概念进行讨论。其实我们已应用了图的很多概念。我们已应用了图的很多概念。例如：例如：AEFDCB58 1.图的概念（图的概念（1 1）一般几何上将一般几何上将图图定义成空间中一些定义成空间中一些点点（顶点）和连（顶点）和连接这些点的接这些点的线线（边）的（边）的集合集合。图论中将图定义为图论中将图定义为G=(V,E)，其中其中V表示顶点的集合，表示顶点的集合，E表示边的集合。表示边的集合。例如例如：如图：如图1-16所示的图所示的图可以表示为：可以表示为：59 1.图的概念（图的概念（2 2）我我们们也也可

27、可以以用用边边的的两两个个顶顶点点来来表表示示边边。如如果果边边e的的两两个个顶顶点点是是u和和v，那那么么e可可写写成成 e=(u,v)，这这里里（u,v）表表示示u和和v的的有序对有序对。如如果果有有（u,v）和和（v,u）同同时时存存在在，它它表表达达了了以以u，v为为端端点点的的一一条条无无向向边边。如如果果图图中中的的所所有有边边都都是是无无向向边边，则则称该图为称该图为无向图无向图。uveuve这这样样，我我们们也也可可以以这这样样来来表表示示无无向向图图1-16。G=(V,E),60 1.图的概念（图的概念（3 3）一般图一般图G=(V,E)的顶点数用的顶点数用 表示，边的数目表

28、示，边的数目 用用 表示。若表示。若 和和 都是有限的，则称图都是有限的，则称图G是是有限图有限图，否则称为无限图。本书只讨论有限图的情，否则称为无限图。本书只讨论有限图的情况。况。61 1.图的概念（图的概念（4 4）在实际应用中，图中每条边可能有一个方向是很自然的在实际应用中，图中每条边可能有一个方向是很自然的（它反映了信息或物质的流向）。当给图（它反映了信息或物质的流向）。当给图G的每一条边的每一条边都规定一个方向，则称该图为都规定一个方向，则称该图为有向图有向图。对有向图图。对有向图图G=(V,E)，有向边有向边e用与其关联的顶点（用与其关联的顶点（u，v）的有序对来的有序对来表示，即

29、，它表示表示，即，它表示u为边为边e的起点，的起点，v为边为边e的终点。那么的终点。那么图图1-17所示的有向图可表示如下：所示的有向图可表示如下：62 1.图的概念（图的概念（5 5）如果顶点如果顶点v是边是边e的一个端点，则称边的一个端点，则称边e和顶点和顶点v相相关联关联（incident）；）；对于顶点对于顶点u和和v，若若 ，则称，则称u和和v是是邻接邻接的（的（adjacent）。）。在图在图1-16中，边中，边e2，e4，e5都与顶都与顶点点v4相关联，相关联，v4分别与分别与v1，v2，v3相邻接。若两条边有共相邻接。若两条边有共同的顶点，则称这两条边是邻接的。在图同的顶点，则

30、称这两条边是邻接的。在图1-16中，边中，边e1，e2，e3两两相邻接。两两相邻接。63 1.图的概念（图的概念（6 6）对图对图G=(V,E)和和G=(V,E)来说，若有来说，若有 和和 ，则称图，则称图 G是图是图G的一个的一个子图子图；若；若 或或 ，则，则称图称图G是图是图G的一个的一个真子图真子图。64 2 2 路径与回路路径与回路(1)(1)如果路径如果路径 中有中有v0=vk ，则则 为为回路回路（或（或环环Cycle），），回回路中没有重复边时称为路中没有重复边时称为简单回路简单回路。定定义义：图图的的一一些些顶顶点点和和边边的的交交替替序序列列 ，且且边边ei的的端端点点为为

31、vi-1和和vi，i=1,2,3,k，则则称称 为为一一条条路路径径（Path），v0和和vk分分别别为为 的的起起点点和和终终点点。如如果果 中中所所有有的的边边均均不不相相同同，则则称称其其为为简简单单路路径径。以以v0为为起起点，点，vk为终点的路径称为为终点的路径称为v0vk路径。路径。对于有向图也有类似定义路径、回路的概念，只不对于有向图也有类似定义路径、回路的概念，只不过此时需要考虑方向性。过此时需要考虑方向性。65 2 2 路径与回路路径与回路(2)(2)例例4：在图在图1-18中，中，是一路径，是一路径，是一回路是一回路.66 2 2 路径与回路路径与回路(3)(3)定定义义：

32、对对图图G=(V,E)来来说说，若若G的的两两个个顶顶点点u，v之之间间存存在在一一条条路路径径，则则称称u和和v是是连连通通的的；若若图图G的的任任意意两两个个顶顶点点都都是是连连通通的的，则则称称图图G是是连连通通的的；否否则则是是非非连连通的。非连通的图可分解为若干连通的子图。通的。非连通的图可分解为若干连通的子图。67 2 2 路径与回路路径与回路(4)(4)图图1-19的无方向图中，图（的无方向图中，图（a）中任意两个顶点之间中任意两个顶点之间都有路径，所以该图是连通的；图（都有路径，所以该图是连通的；图（b）中顶点中顶点3和和图中其它顶点之间没有路径，所以该图是非连通的；图中其它顶

33、点之间没有路径，所以该图是非连通的；图（图（c）则是一个孤立的节点。则是一个孤立的节点。68 2 2 路径与回路路径与回路(5)(5)对于有向图，若边对于有向图，若边去掉方向后是连通的去掉方向后是连通的，则称该图为连，则称该图为连通的有向图。若对于有向图的任意两个顶点通的有向图。若对于有向图的任意两个顶点u和和v之间存之间存在在u到到v的路径和的路径和v到到u的路径时，称该图为的路径时，称该图为强连通强连通的。的。图图1-20（a）的有向图是的有向图是一个连通的有向图，但一个连通的有向图，但不是强连通的。因为顶不是强连通的。因为顶点点2和顶点和顶点3之间不存在之间不存在双向的路径；图双向的路径

34、；图1-20（b）是一个强连通是一个强连通的图，该图中任意两个的图，该图中任意两个顶点之间都存在双向的顶点之间都存在双向的路径。路径。69 3.生成树和最小重量生成树（生成树和最小重量生成树（1 1）定义：不包括回路（环）的连通图，称为定义：不包括回路（环）的连通图，称为树树。定义：对于图，包含了图定义：对于图，包含了图G中所有顶点的树称为中所有顶点的树称为生成树生成树（Spanning Tree）。在图在图1-21中，图（中，图（b）、（）、（c）和（和（d）都是树。而图都是树。而图（a）由于有回路，所以不是树。在图由于有回路，所以不是树。在图1-21中，图（中，图（b）和图（和图（c）都是

35、图（都是图（a）的生成树。的生成树。70 3.生成树和最小重量生成树（生成树和最小重量生成树（2 2）对于一个给定的图对于一个给定的图G=(V,E)，其生成树的构其生成树的构造算法如下：造算法如下：1)令令n是是V中的任意一个顶点，构造子图中的任意一个顶点，构造子图G=(V,E)，其中，其中，V=n,E=空集；空集；2)如果如果V=V 则停止。此时则停止。此时G=(V,E)就就是一个生成树。否则进行第是一个生成树。否则进行第3）步；）步；3)令令(i,j)E，其中其中i V,j V-V ，并并采用下列方式更新采用下列方式更新V和和V ：V:=:=V j ，E:=:=E(i,j)，转到第转到第2

36、）步。）步。nEFDCBV=n,E=nEFDCBVnEFDCB71 3.生成树和最小重量生成树（生成树和最小重量生成树（3 3）该算法是从该算法是从仅有一个顶点、仅有一个顶点、0条边的子图条边的子图开始，以开始，以后每执行一次第后每执行一次第3）步就增加一个顶点和一条边。）步就增加一个顶点和一条边。这就意味着最终生成的树有个这就意味着最终生成的树有个 节点，节点，1条链条链路。路。通常对于一个连通图，其边的条数大于等于通常对于一个连通图，其边的条数大于等于 -1-1。如果一个图。如果一个图G的边的数目等于的边的数目等于 1，则上，则上述算法将使用该图中所有的边，因而有述算法将使用该图中所有的边

37、，因而有G=G，即即此时图此时图G本身就是一颗树。本身就是一颗树。72 3.生成树和最小重量生成树（生成树和最小重量生成树（4 4）一般而言，对于一个图可以一般而言，对于一个图可以有很多个生成有很多个生成树。树。对于通信网络来说，利用生成树来实对于通信网络来说，利用生成树来实现现广播广播是比较经济的。但每一条边的成本是比较经济的。但每一条边的成本或时延通常是不相同的，这时就要考虑树或时延通常是不相同的，这时就要考虑树中各边的重量（成本或时延）。通常我们中各边的重量（成本或时延）。通常我们用用Wij表示边（表示边（i,j）的重量。的重量。nEFDCBnEFDCBnEFDCB231152164最小

38、重量生成树最小重量生成树（MST，Minimum Weight Spanning Tree）：）：是指边的重是指边的重量和最小的生成树。量和最小的生成树。73 3.生成树和最小重量生成树（生成树和最小重量生成树（5 5）MST的任一个子树称为一个的任一个子树称为一个树枝树枝（fragment）。（）。（注意：一个顶点本注意：一个顶点本身就是自己的一个树枝）。身就是自己的一个树枝）。输出链路输出链路（Outgoing Arc）是指该链是指该链路的一个端点在路的一个端点在fragment内，而另一内，而另一个端点不在该个端点不在该fragment内。这里所谓内。这里所谓的链路和我们讨论的图的边的概

39、念的链路和我们讨论的图的边的概念是等效的。是等效的。下面我们讨论对于一个给定的图，下面我们讨论对于一个给定的图，如何构造该图的最小重量生成树如何构造该图的最小重量生成树（MST）。）。nEFDCB树树枝枝输出链路输出链路74 3.生成树和最小重量生成树（生成树和最小重量生成树（6 6）nEFDCB树树枝枝输出链路输出链路定理定理1：给定一个给定一个fragmentF，令令 =（i,j），j 是是的最小重量输出链的最小重量输出链路，将路，将扩展一条链路扩展一条链路 和一个顶点和一个顶点，仍是一个仍是一个fragment。nEFDCB231152164该定理告诉我们如何从该定理告诉我们如何从MST

40、的一个子树的一个子树生成一个完整的生成一个完整的MST。根据该定理可以有下列三种构造根据该定理可以有下列三种构造MST的的方法（以图方法（以图1-22（a）为例）。为例）。75 (1)Prim-Dijkstra(1)Prim-Dijkstra算法算法 选择任意一个顶点作为选择任意一个顶点作为一个一个fragment，然后根然后根据定理据定理1，每次选择一，每次选择一条具有最小重量的输出条具有最小重量的输出链路来扩展链路来扩展fragment，最终即可生成最终即可生成MST，如如图图1-22（b）所示。所示。76 (2)Kruskal算法算法 选择所有的顶点作为单顶选择所有的顶点作为单顶点的点的

41、fragment，在所有的在所有的链路中选择具有最小重量链路中选择具有最小重量且不会形成回路（环）的且不会形成回路（环）的链路添加到当前的链路添加到当前的fragment中。每次迭代仅中。每次迭代仅添加一条链路。最终即可添加一条链路。最终即可生成生成MST，如图如图1-22(c)所所示。示。77 (3)(3)分布式构造分布式构造MST算法算法(1)(1)假假定定网网络络中中仅仅有有惟惟一一一一个个MST.从从一一个个fragment集集（例如：该集就是图中的某一个顶点）开始（例如：该集就是图中的某一个顶点）开始:a).a).每每个个fragment决决定定它它自自己己的的最最小小重重量量输输出

42、出链链路路，将将该该链链路路添添加加到到自自身身的的fragment中中，并并通通知知该该输输出出链链路路的的另另一一个端点。个端点。b).b).只只要要连连接接两两个个fragment的的链链路路的的确确是是某某个个fragment的的最最小小重重量量输输出出链链路路，则则所所有有时时间间内内，算算法法都都维维持持着着MST的的fragment集，并且不会形成回路（环）集，并且不会形成回路（环）c).c).继继续续算算法法，添添加加新新的的链链路路，直直至至没没有有新新的的输输出出链链路路，且只有一个且只有一个fragment（即（即MST）为止。为止。78 (3)(3)分布式构造分布式构造

43、MST算法算法(2)(2)上述分布式算法要求上述分布式算法要求MST是惟一的；如果不惟一，是惟一的；如果不惟一，则可能会引起闭环。则可能会引起闭环。例如，有一个网络如图例如，有一个网络如图1-23所所示。从三个顶点开始构造示。从三个顶点开始构造MST，则可能会出现三个顶点同时则可能会出现三个顶点同时加入（加入（1,2）、（）、（2,3）和）和（3,1）三条链路，从而形成）三条链路，从而形成一个闭环。这个例子中，三条一个闭环。这个例子中，三条链路的重量是不可区分的。链路的重量是不可区分的。79 3.生成树和最小重量生成树（生成树和最小重量生成树（7 7）定理定理2 如果图如果图G中中所有链路的重

44、量是不同的所有链路的重量是不同的，则仅，则仅有惟一的一个有惟一的一个MST。在实际的网络中，对于具有相同重量的链路，可在实际的网络中，对于具有相同重量的链路，可以采用以采用链路重量以及链路关联的两个顶点的标号链路重量以及链路关联的两个顶点的标号来共同区分链路。例如，有两条链路（来共同区分链路。例如，有两条链路（i,j）和和（k，l）具有相同的重量，如果具有相同的重量，如果 i j ，k l且且有有i k，则选定链路（则选定链路（i,j）是具有最小重量的链是具有最小重量的链路。路。80 4.割集（割集（1 1）设图设图G=(V,E)是连通图。设是连通图。设S E，若从图若从图G中消去属于中消去属

45、于S的所有的边，图的所有的边，图 G S 变为一个非连通的。变为一个非连通的。如果去掉属于如果去掉属于S的任何的任何真子集中的边，图仍真子集中的边，图仍然保持连通，则称然保持连通，则称S是是图图G的一个的一个割集割集。也就。也就是说割集是说割集S是使连通图是使连通图G失去连通性的失去连通性的最小的最小的边的集合边的集合。81 4.割集（割集（2 2）所谓所谓饱和割集饱和割集是指链路利用率（负荷）非常高的割集。是指链路利用率（负荷）非常高的割集。例如图例如图1-24中与虚线对应边是一个割集，它同时也是中与虚线对应边是一个割集，它同时也是一个饱和割集。一个饱和割集。82 习习 题题 1.101.111.121.131.141.151.16