通信网理论基础.复习题.ppt
2004-07-29,第1/14页,信 道信号传输媒质,噪声源各种干扰等效结果,信 源信息源,变换器信号适合在信道中传输,反变换器适合接收者,信 宿信息接收者,1简述通信系统的模型,并简要介绍各部分的作用,2004-07-29,第2/14页,2.1简述通信网基本结构及其特点,2004-07-29,第3/14页,2.2简述通信网基本结构及其特点.,2004-07-29,第4/14页,现代通信网的发展 数字化：数字传输、数字交换、数字终端等 综合化：各种业务综合在一个数字通信网中传输 智能化：建立智能网，网路结构更灵活，用户具有更 强的控制能力 个人化：任何人、任何地点、任何时间,3简述现代通信网的发展趋势,2004-07-29,第5/14页,4.什么是图,2004-07-29,第6/14页,5.什么是端点，何谓关联,端点,关联,2004-07-29,第7/14页,6.下图描述的是同一个图么？为什么,描述一个图的图形不是唯一的。端点和边的相对位置并不重要，一个图的图形仅仅描绘出端点和边的关联关系。,2图形描述了同一个图,2004-07-29,第8/14页,7.什么是无向图,2004-07-29,第9/14页,8.什么是有向图,2004-07-29,第10/14页,9.什么是有权图,7.有权图,2004-07-29,第11/14页,10 什么是端的度数？何谓出度，入度,端的度数,端的出度,端的入度,有向图中,2004-07-29,第12/14页,11.什么是连通图,图G=(V,E)。若图中任意2点之间至少存在一条路径,连通图,非连通图,2004-07-29,第13/14页,12.什么是子图、真子图、生成子图和最大连通子图？,子图,真子图,生成子图,包含原图所有端点的子图,最大连通子图,若G是图G的一个连通子图.若再加上属于原图G中的任何一个其他元素,图G就失去了连通性,成为非连通图.则G为图G的最大连通子图,2004-07-29,第14/14页,13.何谓树，树枝，树干，树尖和有根树,任意两端间有且只有一条径的图称为树树枝(branch):树中的边树干:树枝的两个端点都至少 与两条边关联树尖:树枝的一个端点(称为树 叶)仅与此边关联有根树:指定树中的一个节点 为根,2004-07-29,第15/14页,14.1 利用破圈法求下图的一棵生成树,例:破圈法求解下图的一棵生成树,2004-07-29,第16/14页,14.2 利用破圈法求下图的一棵生成树.续,2004-07-29,第17/14页,15 利用避圈法求下图的一棵生成树,例:避圈法求解下图的一棵生成树,2004-07-29,第18/14页,16.1 求下图的基本割集,例：求基本割集,解：,1.破圈法求生成树,2004-07-29,第19/14页,16.2 求下图的基本割集.续,2.求解连枝集,2004-07-29,第20/14页,16.3 求下图的基本割集.续,3.基本割集 生成树中的每条树枝+某些连枝,（1）,2004-07-29,第21/14页,16.4 求下图的基本割集.续,（2）,2004-07-29,第22/14页,16.5 求下图的基本割集.续,（2）,2004-07-29,第23/14页,16.6 求下图的基本割集.续,2004-07-29,第24/14页,16.7 求下图的基本割集.续,2004-07-29,第25/14页,16.8 求下图的基本割集矩阵,例子（无向图）,2004-07-29,第26/14页,16.9 求下图的基本割集矩阵,例子（有向图）,2004-07-29,第27/14页,17.什么是网络，何谓容量,网络:,2004-07-29,第28/14页,18.什么是可行流,可行流(flow):,2004-07-29,第29/14页,19.1 利用K方法求解下列问题,解,思路,K0：权值非减顺序排列K1：权值最小的边为树枝K3：直到选出n1条边选出,结束,例题5个城镇，距离为权值。求线路费用最小的网路结构,2004-07-29,第30/14页,19.2 利用K方法求解下列问题.续,思路,K0：权值非减顺序排列K1：权值最小的边为树枝K2：直到选出n1条边选出,结束,2004-07-29,第31/14页,19.3 利用K方法求解下列问题.续,2004-07-29,第32/14页,20.1 利用P方法求解下列问题,解,例5个城镇，权值为距离。求线路费用最小的网络,2004-07-29,第33/14页,20.2 利用P方法求解下列问题.续,2004-07-29,第34/14页,20.3 利用P方法求解下列问题.续,2004-07-29,第35/14页,20.4 利用P方法求解下列问题.续,2004-07-29,第36/14页,21.1 利用D算法求解下列问题,解,初始化,2004-07-29,第37/14页,21.2 利用D算法求解下列问题.续,计算暂置值,取最小值,2004-07-29,第38/14页,21.3 利用D算法求解下列问题.续,初始化,计算暂置值,2004-07-29,第39/14页,21.4 利用D算法求解下列问题.续,2004-07-29,第40/14页,21.5 利用D算法求解下列问题.续,2004-07-29,第41/14页,21.6 利用D算法求解下列问题.续,2004-07-29,第42/14页,21.7 利用D算法求解下列问题.续,2004-07-29,第43/14页,21.8 利用D算法求解下列问题.续,取最小值,初始化,2004-07-29,第44/14页,21.9 利用D算法求解下列问题.续,计算暂置值,2004-07-29,第45/14页,21.10 利用D算法求解下列问题.续,2004-07-29,第46/14页,21.11 利用D算法求解下列问题.续,2004-07-29,第47/14页,21.12 利用D算法求解下列问题.续,2004-07-29,第48/14页,21.13 利用D算法求解下列问题.续,取最小值,初始化,2004-07-29,第49/14页,21.14 利用D算法求解下列问题.续,计算暂置值,2004-07-29,第50/14页,21.15 利用D算法求解下列问题.续,2004-07-29,第51/14页,21.16 利用D算法求解下列问题.续,2004-07-29,第52/14页,21.17 利用D算法求解下列问题.续,取最小值,初始化,2004-07-29,第53/14页,21.18 利用D算法求解下列问题.续,2004-07-29,第54/14页,21.19 利用D算法求解下列问题.续,2004-07-29,第55/14页,21.20 利用D算法求解下列问题.续,取最小值,初始化,2004-07-29,第56/14页,21.21 利用D算法求解下列问题.续,计算暂置值,2004-07-29,第57/14页,21.23 利用D算法求解下列问题.续,最后结果,2004-07-29,第58/14页,22.1 已知F算法得到的全值矩阵和路由矩阵,最后结果,2004-07-29,第59/14页,22.2 F算法.续,最短长度,2004-07-29,第60/14页,22.3 F算法.续,最短路径,2004-07-29,第61/14页,22.4 F算法.续,2004-07-29,第62/14页,22.5 F算法.续,虚线说明最短路径所经过的端，但具体边未定,2004-07-29,第63/14页,22.6 F算法.续,原问题转化为,2004-07-29,第64/14页,22.7 F算法.续,2004-07-29,第65/14页,22.8 F算法.续,是否说明？,2004-07-29,第66/14页,22.9 F算法.续,2004-07-29,第67/14页,22.10 F算法.续,2004-07-29,第68/14页,22.11 F算法.续,2004-07-29,第69/14页,22.12 F算法.续,2004-07-29,第70/14页,22.13 F算法.续,原问题转化为,问题回顾,2004-07-29,第71/14页,22.14 F算法.续,第1问题得到解决,2004-07-29,第72/14页,22.15 F算法.续,第2个问题,2004-07-29,第73/14页,22.16 F算法.续,2004-07-29,第74/14页,22.17 F算法.续,2个问题,2004-07-29,第75/14页,22.18 F算法.续,2004-07-29,第76/14页,22.19 F算法.续,结果为,2004-07-29,第77/14页,22.20 F算法.续,2004-07-29,第78/14页,22.21 F算法.续,其解为,2004-07-29,第79/14页,22.22 F算法.续,其解为,2004-07-29,第80/14页,23 什么是呼叫量，其单位是什么,2.呼叫量,业务量的强度可以定义为线路占用时间与观察时间之比(没有量纲),但是通常用“爱尔兰”表示它的单位,即,2004-07-29,第81/14页,24 求解下列问题,2004-07-29,第82/14页,25 求解下列问题,2004-07-29,第83/14页,26 简述排队系统的组成,输入过程：是对顾客到来的特征进行描述,包括顾客总体数目，到来方式（单个或成批），到来间隔的规律等。服务规则：包括先到先服务（FIFO），后到先服务（LIFO），随机服务，有优先权服务等。服务机构：包括服务员数目，服务时间特征等。,排队系统的组成,2004-07-29,第84/14页,27 描述排队系统的三个基本参数是什么,2004-07-29,第85/14页,28 描述排队系统的三个基本参数是什么.续,2004-07-29,第86/14页,29 什么是排队强度？有什么意义,排队强度（稳定性参数）,2004-07-29,第87/14页,30 排队系统的表示方法,2004-07-29,第88/14页,31 求下列问题,例,设电话呼叫为30次/小时的泊松过程，求5分钟间隔内（1）不呼叫的概率（2）呼叫3次的概率,解,2004-07-29,第89/14页,32 求下列问题,在某数据传输系统中，有一数据节点，顾客的信息包按照泊松流到达。已知平均每小时到达20个信息包，节点处理时间服从指数分布，处理一个信息包平均需要2.5分钟。求该节点的有关运行指标,解,此系统为一M/M/1非拒绝系统,2004-07-29,第90/14页,33 求下列问题.续,系统的运行指标,2004-07-29,第91/14页,34 求下列问题,例题：某机关接待室只有1位对外接待人员，每天工作10小时，来访人员和接待时间都是随机的。若来访人员按照泊松流输入，平均每小时7人，接待时间服从指数分布，其服务速率为每小时7.5人。求：（1）来访者的逗留时间（2）平均队长（3）若希望来访者逗留时间减少一般，则单位时间内接待人数应为多少？,解,
