通信网理论基础.复习题

通信网理论基础信源反变换器信道变换器信宿噪声信道－信号传输媒质噪声源－各种干扰等效结果信源－信息源变换器－信号适合在信道中传输反变换器－适合接收者信宿－信息接收者1简述通信系统的模型,并简要介绍各部分的作用通信网理论基础网形网网孔形网星形网复合形网任意2个节点间均有线路相连冗余度较大、稳定性较好线路利用率不高、经济性较差不完全的网形网。大部分节点间均有线路相连线路利用率、经济性改善稳定性下降辐射网，一个节点作为辐射点，其余节点均与之相连传输链路少稳定性差（中心节点是瓶颈）兼具网形网和星形网的优点，常用网形网和星形网复合而成2.1简述通信网基本结构及其特点通信网理论基础总线形网环形网线形网SDH常见树形网接入网所有节点都连接在总线上传输链路少、增加节点方便稳定性差，网络范围受限所有节点按次序连接成环结构简单，稳定性较高所有节点按次序连接，但不成环节点按层次进行连接，信息交换主要在上、下节点间进行2.2简述通信网基本结构及其特点.通信网理论基础现代通信网的发展数字化：数字传输、数字交换、数字终端等综合化：各种业务综合在一个数字通信网中传输智能化：建立智能网，网路结构更灵活，用户具有更强的控制能力个人化：任何人、任何地点、任何时间3简述现代通信网的发展趋势通信网理论基础4.什么是图设有端点集},,,{21nvvvV和边集},,,{21meeeE当存在关系R，使得），＝（记为，组成图和边集成立时，则说由端点集EVGGEVEVVR通信网理论基础5.什么是端点，何谓关联),(,),(jikkjijikvveevvvve的端点，记为是则相对应，与点对如有有一条边端点关联关联与边则称，如果kjijikevvvve,),(通信网理论基础6.下图描述的是同一个图么？为什么描述一个图的图形不是唯一的。端点和边的相对位置并不重要，一个图的图形仅仅描绘出端点和边的关联关系。2v1v3v4v1e4e2e6e5e3e2图形描述了同一个图2v1v3v4v1e2e3e4e5e6e通信网理论基础7.什么是无向图),(),(G),(ijjikijjivvvveGRvvRvvEVG对应一无序点对中任一条边即图为无向图时，则称存在关系对等价于存在某种关系对。当设图2v1v3v4v1e4e2e6e5e3e通信网理论基础8.什么是有向图2v1v3v4v1e4e2e6e5e3e),(),(G),(ijjikijjivvvveGRvvRvvEVG对应一有序点对中任一条边即图为有向图时，则称存在关系对不等价于存在某种关系对。当设图通信网理论基础9.什么是有权图2v1v3v4v1e4e2e6e5e3e3.03.42.63.03.72.07.有权图称为权值。赋以一个实数或者每个端点条边，每设图kkikppveEVG1),(通信网理论基础10什么是端的度数？何谓出度，入度端的度数端的出度)(ivd数。记为：与某一端点相关联的边)(iivdv射出的边数。记为：有向图中，离开或从端端的入度)(iivdv＋的边数。记为：端有向图中，进入或射入)()()(iiivdvdvd端的度数有向图中通信网理论基础11.什么是连通图图G=(V,E)。若图中任意2点之间至少存在一条路径1v2v3v4v5v1e2e3e4e5e6e7e1v2v3v4v5v1e2e3e4e5e6e7e6v7v8e连通图非连通图通信网理论基础12.什么是子图、真子图、生成子图和最大连通子图？子图)','('),,(EVGEVG设图EEVV','GGGG':'的子图是称真子图的真子图为称但设GGEEGG'.','生成子图包含原图所有端点的子图最大连通子图若G’是图G的一个连通子图.若再加上属于原图G中的任何一个其他元素,图G’就失去了连通性,成为非连通图.则G’为图G的最大连通子图通信网理论基础13.何谓树，树枝，树干，树尖和有根树任意两端间有且只有一条径的图称为树树枝(branch):树中的边树干:树枝的两个端点都至少与两条边关联树尖:树枝的一个端点(称为树叶)仅与此边关联有根树:指定树中的一个节点为根树根树干树尖树叶通信网理论基础19.1利用K方法求解下列问题1v2v3v4v5v358.46.85111261014解思路14101291181075868546463523153425241514354313221),(),(),(),(.),(),(.),(),(),(),(vvvvvvvvvvvvvvvvvvvv权值（距离）边顺序K0：权值非减顺序排列K1：权值最小的边为树枝K3：直到选出n－1条边选出,结束1排序:0K例题5个城镇，距离为权值。求线路费用最小的网路结构通信网理论基础19.2利用K方法求解下列问题.续按顺序选边:1K2没有形成回路，保留）（没有形成回路，保留）（形成回路，舍去）（没有形成回路，保留）（）（4354313221vvvvvvvvvv,,,,,12v3v4v5v346.853思路K0：权值非减顺序排列K1：权值最小的边为树枝K2：直到选出n－1条边选出,结束1v2v3v4v5v358.46.85111261014通信网理论基础19.3利用K方法求解下列问题.续42284653..结构总长度为412v3v4v5v346.85通信网理论基础20.1利用P方法求解下列问题1v2v3v4v5v358.46.85111261014解例5个城镇，权值为距离。求线路费用最小的网络1v2v3v4v5v358.46.85111261014任选一点11vG通信网理论基础20.2利用P方法求解下列问题.续1v2v3v4v5v358.46.85111261014中各端的权值，取极小到比较11GGG2,1,11minddjGGj212,vvG1v2v3v4v5v358.46.85111261014212,vvG通信网理论基础20.3利用P方法求解下列问题.续1v2v3v4v5v358.46.85111261014中各端的权值，取极小到比较22GGG1v2v3v4v5v358.46.851112610143213,,vvvG通信网理论基础20.4利用P方法求解下列问题.续},,,,{};,,,{};,,{};,{};{54321543214321321211vvvvvGvvvvGvvvGvvGvG最小12d最小23d最小34d最小45d1v2v3v4v5v358.46.85111261014通信网理论基础21.1利用D算法求解下列问题到其他各点的最短径长算法求下图中7Dv解6543217700,},{,:spsvGvvD1初始化3v7v6v5v1v4v2v5.10.40.21.36.155.00.52.17.62.9sv通信网理论基础21.2利用D算法求解下列问题.续2计算暂置值******),min(.)..,min(.)..,min(.)..,min(:657474473733727271711105151510020202050505002ddddD116543212*******),,,,,min(:wD3取最小值通信网理论基础21.3利用D算法求解下列问题.续65432170},{:vvGDp初始化4计算暂置值55.010.2)0.2,5.0,min(),,min(721212*2dd3v7v6v5v1v4v2v5.10.40.21.36.155.00.52.17.62.9sv通信网理论基础21.4利用D算法求解下列问题.续5.0)5.0,5.0,min(),,min(731313*3dd3v7v6v5v1v4v2v5.10.40.21.36.155.00.52.17.62.9sv通信网理论基础21.5利用D算法求解下列问题.续7.1),2.15.0,min(),,min(741414*4dd3v7v6v5v1v4v2v5.10.40.21.36.155.00.52.17.62.9sv通信网理论基础21.6利用D算法求解下列问题.续7.9),2.95.0,min(),,min(751515*5dd3v7v6v5v1v4v2v5.10.40.21.36.155.00.52.17.62.9sv通信网理论基础21.7利用D算法求解下列问题.续),5.0,min(),,min(761616*6dd3v7v6v5v1v4v2v5.10.40.21.36.155.00.52.17.62.9sv通信网理论基础21.8利用D算法求解下列问题.续取最小值6初始化7*3*6*5*4*3*25.0),,,,min(},,,{),,{6542317vvvvGGvvvGpp654321,7.97.1,5.00.2,5.03v7v6v5v1v4v2v5.10.40.21.36.155.00.52.17.62.9sv通信网理论基础21.9利用D算法求解下列问题.续80.2)5.0,5.0,0.2min(),,,min(323721212*2ddd计算暂置值3v7v6v5v1v4v2v5.10.40.21.36.155.00.52.17.62.9sv通信网理论基础21.10利用D算法求解下列问题.续7.1)5.0,,2.15.0,7.1min(),,,min(343741414*4ddd3v7v6v5v1v4v2v5.10.40.21.36.155.00.52.17.62.9sv通信网理论基础21.11利用D算法求解下列问题.续7.9)5.0,,2.95.0,7.9min(),,,min(353751515*5ddd3v7v6v5v1v4v2v5.10.40.21.36.155.00.52.17.62.9sv通信网理论基础21.12利用D算法求解下列问题.续5.4)0.45.0,,5.0,min(),,,min(363761616*6ddd3v7v6v5v1v4v2v5.10.40.21.36.155.00.52.17.62.9sv通信网理论基础21.13利用D算法求解下列问题.续取最小值9*4*6*5*4*27.1),,,min(10初始化},,{},,,{6524317vvvGGvvvvGpp5.4,7.97.1,5.00.2,5.06543213v7v6v5v1v4v2v5.10.40.21.36.155.00.52.17.62.9sv通信网理论基础21.14利用D算法求解下列问题.续计算暂置值110.2)0.57.1,5.0,0.2,5.0,0.2min(),,,,min(424323721212*2dddd3v7v6v5v1v4v2v5.10.40.21.36.155.00.52.17.62.9sv通信网理论基础21.15利用D算法求解下列问题.续4.2)7.07.1,5.0,,2.95.0,7.9min(),,,,min(454353751515*5dddd3v7v6v5v1v4v2v5.10.40.21.36.155.00.52.17.62.9sv通信网理论基础21.16利用D算法求解下列问题.续5.4)7.1,0.45.0,,5.0,5.4min(),,,,min(464363761616*6dddd3v7v6v5v1v4v2v5.10.40.21.36.155.00.52.17.62.9sv通信网理论基础21.17利用