通信网络基础第一章

通信网络基础第一章第1页，课件共82页，创作于2023年2月1.3通信网络中的数学基础

1.3.1随机过程的基本概念1.3.2Poisson过程1.3.3马尔可夫链1.3.4图论基础第2页，课件共82页，创作于2023年2月1.3通信网络中的数学基础为了定量地描述通信网络的运行过程、设计通信网络的体系结构和评估通信网络容量、时延和服务质量等，我们需要了解网络中每个链路、节点、交换机/路由器，用户终端等设备的输入输出业务流的行为特征和处理过程。AEFDCBA(t)C(t)D(t)B(t)描述这些行为特征和处理过程的基本数学基础是随机过程和排队论，描述网络结构的基本方法是图论。本节主要讨论常用的随机过程和图论基础，在第三章中将详细讨论排队论的基本内容。第3页，课件共82页，创作于2023年2月1.3.1随机过程的基本概念（1）

随机过程是用来描述在一个观察区间内某一实体（壶口瀑布水的流量、食堂中的人数）的随机行为。tttX(t)X(t)X(t)(1)(2)(n)•••例如:在通信系统中的噪声就是一个典型的随机过程。(n台性能完全相同的通信接收机的输出如下图。)第4页，课件共82页，创作于2023年2月1.3.1随机过程的基本概念（2）随机过程是随机变量概念在时间域上的延伸。直观地讲，随机过程是时间t的函数的集合，在任一个观察时刻，随机过程的取值是一个随机变量。或者说，依赖于时间参数t的随机变量所构成的总体称为随机过程。tttX(t)X(t)X(t)(1)(2)(n)•••t1X(t1)t2X(t2)第5页，课件共82页，创作于2023年2月1.3.1随机过程的基本概念（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页，创作于2023年2月1.3.1随机过程的基本概念（4）随机过程X(t)的一维分布函数，定义为

（1-1）式中P{}表示概率。如果Ft(x)对x的微分存在，则X(t)的一维概率密度函数定义为

（1-2）

第7页，课件共82页，创作于2023年2月1.3.1随机过程的基本概念（5）通常一维分布函数不能完全描述随机过程的特征，需要采用n维联合分布函数。对于给定的n个时刻t1，t2，…

，tn，随机变量X(t1)，X(t2)，…，X(tn)的联合分布函数为：

（1-3）

若则随机过程X(t)的均值函数为

（1-4）

第8页，课件共82页，创作于2023年2月1.3.1随机过程的基本概念（6）若对任给的时刻t1和t2，如下列函数

（1-5）存在，则称CX(t1,t2)为X(t)的协方差函数；

（1-6）为X(t)的方差函数。第9页，课件共82页，创作于2023年2月1.3.1随机过程的基本概念（7）若对任给的时间t1和t2，RX(t1,t2)=E[X(t1)X(t2)]存在，则RX(t1,t2)为X(t)的自相关函数。协方差函数，自相关函数、均值函数有下列关系：

（1-7）

第10页，课件共82页，创作于2023年2月1.3.1随机过程的基本概念（8）下面介绍几类典型的随机过程：1.独立随机过程2.马尔可夫(Markov)过程

3．独立增量过程

4．平隐随机过程

5．Poisson过程

6．马尔可夫链第11页，课件共82页，创作于2023年2月1.独立随机过程

设有一个随机过程X(t)，如果对任意给定的时刻t1，t2，…

，tn，随机变量X(t1),X(t2),…,X(tn)是相互独立的，也就是其n维分布函数可以表示为：

t1

t2t3tn-2tn-1tnX(t)t（1-8）则称X(t)是独立随机过程。该过程的特点是任意一时刻的状态与其他任何时刻的状态无关。第12页，课件共82页，创作于2023年2月2.马尔可夫(Markov)过程(1)

设有X(t)一个随机过程，如果对于一个任意的时间序列：t1<t2<…

<tn，n

3，在给定随机变量的X(t1)=x1

,X(t2)=x2

,…,X(tn-1)=xn-1条件下,X(tn)=xn

的分布可以表示为：

t1

t2t3tn-2tn-1tnX(t)tx1x2x3xn-2xn-1X(tn)=xn（1-9）则称X(t)为马尔可夫过程或简称为马氏过程。第13页，课件共82页，创作于2023年2月2.马尔可夫(Markov)过程(2)该过程的基本特点是无后效性。即当该过程在t0时刻的状态为已知的条件下，则该过程在t(>t0)所处的状态与该过程在t0时刻之前的状态无关。式（1-9）右端的条件分布函数可以写成：

（1-10）该式称为马氏过程的转移概率。

第14页，课件共82页，创作于2023年2月3．独立增量过程

设X(t2)-X(t1)=X(t1,t2)是随机过程X(t)在时间间隔[t1,t2)上的增量，如果对于时间t的任意n个值0t1<t2<…

<tn

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

t2t3tn-2tn-1tnX(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页，创作于2023年2月4．平隐随机过程(1)

如果对于时间t的任意n个值t1，t2，…

，tn和任意实数，随机过程X(t)的n维分布函数满足关系式：

（1-11）则称X(t)为平稳随机过程或简称为平稳过程。该过程的特点是随机过程的统计特性不随时间的平移而变化。t1

t2t3tn-2tn-1tnX(t)tt1+

t2+

t3+

tn-2+

tn-1+

tn+

第16页，课件共82页，创作于2023年2月4．平隐随机过程(2)按照上述定义的随机过程通常称为严（狭义）平稳过程。在实际应用中，我们更关心这样一类过程：其（称为二阶矩过程），且满足下列条件：1）均值为常量（与时间t无关）；2）对于任意时刻s和t，其相关函数满足，即相关函数仅与时差t-s有关，而与s,t的取值无关；称这类过程为宽（广义）平稳过程。在实际应用中所指的随机过程通常是宽平稳过程。第17页，课件共82页，创作于2023年2月各态历经性(1)

为了说明各态历经性，在时间轴上定义下列两种平均：

（1-12）

（1-13）为随机过程的时间均值和时间相关函数。-T0+Ttt第18页，课件共82页，创作于2023年2月各态历经性(2)如果X(t)是一个平稳过程，如果<X(t)>=E[X(t)]=mx依概率1成立（即对所有样本都成立），则称随机过程X(t)的均值具有各态历经性；如果<X(t)X(t+)>=E[X(t)X(t+)]=Rx()依概率1成立，则称过程X(t)的自相关函数具有各态历经性；如果X(t)的均值和自相关函数都具有各态历经性，则称X(t)是（宽）各态历经过程，或者说X(t)是各态历经的。第19页，课件共82页，创作于2023年2月1.3.2Poisson过程(1)

在日常生活中，如果我们观察顾客进入商店、银行或其它公共服务场所的过程，我们发现如果把一位顾客的到达看成一个“随机点”，则这是一个源源不断出现随机点的过程。在这一过程中任一段时间内到达的顾客数也是随机的。这类描述到达顾客数及其特征的过程通常称为计数过程。如果我们考察一个交换局中电话呼叫到达（人们拨打电话的行为中拿起电话并拨出对方号码的动作称为一次电话呼叫到达）的过程也具有类似的特征。第20页，课件共82页，创作于2023年2月1.3.2Poisson过程(2)设一个随机过程为{A(t),t0}的取值为非负整数，如果该过程满足下列条件，则称该过程为到达率为的Poisson(泊松)过程。(1)A(t)是一个计数过程，它表示在[0,t）区间内到达的用户总数，A(0)=0,

A(t)的状态空间为{0,1,2,…}。如图1-12所示。任给两个时刻s和t，且s<t，则A(t)-A(s)即为[s,t)之间到达的用户总数。第21页，课件共82页，创作于2023年2月1.3.2Poisson过程(3)(2)A(t)是一个独立增量过程。即在两个不同时间区间（区间不重叠）内到达的用户数是相互独立的。由于在区间内平均到达的用户数为，则即为单位时间平均到达的用户数或称为到达率。(3)任一个长度为的区间内，到达的用户数服从参数为的Poisson分布，即

（1-14）其均值和方差均为。第22页，课件共82页，创作于2023年2月1.3.2Poisson过程(4)Poisson过程的基本特征有：（1）到达时间间隔n=tn+1-tn相互独立，且服从指数分布，其概率密度函数为

（1-15）其分布函数为

（1-16）该特性说明Poisson过程的到达间隔服从指数分布。相反，如果一个计数过程的到达间隔序列是相互独立同分布，其分布是参数为的指数分布，则该过程是到达率为的Poisson过程。因此，说“顾客到达过程为到达率为的Poisson过程”与说“顾客到达间隔相互独立且服从参数为的指数分布”是等价的。第23页，课件共82页，创作于2023年2月（2）对于一个任意小的区间0，将Poisson分布用Taylor级数展开，即利用

（1-17）可得：

（1-18）（1-19）（1-20）式中，o()表示的高阶无穷小，即。第24页，课件共82页，创作于2023年2月1.3.2Poisson过程(6)（3）多个相互独立的Poisson过程之和

A=A1+A2+…+Ak仍是一个Poisson过程，其到达率为=1+2+…+k，式中k是Poisson过程Ak的到达率。

第25页，课件共82页，创作于2023年2月1.3.2Poisson过程(6)（4）如果将一个Poisson过程的到达以概率p和1-p独立地分配给两个子过程，则这两个子过程也是Poisson过程。注意:这里是将到达独立地进行分配。如果把到达交替的分配给两个子过程，即两个子过程分别由奇数号到达和偶数号到达组成，则这两个子过程就不是Poisson过程。

第26页，课件共82页，创作于2023年2月1.3.2Poisson过程(6)例1.1有红、绿、蓝三种颜色的汽车，分别以强度为R、G、B的Poisson流到达某哨卡，设它们是相互独立的。把汽车合并成单个输出过程（假设汽车长度为0）。RBG第27页，课件共82页，创作于2023年2月1.3.2Poisson过程(7)（1）求两辆汽车之间的时间间隔的概率密度函数；tZC解:由于独立的Poisson过程之和仍为Poisson过程(特征（4）)，且其强度为C=R+G+B。设为两辆汽车到达的时间间隔ZC，则其概率密度函数为:合成的过程的特性？第28页，课件共82页，创作于2023年2月1.3.2Poisson过程(7)（2）求在t0时刻观察到一辆红色汽车，下一辆汽车将是(a)红的，(b)蓝的，(c)非红的概率；tt0(a)tt0tt0RX=G+BZRZX=+ZX第29页，课件共82页，创作于2023年2月1.3.2Poisson过程(8)（2）求在t0时刻观察到一辆红色汽车，下一辆汽车将是(a)红的，(b)蓝的，(c)非红的概率；tt0tt0BY=G+RZBZY=+tt0(b)第30页，课件共82页，创作于2023年2月1.3.2Poisson过程(9)tt0tt0or(c)（2）求在t0时刻观察到一辆红色汽车，下一辆汽车将是(a)红的，(b)蓝的，(c)非红的概率；第31页，课件共82页，创作于2023年2月1.3.2Poisson过程(10)（3）求在t0时刻观察到一辆红色汽车，下三辆汽车是红的，然后又是一辆非红色汽车将到达的概率。tt0tt0or第32页，课件共82页，创作于2023年2月1.3.3马尔可夫链(1)

马尔可夫（Markov）链是最简单的马氏过程－即时间和状态过程的取值参数都是离散的马氏过程。{X(t1),X(t2),X(t3),…,X(tn),…}t状态Xt1t2t3t4t5tn-1tntn+1状态转移时刻第33页，课件共82页，创作于2023年2月1.3.3马尔可夫链(2)

（1-21）

我们把可列个发生状态转移（变化）的时刻记为t1，t2，…,tn，…，在tn时刻发生的转移称为第n次转移；并且假定在每一个时刻tn(n=1,2,…),Xn=X(tn)所有可能的状态的集合S是可数的.对应于时间序列t1，t2，…,tn，…，马氏链的状态序列为i1，i2，…,in，…，。这时对应于式（1-9）（马氏过程的概率分布）有马氏链的转移概率为：该式表示在Xn-1=in-1的条件下，第n次转移出现in的概率。

第34页，课件共82页，创作于2023年2月1.3.3马尔可夫链(3)如转移概率与n无关（即与哪一次转移无关，仅与转移前后的状态有关），则该马氏链为齐次马氏链；否则称为非齐次马氏链。本书仅讨论齐次马氏链。上式称为马氏链的（一步）转移概率。Pij满足下列条件：

（1-23）（1-22）此时式（1-21）可以表示为第35页，课件共82页，创作于2023年2月1.3.3马尔可夫链(4)相应的转移概率矩阵可以表示为：(1-24)第36页，课件共82页，创作于2023年2月1.3.3马尔可夫链(5)例1.2设一盲人（或看成一个随机点）在如图1-13所示的线段上游走，其步长为l。假定他只能在a1=2l，a2=l，a3=0，a4=-l，a5=-2l这5个点上停留，且只在时刻t=1,2,…上发生游走。游走的规则是：如果游走前他在a2，a3，a4这几个点上，那末就分别以1/2的概率向左或向右走动一步；如果游走前他在a1(a5)上，那末就以概率1走到a2(a4)点上。第37页，课件共82页，创作于2023年2月1.3.3马尔可夫链(6)以Xn=ai,i=1,2,3,4,5表示在t=n时刻盲人位于停留点ai处，则容易看出X1,X2,…是一个马氏链，且他游走的转移概率矩阵为：第38页，课件共82页，创作于2023年2月1.3.3马尔可夫链(7)如果用图来表示这一转移过程，则可得图1-14。图中的圆圈表示马氏过程的状态，图中带箭头的弧线表示状态的转移，弧线上的数字表示一步转移概率。该图称为马氏过程的状态转移图。

第39页，课件共82页，创作于2023年2月1.3.3马尔可夫链(8)它表示当前（第m步）的状态为i，经过n步转移后（第n+m步）系统的状态为j的概率。在考察马氏过程中，我们还经常用到n步转移概率，即

（1-25）第40页，课件共82页，创作于2023年2月1.3.3马尔可夫链(9)系统中n=m1+m2步状态转移概率可用下式来求解：

（1-26）该公式称为Chapman—Kolmogorov等式。ijkm1步m2步第41页，课件共82页，创作于2023年2月1.3.3马尔可夫链(10)根据n步转移概率，就可以来定义马氏链状态转移的特性。如果马氏链的两个状态i和j有下列特性：即存在整数n和n’

有及（也就是从状态i(j)经过n（n’）步转移到状态j(i)的概率大于0），则称i和j是互通的。如果马氏链的所有状态都是互通的，则该马氏链是不可约的(irreducible)。

第42页，课件共82页，创作于2023年2月1.3.3马尔可夫链(10)周期性与非周期性周期性存在某个整数d>1，并仅当n为d的整倍时有则状态i是有周期性的。非周期性 如果马氏链中没有一个状态是有周期性的，则称该马氏链为非周期的。本课程仅考虑非周期不可约的马氏链。第43页，课件共82页，创作于2023年2月1.3.3马尔可夫链(12)对于马氏链，其状态的稳态概率定义为：如果有

（1-27）则称概率分布是马氏链的稳态分布。对于概率分布有。稳态概率反映了系统达到稳态后，系统处于某一状态的可能性（概率）。第44页，课件共82页，创作于2023年2月1.3.3马尔可夫链(13)稳态分布可以表示为：

（1-28）即过程从初始状态X0=i出发，最终转移到状态Xn=j的概率。显然与初始状态X0=i无关。稳态分布也可以表示为：（以概率1成立）

（1-29）因此pj表示该过程中访问状态j的时间比例或频率，且该频率与初始状态无关。第45页，课件共82页，创作于2023年2月1.3.3马尔可夫链(14)该式称为全局平衡方程(Globalbalanceequations)。它表示在稳态情况下，从一个状态j转移出去的频率（式（1-30）左边）等于转移进入状态j的频率（式（1-30）的右边）。该方程提供给我们一种典型的求解稳态概率分布的方法。由于，则结合式（1-27）有

（1-30）第46页，课件共82页，创作于2023年2月1.3.3马尔可夫链(15)例1.2（续）求随机游走过程的稳态概率。在例1.2中我们已知各种状态的转移概率矩阵，设状态a5,a4,a3,a2,a1的稳态概率为p5,p4,p3,p2和p1，则我们根据式（1-27）可得稳态概率的方程为：第47页，课件共82页，创作于2023年2月1.3.3马尔可夫链(16)例1.2（续）求随机游走过程的稳态概率。由于是稳态概率分布，则有

（1-32）求解式(1-31)和式(1-32)组成的方程组，得稳态概率分布为：

（1-33）

第48页，课件共82页，创作于2023年2月生灭（birth-death）过程(1)

在实际中，我们经常遇到这样一类特殊的马氏过程：仅有相邻状态的转移，而没有其它状态的转移（即如果，则），如图1-15所示。这一类过程通常称为生灭（birth-death）过程。

第49页，课件共82页，创作于2023年2月生灭（birth-death）过程(2)它表示一个群体（动物、生物等）总数为n的特殊状态转移过程。该群体总数的状态转移只有三种可能：或者从n增加一个（群体出生一个），或者从n减少一个（死亡一个），或者群体的总数n保持不变。而其它所有可能的转移相对前三种转移都是高阶无穷小，因而可以忽略不计。该群体状态的转移概率取决于群体的总数n（状态）。第50页，课件共82页，创作于2023年2月生灭（birth-death）过程(3)令，则应用式（1-30）可得：

（1-35）它表示在稳态的情况下，从状态n转移到状态n+1的频率等于从状态n+1转移到状态n的频率，或在状态转移图中设置一个虚拟的平面（图1-15中的虚线），则进入该平面的频率等于退出该平面的频率，即该平面是系统的一个稳定点。第51页，课件共82页，创作于2023年2月生灭（birth-death）过程(2)令状态空间为，详细平衡方程第52页，课件共82页，创作于2023年2月生灭（birth-death）过程(3)详细平衡方程localbalanceequations求解稳态概率第53页，课件共82页，创作于2023年2月1.3.3马尔可夫链(16)上式可推广到一个更一般的形式：

（1-36）该等式称为详细平衡方程（detailedbalanceequation）。如果对于一个过程，有式（1-36）成立，则意味着有式（1-30）全局平衡方程存在。但并不是任何马尔可夫链都必须有式（1-36）成立。但在很多实际应用中，式（1-36）是成立的。因此实际中，我们可以先假设式（1-36）成立，然后通过它们求解稳态概率{pj,j}。如果求得的结果满足，则求得的分布{pj,j}就是满足式（1-27）的稳态分布。第54页，课件共82页，创作于2023年2月生灭（birth-death）过程(4)例1.3

设一个特殊的生灭过程的状态转移概率为试求其稳态分布。解：利用式（1-35）（或假设式（1-36）成立）有：从而有：

式中

经过递推得：第55页，课件共82页，创作于2023年2月生灭（birth-death）过程(5)显然只有在的情况下，才可能有下式成立。从而可得。进而可得：

综上可得，在的情况下，该生灭过程的稳态分布为第56页，课件共82页，创作于2023年2月1.3.4图论基础

在通信网络中，许多问题的描述都是基于图论的，因此，我们下面对图论的一些基本概念进行讨论。其实我们已应用了图的很多概念。例如：

AEFDCB第57页，课件共82页，创作于2023年2月1.图的概念（1）

一般几何上将图定义成空间中一些点（顶点）和连接这些点的线（边）的集合。图论中将图定义为G=(V,E)，其中V表示顶点的集合，E表示边的集合。例如：如图1-16所示的图可以表示为：第58页，课件共82页，创作于2023年2月1.图的概念（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页，创作于2023年2月1.图的概念（3）一般图G=(V,E)的顶点数用表示，边的数目用表示。若和都是有限的，则称图G是有限图，否则称为无限图。本书只讨论有限图的情况。

第60页，课件共82页，创作于2023年2月1.图的概念（4）在实际应用中，图中每条边可能有一个方向是很自然的（它反映了信息或物质的流向）。当给图G的每一条边都规定一个方向，则称该图为有向图。对有向图图G=(V,E)，有向边e用与其关联的顶点（u，v）的有序对来表示，即，它表示u为边e的起点，v为边e的终点。那么图1-17所示的有向图可表示如下：

第61页，课件共82页，创作于2023年2月1.图的概念（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页，创作于2023年2月1.图的概念（6）对图G=(V,E)和G’=(V’,E’)来说，若有和，则称图

G’是图G的一个子图；若或，则称图G’是图G的一个真子图。第63页，课件共82页，创作于2023年2月2．路径与回路(1)如果路径中有v0=vk，则为回路（或环Cycle），回路中没有重复边时称为简单回路。定义：图的一些顶点和边的交替序列，且边ei的端点为vi-1和vi，i=1,2,3,…k，则称为一条路径（Path），v0和vk分别为的起点和终点。如果中所有的边均不相同，则称其为简单路径。以v0为起点，vk为终点的路径称为v0－vk路径。对于有向图也有类似定义路径、回路的概念，只不过此时需要考虑方向性。第64页，课件共82页，创作于2023年2月2．路径与回路(2)例4：

在图1-18中，是一路径，是一回路.

第65页，课件共82页，创作于2023年2月2．路径与回路(3)定义：对图G=(V,E)来说，若G的两个顶点u，v之间存在一条路径，则称u和v是连通的；若图G的任意两个顶点都是连通的，则称图G是连通的；否则是非连通的。非连通的图可分解为若干连通的子图。第66页，课件共82页，创作于2023年2月2．路径与回路(4)图1-19的无方向图中，图（a）中任意两个顶点之间都有路径，所以该图是连通的；图（b）中顶点3和图中其它顶点之间没有路径，所以该图是非连通的；图（c）则是一个孤立的节点。第67页，课件共82页，创作于2023年2月2．路径与回路(5)对于有向图，若边去掉方向后是连通的，则称该图为连通的有向图。若对于有向图的任意两个顶点u和v之间存在u到v的路径和v到u的路径时，称该图为强连通的。图1-20（a）的有向图是一个连通的有向图，但不是强连通的。因为顶点2和顶点3之间不存在双向的路径；图1-20（b）是一个强连通的图，该图中任意两个顶点之间都存在双向的路径。第68页，课件共82页，创作于2023年2月3.生成树和最小重量生成树（1）

定义：不包括回路（环）的连通图，称为树。定义：对于图，包含了图G中所有顶点的树称为生成树（SpanningTree）。在图1-21中，图（b）、（c）和（d）都是树。而图（a）由于有回路，所以不是树。在图1-21中，图（b）和图（c）都是图（a）的生成树。第69页，课件共82页，创作于2023年2月3.生成树和最小重量生成树（2）对于一个给定的图G=(V,E)，其生成树的构造算法如下：

1)令n是V中的任意一个顶点，构造子图G’=(V’,E’)，其中，V’={n},E’=｛空集｝；2)如果V’=V则停止。此时G’=(V’,E’)就是一个生成树。否则进行第3）步；3)令(i,j)E，其中iV’,jV-V’，并采用下列方式更新V和V’：V’:=V’{j}，E’:=E’{(i,j)}，转到第2）步。nEFDCBV’={n},E’=nEFDCBV’nEFDCB第70页，课件共82页，创作于2023年2月3.生成树和最小重量生成树（3）该算法是从仅有一个顶点、0条边的子图开始，以后每执行一次第3）步就增加一个顶点和一条边。这就意味着最终生成的树有个节点，－1条链路。通常对于一个连通图，其边的条数大于等于-1。如果一个图G的边的数目等于－1，则上述算法将使用该图中所有的边，因而有G=G’，即此时图G本身就是一颗树。

第71页，课件共82页，创作于2023年2月3.生成树和最小重量生成树（4）一般而言，对于一个图可以有很多个生成树。对于通信网络来说，利用生成树来实现广播是比较经济的。但每一条边的成本或时延通常是不相同的，这时就要考虑树中各边的重量（成本或时延）。通常我们用Wij表示边（i,j）的重量。

nEFDCBnEFDCBnEFDCB231152164最小重量生成树（MST，MinimumWeightSpanningTree）：是指边的重量和最小的生成树。

第72页，课件共82页，创作于2023年2月3.生成树和最小重量生成树（5）MST的任一个子树称为一个树枝（fragment）。（注意：一个顶点