通信网络基础第一章精.ppt

通信网络基础第一章通信网络基础第一章第1页，本讲稿共82页1.3 通信网络中的数学基础通信网络中的数学基础 1.3.1 随机过程的基本概念随机过程的基本概念1.3.2 Poisson过程过程1.3.3 马尔可夫链马尔可夫链1.3.4 图论基础图论基础第2页，本讲稿共82页1.3 通信网络中的数学基础通信网络中的数学基础为为了了定定量量地地描描述述通通信信网网络络的的运运行行过过程程、设设计计通通信信网网络络的的体体系系结结构构和和评评估估通通信信网网络络容容量量、时时延延和和服服务务质质量量等等，我我们们需需要要了了解解网网络络中中每每个个链链路路、节节点点、交交换换机机/路路由由器器，用用户户终终端端等等设设备备的的输输入入输输出出业业务务流流的的行行为为特特征征和和处理过程处理过程。AEFDCB A(t)C(t)D(t)B(t)描述这些行为特征和处理过程的基本描述这些行为特征和处理过程的基本数学基础是数学基础是随机过程随机过程和和排队论排队论，描述网络，描述网络结构的基本方法是结构的基本方法是图论图论。本节主要讨论常。本节主要讨论常用的随机过程和图论基础，在第三章中用的随机过程和图论基础，在第三章中将详细讨论排队论的基本内容。将详细讨论排队论的基本内容。第3页，本讲稿共82页1.3.1 随机过程的基本概念（随机过程的基本概念（1 1）随机过程随机过程是用来描述在一个观察区间内某一实体（是用来描述在一个观察区间内某一实体（壶口壶口瀑布水的流量、食堂中的人数瀑布水的流量、食堂中的人数）的随机行为。）的随机行为。tttX(t)X(t)X(t)(1)(2)(n)例如例如:在通信系统中的噪声就是一个典型的随机过程。在通信系统中的噪声就是一个典型的随机过程。(n台性能完全相同的通信接收机的输出如下图。台性能完全相同的通信接收机的输出如下图。)第4页，本讲稿共82页1.3.1 随机过程的基本概念（随机过程的基本概念（2 2）随机过程是随机过程是随机变量随机变量概念在概念在时间域时间域上的延伸。直观地讲，随上的延伸。直观地讲，随机过程是时间机过程是时间t的的函数的集合函数的集合，在任一个观察时刻，随机过程，在任一个观察时刻，随机过程的取值是一个随机变量。或者说，的取值是一个随机变量。或者说，依赖于时间参数依赖于时间参数t的随机的随机变量所构成的总体称为随机过程变量所构成的总体称为随机过程。tttX(t)X(t)X(t)(1)(2)(n)t1X(t1)t2X(t2)第5页，本讲稿共82页1.3.1 随机过程的基本概念（随机过程的基本概念（3 3）设设X(t)是一个随机过程，则可以从两个方面来描述是一个随机过程，则可以从两个方面来描述X(t)的特征：的特征：一是一是在任意时刻在任意时刻t1，随机变量随机变量X(t1)的统计特征的统计特征，如一维分布函数，概，如一维分布函数，概率密度函数，均值和方差等。率密度函数，均值和方差等。二是二是同一随机过程在不同时刻同一随机过程在不同时刻t1和和t2对应的随机变量对应的随机变量X(t1)和和X(t2)的相的相关特性关特性，如多维联合分布函数、相关函数、协方差矩阵等。，如多维联合分布函数、相关函数、协方差矩阵等。tttX(t)X(t)X(t)(1)(2)(n)t1X(t1)t2X(t2)第6页，本讲稿共82页1.3.1 随机过程的基本概念（随机过程的基本概念（4 4）随机过程随机过程X(t)的的一维分布函数一维分布函数，定义为，定义为 （1-1）式中式中P表示概率。表示概率。如如果果Ft(x)对对x的的微微分分存存在在，则则X(t)的的一一维维概概率率密密度度函函数数定义为定义为 （1-2）第7页，本讲稿共82页1.3.1 随机过程的基本概念（随机过程的基本概念（5 5）通通常常一一维维分分布布函函数数不不能能完完全全描描述述随随机机过过程程的的特特征征，需需要要采采用用n维维联联合合分分布布函函数数。对对于于给给定定的的n个个时时刻刻t1，t2，tn，随随机机变变量量X(t1)，X(t2)，X(tn)的的联合分布函数为：联合分布函数为：（1-3）若若 则随机过程则随机过程X(t)的的均值函数均值函数为为 （1-4）第8页，本讲稿共82页1.3.1 随机过程的基本概念（随机过程的基本概念（6 6）若对任给的时刻若对任给的时刻t1和和t2，如下列函数，如下列函数 （1-5）存在，则称存在，则称CX(t1,t2)为为X(t)的的协方差函数协方差函数；（1-6）为为X(t)的的方差函数方差函数。第9页，本讲稿共82页1.3.1 随机过程的基本概念（随机过程的基本概念（7 7）若若对对任任给给的的时时间间t1和和t2，RX(t1,t2)=)=E E X(t1)X(t2)存存在在，则则 RX(t1,t2)为为X(t)的的自相关函数自相关函数。协方差函数，自相关函数、均值函数有下列关系：协方差函数，自相关函数、均值函数有下列关系：（1-7）第10页，本讲稿共82页1.3.1 随机过程的基本概念（随机过程的基本概念（8 8）下面介绍几类典型的随机过程：下面介绍几类典型的随机过程：1.独立随机过程独立随机过程2.马尔可夫马尔可夫(Markov)过程过程 3独立增量过程独立增量过程 4平隐随机过程平隐随机过程 5 Poisson过程过程 6 马尔可夫链马尔可夫链第11页，本讲稿共82页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)是是独独立立随随机机过过程程。该该过过程程的的特特点点是是任任意意一一时时刻刻的的状态与其他任何时刻的状态无关。状态与其他任何时刻的状态无关。第12页，本讲稿共82页2.马尔可夫马尔可夫(Markov)过程过程(1)(1)设有设有X(t)一个随机过程，如果对于一个任意的时间序列：一个随机过程，如果对于一个任意的时间序列：t1 t2 t0)所处的状态所处的状态与该过程在与该过程在t0时刻之前的状态无关。时刻之前的状态无关。式（式（1-9）右端的条件分布函数可以写成：）右端的条件分布函数可以写成：（1-10）该式称为马氏过程的该式称为马氏过程的转移概率转移概率。第14页，本讲稿共82页3独立增量过程独立增量过程 设设X(t2)-X(t1)=X(t1,t2)是随机过程是随机过程X(t)在时间间隔在时间间隔 t1,t2)上的增量，如果对于时间上的增量，如果对于时间t的任意的任意n个值个值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,tn-1)X(tn-1,tn)第15页，本讲稿共82页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+第16页，本讲稿共82页4平隐随机过程平隐随机过程(2)(2)按照上述定义的随机过程通常称为按照上述定义的随机过程通常称为严（狭义）平稳过程严（狭义）平稳过程。在实际应用中，我们更关心这样一类过程：其在实际应用中，我们更关心这样一类过程：其 （称为二阶矩过程），且满足下列条件：（称为二阶矩过程），且满足下列条件：1）均值均值为常量（与时间为常量（与时间t无关）；无关）；2）对于任意时刻）对于任意时刻s和和t，其，其相关函数相关函数满足满足 ，即相关函数仅与时差即相关函数仅与时差t-s有关，而与有关，而与s,t的取值无关；的取值无关；称这类过程为称这类过程为宽（广义）平稳过程宽（广义）平稳过程。在实际应用中所指的随。在实际应用中所指的随机过程通常是宽平稳过程。机过程通常是宽平稳过程。第17页，本讲稿共82页各态历经性各态历经性(1)(1)为了说明各态历经性，在时间轴上定义下列两种平均：为了说明各态历经性，在时间轴上定义下列两种平均：（1-12）（1-13）为随机过程的为随机过程的时间均值时间均值和和时间相关函数时间相关函数。-T 0 +Ttt第18页，本讲稿共82页各态历经性各态历经性(2)(2)如果如果X(t)是一个平稳过程，如果是一个平稳过程，如果=EX(t)=mx依概率依概率1成立（即对所有样本都成立），则称随成立（即对所有样本都成立），则称随机过程机过程X(t)的的均值具有各态历经性均值具有各态历经性；如果如果=EX(t)X(t+)=Rx()依依概率概率1成立，则称过程成立，则称过程X(t)的的自相关函数具有各态历自相关函数具有各态历经性；经性；如果如果X(t)的均值和自相关函数都具有各态历经性，的均值和自相关函数都具有各态历经性，则称则称X(t)是（宽）各态历经过程是（宽）各态历经过程，或者说，或者说X(t)是各态是各态历经的。历经的。第19页，本讲稿共82页1.3.2 Poisson过程过程(1)(1)在日常生活中，如果我们观察顾客进入商店、银行或其在日常生活中，如果我们观察顾客进入商店、银行或其它公共服务场所的过程，我们发现如果把一位顾客的到它公共服务场所的过程，我们发现如果把一位顾客的到达看成一个达看成一个“随机点随机点”，则这是一个源源不断出现，则这是一个源源不断出现随机点的随机点的过程过程。在这一过程中任一段时间内到达的顾客数也是随机的。在这一过程中任一段时间内到达的顾客数也是随机的。这类描述到达顾客数及其特征的过程通常称为这类描述到达顾客数及其特征的过程通常称为计数过程。计数过程。如果我们考察一个交换局中如果我们考察一个交换局中电话呼叫到达电话呼叫到达（人们拨打电话（人们拨打电话的行为中拿起电话并拨出对方号码的动作称为一次电话呼的行为中拿起电话并拨出对方号码的动作称为一次电话呼叫到达）的过程也具有类似的特征。叫到达）的过程也具有类似的特征。第20页，本讲稿共82页1.3.2 Poisson过程过程(2)(2)设一个随机过程为设一个随机过程为A(t),t 0的的取值为非负整数取值为非负整数，如果，如果该过程满足下列条件，则称该过程为到达率为该过程满足下列条件，则称该过程为到达率为 的的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是有周期性的。是有周期性的。非周期性如果马氏链中没有一个状态是有周期性的，则称该马氏链为非周期的。本课程仅考虑本课程仅考虑非周期不可约非周期不可约的马氏链。的马氏链。第43页，本讲稿共82页1.3.3 马尔可夫链马尔可夫链(12)(12)对于马氏链，其对于马氏链，其状态的稳态概率状态的稳态概率定义为：如果有定义为：如果有 （1-27）则称概率分布则称概率分布 是马氏链的是马氏链的稳态分布稳态分布。对于概率分布有对于概率分布有 。稳稳态态概概率率反反映映了了系系统统达达到到稳稳态态后后，系系统统处处于于某某一一状状态态的的可可能能性（概率）。性（概率）。第44页，本讲稿共82页1.3.3 马尔可夫链马尔可夫链(13)(13)稳态分布稳态分布可以表示为：可以表示为：（1-28）即过程从初始状态即过程从初始状态X0=i 出发，最终转移到状态出发，最终转移到状态Xn=j的概率。的概率。显然与初始状态显然与初始状态X0=i无关。无关。稳态分布稳态分布也可以表示为：（以概率也可以表示为：（以概率1成立）成立）（1-29）因此因此pj表示该过程中访问状态表示该过程中访问状态j的时间比例或频率，且该频率的时间比例或频率，且该频率与初始状态无关。与初始状态无关。第45页，本讲稿共82页1.3.3 马尔可夫链马尔可夫链(14)(14)该该式式称称为为全全局局平平衡衡方方程程(Global balance equations)。它它表表示示在在稳稳态态情情况况下下，从从一一个个状状态态j转转移移出出去去的的频频率率（式式（1-30）左左边边）等等于于转转移移进进入入状状态态j的的频频率率（式式（1-30）的的右右边边）。该该方方程提供给我们一种典型的求解稳态概率分布的方法。程提供给我们一种典型的求解稳态概率分布的方法。由于由于 ，则结合式（，则结合式（1-27）有）有 （1-30）第46页，本讲稿共82页1.3.3 马尔可夫链马尔可夫链(15)(15)例例1.2（续续）求随机游走过程的稳态概率。）求随机游走过程的稳态概率。在在例例1.2中中我我们们已已知知各各种种状状态态的的转转移移概概率率矩矩阵阵，设设状状态态a5,a4,a3,a2,a1的的稳稳态态概概率率为为p5,p4,p3,p2和和p1，则则我我们们根根据式（据式（1-27）可得稳态概率的方程为：）可得稳态概率的方程为：第47页，本讲稿共82页1.3.3 马尔可夫链马尔可夫链(16)(16)例例1.2（续续）求随机游走过程的稳态概率。）求随机游走过程的稳态概率。由于由于 是稳态概率分布，则有是稳态概率分布，则有 （1-32）求求解解式式(1-31)和和式式(1-32)组组成成的的方方程程组组，得得稳稳态态概概率分布为：率分布为：（1-33）第48页，本讲稿共82页生灭（生灭（birth-death）过程）过程(1)(1)在实际中，我们经常遇到这样一类特殊的马氏过程：在实际中，我们经常遇到这样一类特殊的马氏过程：仅有相邻状态的转移，而没有其它状态的转移（即如仅有相邻状态的转移，而没有其它状态的转移（即如果果 ，则，则 ），如图），如图1-15所示。这一所示。这一类过程通常称为类过程通常称为生灭（生灭（birth-death）过程）过程。第49页，本讲稿共82页生灭（生灭（birth-death）过程）过程(2)(2)它它表表示示一一个个群群体体（动动物物、生生物物等等）总总数数为为n的的特特殊殊状状态态转转移移过过程程。该该群群体体总总数数的的状状态态转转移移只只有有三三种种可可能能：或或者者从从n增增加加一一个个（群群体体出出生生一一个个），或或者者从从n减减少少一一个个（死死亡亡一一个个），或或者者群群体体的的总总数数n保保持持不不变变。而而其其它它所所有有可可能能的的转转移移相相对对前前三三种种转转移移都都是是高高阶阶无无穷穷小小，因因而而可可以以忽忽略略不不计计。该该群群体体状状态的转移概率取决于群体的总数态的转移概率取决于群体的总数n（状态）。（状态）。第50页，本讲稿共82页生灭（生灭（birth-death）过程）过程(3)(3)令令 ，则应用式（，则应用式（1-30）可得：）可得：（1-35）它表示在稳态的情况下，从它表示在稳态的情况下，从状态状态n转移到状态转移到状态n+1的频率等的频率等于从状态于从状态n+1转移到状态转移到状态n的频率的频率，或在状态转移图中设置一，或在状态转移图中设置一个虚拟的平面（图个虚拟的平面（图1-15中的虚线），则进入该平面的频率等于中的虚线），则进入该平面的频率等于退出该平面的频率，即该平面是系统的一个稳定点。退出该平面的频率，即该平面是系统的一个稳定点。第51页，本讲稿共82页生灭（生灭（birth-death）过程）过程(2)令状态空间为令状态空间为，详细平衡方程详细平衡方程第52页，本讲稿共82页生灭（生灭（birth-death）过程）过程(3)详细平衡方程详细平衡方程 local balance equations求解稳态概率求解稳态概率第53页，本讲稿共82页1.3.3 马尔可夫链马尔可夫链(16)(16)上式可推广到一个更一般的形式：上式可推广到一个更一般的形式：（1-36）该等式称为该等式称为详细平衡方程详细平衡方程（detailed balance equation）。）。如果对于一个过程，有式（如果对于一个过程，有式（1-36）成立，则意味着有式）成立，则意味着有式（1-30）全局平衡方程存在。但并不是任何马尔可夫链）全局平衡方程存在。但并不是任何马尔可夫链都必须有式（都必须有式（1-36）成立。但在很多实际应用中，式）成立。但在很多实际应用中，式（1-36）是成立的。因此实际中，我们可以先假设式）是成立的。因此实际中，我们可以先假设式（1-36）成立，然后通过它们求解稳态概率）成立，然后通过它们求解稳态概率 pj,j。如果求得的结果满足如果求得的结果满足 ，则求得的分布，则求得的分布 pj,j就是满足式（就是满足式（1-27）的稳态分布。）的稳态分布。第54页，本讲稿共82页生灭（生灭（birth-death）过程）过程(4)(4)例例1.3 设一个特殊的生灭过程的状态转移概率为设一个特殊的生灭过程的状态转移概率为 试求其稳态分布。试求其稳态分布。解：解：利用式（利用式（1-35）（或假设式（）（或假设式（1-36）成立）有：）成立）有：从而有：从而有：式中式中 经过递推得：经过递推得：第55页，本讲稿共82页生灭（生灭（birth-death）过程）过程(5)(5)显然只有在显然只有在 的情况下，才可能有下式成立。的情况下，才可能有下式成立。从而可得从而可得 。进而可得：。进而可得：综上可得，在综上可得，在 的情况下，该生灭过程的稳态分的情况下，该生灭过程的稳态分布为布为第56页，本讲稿共82页1.3.4 图论基础图论基础 在通信网络中，许多问题的描述都是基于图论的，因此，我在通信网络中，许多问题的描述都是基于图论的，因此，我们下面对图论的一些基本概念进行讨论。其实我们已应用了们下面对图论的一些基本概念进行讨论。其实我们已应用了图的很多概念。图的很多概念。例如：例如：AEFDCB第57页，本讲稿共82页1.图的概念（图的概念（1 1）一般几何上将一般几何上将图图定义成空间中一些定义成空间中一些点点（顶点）和连接这些（顶点）和连接这些点的点的线线（边）的（边）的集合集合。图论中将图定义为图论中将图定义为G=(V,E)，其中，其中V表示顶点的集合，表示顶点的集合，E表示边的集合。表示边的集合。例如例如：如图：如图1-16所示的图可所示的图可以表示为：以表示为：第58页，本讲稿共82页1.图的概念（图的概念（2 2）我我们们也也可可以以用用边边的的两两个个顶顶点点来来表表示示边边。如如果果边边e的的两两个个顶顶点点是是u和和v，那那么么e可可写写成成 e=(u,v)，这这里里（u,v）表表示示u和和v的的有序对有序对。如如果果有有（u,v）和和（v,u）同同时时存存在在，它它表表达达了了以以u，v为为端端点点的的一一条条无无向向边边。如如果果图图中中的的所所有有边边都都是是无无向向边边，则则称称该该图图为为无无向图向图。uveuve这这样样，我我们们也也可可以以这这样样来来表表示示无无向向图图1-16。G=(V,E),第59页，本讲稿共82页1.图的概念（图的概念（3 3）一般图一般图G=(V,E)的顶点数用的顶点数用 表示，边的数目表示，边的数目 用用 表示。若表示。若 和和 都是有限的，则称图都是有限的，则称图G是是有限图有限图，否则称为无限图。本书只讨论有限图的情，否则称为无限图。本书只讨论有限图的情况。况。第60页，本讲稿共82页1.图的概念（图的概念（4 4）在实际应用中，图中每条边可能有一个方向是很自然的（它在实际应用中，图中每条边可能有一个方向是很自然的（它反映了信息或物质的流向）。当给图反映了信息或物质的流向）。当给图G的每一条边都规定一的每一条边都规定一个方向，则称该图为个方向，则称该图为有向图有向图。对有向图图。对有向图图G=(V,E)，有向，有向边边e用与其关联的顶点（用与其关联的顶点（u，v）的有序对来表示，即，它表示）的有序对来表示，即，它表示u为边为边e的起点，的起点，v为边为边e的终点。那么图的终点。那么图1-17所示的有向图可表所示的有向图可表示如下：示如下：第61页，本讲稿共82页1.图的概念（图的概念（5 5）如果顶点如果顶点v是边是边e的一个端点，则称边的一个端点，则称边e和顶点和顶点v相相关联关联（incident）；对于顶点）；对于顶点u和和v，若，若 ，则称，则称u和和v是是邻接邻接的（的（adjacent）。在图）。在图1-16中，边中，边e2，e4，e5都与顶都与顶点点v4相关联，相关联，v4分别与分别与v1，v2，v3相邻接。若两条边有共相邻接。若两条边有共同的顶点，则称这两条边是邻接的。在图同的顶点，则称这两条边是邻接的。在图1-16中，边中，边e1，e2，e3两两相邻接。两两相邻接。第62页，本讲稿共82页1.图的概念（图的概念（6 6）对图对图G=(V,E)和和G=(V,E)来说，若有来说，若有 和和 ，则称图，则称图 G是图是图G的一个的一个子图子图；若；若 或或 ，则，则称图称图G是图是图G的一个的一个真子图真子图。第63页，本讲稿共82页2 2 路径与回路路径与回路(1)(1)如果路径如果路径 中有中有v0=vk ，则，则 为为回路回路（或（或环环Cycle），回路中没），回路中没有重复边时称为有重复边时称为简单回路简单回路。定定义义：图图的的一一些些顶顶点点和和边边的的交交替替序序列列 ，且且边边ei的的端端点点为为vi-1和和vi，i=1,2,3,k，则则称称 为为一一条条路路径径（Path），v0和和vk分分别别为为 的的起起点点和和终终点点。如如果果 中中所所有有的的边边均均不不相相同同，则则称称其其为为简简单单路路径径。以以v0为为起起点，点，vk为终点的路径称为为终点的路径称为v0vk路径。路径。对于有向图也有类似定义路径、回路的概念，只不过此对于有向图也有类似定义路径、回路的概念，只不过此时需要考虑方向性。时需要考虑方向性。第64页，本讲稿共82页2 2 路径与回路路径与回路(2)(2)例例4：在图在图1-18中，中，是一路径，是一路径，是一回路是一回路.第65页，本讲稿共82页2 2 路径与回路路径与回路(3)(3)定定义义：对对图图G=(V,E)来来说说，若若G的的两两个个顶顶点点u，v之之间间存存在在一一条条路路径径，则则称称u和和v是是连连通通的的；若若图图G的的任任意意两两个个顶顶点点都都是是连连通通的的，则则称称图图G是是连连通通的的；否否则则是是非非连连通通的的。非非连连通通的图可分解为若干连通的子图。的图可分解为若干连通的子图。第66页，本讲稿共82页2 2 路径与回路路径与回路(4)(4)图图1-19的无方向图中，图（的无方向图中，图（a）中任意两个顶点之间都有）中任意两个顶点之间都有路径，所以该图是连通的；图（路径，所以该图是连通的；图（b）中顶点）中顶点3和图中其它顶和图中其它顶点之间没有路径，所以该图是非连通的；图（点之间没有路径，所以该图是非连通的；图（c）则是一个）则是一个孤立的节点。孤立的节点。第67页，本讲稿共82页2 2 路径与回路路径与回路(5)(5)对于有向图，若边对于有向图，若边去掉方向后是连通的去掉方向后是连通的，则称该图为连通的，则称该图为连通的有向图。若对于有向图的任意两个顶点有向图。若对于有向图的任意两个顶点u和和v之间存在之间存在u到到v的的路径和路径和v到到u的路径时，称该图为的路径时，称该图为强连通强连通的。的。图图1-20（a）的有向图是一）的有向图是一个连通的有向图，但不是个连通的有向图，但不是强连通的。因为顶点强连通的。因为顶点2和和顶点顶点3之间不存在双向的之间不存在双向的路径；图路径；图1-20（b）是一）是一个强连通的图，该图中任个强连通的图，该图中任意两个顶点之间都存在双意两个顶点之间都存在双向的路径。向的路径。第68页，本讲稿共82页3.生成树和最小重量生成树（生成树和最小重量生成树（1 1）定义：不包括回路（环）的连通图，称为定义：不包括回路（环）的连通图，称为树树。定义：对于图，包含了图定义：对于图，包含了图G中所有顶点的树称为中所有顶点的树称为生成树生成树（Spanning Tree）。在图在图1-21中，图（中，图（b）、（）、（c）和（）和（d）都是树。而图（）都是树。而图（a）由）由于有回路，所以不是树。在图于有回路，所以不是树。在图1-21中，图（中，图（b）和图（）和图（c）都是）都是图（图（a）的生成树。）的生成树。第69页，本讲稿共82页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）步。）步。nEFDCBV=n,E=nEFDCBVnEFDCB第70页，本讲稿共82页3.生成树和最小重量生成树（生成树和最小重量生成树（3 3）该算法是从该算法是从仅有一个顶点、仅有一个顶点、0条边的子图条边的子图开始，以后每开始，以后每执行一次第执行一次第3）步就增加一个顶点和一条边。这就意味着）步就增加一个顶点和一条边。这就意味着最终生成的树有个最终生成的树有个 节点，节点，1条链路。条链路。通常对于一个连通图，其边的条数大于等于通常对于一个连通图，其边的条数大于等于 -1-1。如果一个图。如果一个图G的边的数目等于的边的数目等于 1，则上，则上述算法将使用该图中所有的边，因而有述算法将使用该图中所有的边，因而有G=G，即，即此时图此时图G本身就是一颗树。本身就是一颗树。第71页，本讲稿共82页3.生成树和最小重量生成树（生成树和最小重量生成树（4 4）一般而言，对于一个图可以一般而言，对于一个图可以有很多个生成树。有很多个生成树。对于通信网络来说，利用生成树来实现对于通信网络来说，利用生成树来实现广播广播是比较经济的。但每一条边的成本或时延通是比较经济的。但每一条边的成本或时延通常是不相同的，这时就要考虑树中各边的重常是不相同的，这时就要考虑树中各边的重量（成本或时延）。通常我们用量（成本或时延）。通常我们用Wij表示边表示边（i,j）的重量。）的重量。nEFDCBnEFDCBnEFDCB231152164最小重量生成树最小重量生成树（MST，Minimum Weight Spanning Tree）：是指边的重量和）：是指边的重量和最小的生成树。最小的生成树。第72页，本讲稿共82页3.生成树和最小重量生成树（生成树和最小重量生成树（5 5）MST的任一个子树称为一个的任一个子树称为一个树枝树枝（fragment）。（注意：一个顶点本身就）。（注意：一个顶点本身就是自己的一个树枝）。是自己的一个树枝）。输出链路输出链路（Outgoing Arc）是指该链路）是指该链路的一个端点在的一个端点在fragment内，而另一个内，而另一个端点不在该端点不在该fragment内。这里所谓的链内。这里所谓的链路和我们讨论的图的边的概念是等效路和我们讨论的图的边的概念是等效的。的。下面我们讨论对于一个给定的图，如何构下面我们讨论对于一个给定的图，如何构造该图的最小重量生成树（造该图的最小重量生成树（MST）。）。nEFDCB树树枝枝输出链路输出链路第73页，本讲稿共82页3.生成树和最小重量生成树（生成树和最小重量生成树（6 6）nEFDCB树树枝枝输出链路输出链路定理定理1：给定一个给定一个fragmentF，令，令 =（i,j），j 是是的最小重量输出链路，的最小重量输出链路，将将扩展一条链路扩展一条链路 和一个顶点和一个顶点，仍是，仍是一个一个fragment。nEFDCB231152164该定理告诉我们如何从该定理告诉我们如何从MST的一个子树生成的一个子树生成一个完整的一个完整的MST。根据该定理可以有下列三种构造根据该定理可以有下列三种构造MST的方法的方法（以图（以图1-22（a）为例）。）为例）。第74页，本讲稿共82页(1)Prim-Dijkstra(1)Prim-Dijkstra算法算法 选择任意一个顶点作为一选择任意一个顶点作为一个个fragment，然后根据定，然后根据定理理1，每次选择一条具有最，每次选择一条具有最小重量的输出链路来扩展小重量的输出链路来扩展fragment，最终即可生成，最终即可生成MST，如图，如图1-22（b）所）所示。示。第75页，本讲稿共82页(2)Kruskal算法算法 选择所有的顶点作为单顶点的选择所有的顶点作为单顶点的fragment，在所有的链路中选，在所有的链路中选择具有最小重量且不会形成择具有最小重量且不会形成回路（环）的链路添加到当回路（环）的链路添加到当前的前的fragment中。每次迭代中。每次迭代仅添加一条链路。最终即可仅添加一条链路。最终即可生成生成MST，如图，如图1-22(c)所示。所示。第76页，本讲稿共82页(3)(3)分布式构造分布式构造MST算法算法(1)(1)假假定定网网络络中中仅仅有有惟惟一一一一个个MST.从从一一个个fragment集集（例例如如：该集就是图中的某一个顶点）开始该集就是图中的某一个顶点）开始:a).a).每每个个fragment决决定定它它自自己己的的最最小小重重量量输输出出链链路路，将将该该链链路路添加到自身的添加到自身的fragment中，并通知该输出链路的另一个端点。中，并通知该输出链路的另一个端点。b).b).只只要要连连接接两两个个fragment的的链链路路的的确确是是某某个个fragment的的最最小小重重量量输输出出链链路路，则则所所有有时时间间内内，算算法法都都维维持持着着MST的的fragment集集，并且不会形成回路（环）并且不会形成回路（环）c).c).继继续续算算法法，添添加加新新的的链链路路，直直至至没没有有新新的的输输出出链链路路，且且只只有有一个一个fragment（即（即MST）为止。）为止。第77页，本讲稿共82页(3)(3)分布式构造分布式构造MST算法算法(2)(2)上述分布式算法要求上述分布式算法要求MST是惟一的；如果不惟一，则可是惟一的；如果不惟一，则可能会引起闭环。能会引起闭环。例如，有一个网络如图例如，有一个网络如图1-23所示。所示。从三个顶点开始构造从三个顶点开始构造MST，则，则可能会出现三个顶点同时加入可能会出现三个顶点同时加入（1,2）、（）、（2,3）和（）和（3,1）三条）三条链路，从而形成一个闭环。这个链路，从而形成一个闭环。这个例子中，三条链路的重量是不可例子中，三条链路的重量是不可区分的。区分的。第78页，本讲稿共82页3.生成树和最小重量生成树（生成树和最小重量生成树（7 7）定理定理2 如果图如果图G中中所有链路的重量是不同的所有链路的重量是不同的，则仅有惟一，则仅有惟一的一个的一个MST。在实际的网络中，对于具有相同重量的链路，可以在实际的网络中，对于具有相同重量的链路，可以采用采用链路重量以及链路关联的两个顶点的标号链路重量以及链路关联的两个顶点的标号来共同来共同区分链路。例如，有两条链路（区分链路。例如，有两条链路（i,j）和（）和（k，l）具）具有相同的重量，如果有相同的重量，如果 i j ，k l且有且有i k，则选定，则选定链路（链路（i,j）是具有最小重量的链路。）是具有最小重量的链路。第79页，本讲稿共82页4.割集（割集（1 1）设图设图G=(V,E)是连通图。设是连通图。设S E，若从图，若从图G中消去属于中消去属于S的所的所有的边，图有的边，图 G S 变为一个非连通的。变为一个非连通的。如果去掉属于如果去掉属于S的任何真的任何真子集中的边，图仍然保子集中的边，图仍然保持连通，则称持连通，则称S是图是图G的的一个一个割集割集。也就是说割集。也就是说割集S是使连通图是使连通图G失去连通失去连通性的性的最小的边的集合最小的边的集合。第80页，本讲稿共82页4.割集（割集（2 2）所谓所谓饱和割集饱和割集是指链路利用率（负荷）非常高的割集。例如图是指链路利用率（负荷）非常高的割集。例如图1-24中与虚线对应边是一个割集，它同时也是一个饱和割集。中与虚线对应边是一个割集，它同时也是一个饱和割集。第81页，本讲稿共82页习习 题题 1.101.111.121.131.141.151.16第82页，本讲稿共82页