通信网图论及应用(txt+pdf+epub+mobi电子书下载)


发布时间:2020-07-20 02:00:22

点击下载

作者:刘焕淋,陈勇(编著)

出版社:人民邮电出版社

格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT

通信网图论及应用

通信网图论及应用试读:

前言

信息通信网是现代信息社会的重要基础设施之一。人们对信息化网络提供的服务需求促进了信息通信技术及网络的快速发展。在信息化通信网络中,光纤通信、微波通信、卫星通信和移动通信构成了通信网的传输基础,向我们提供语音、数据和图像等各类业务,为广大公众提供稳定可靠、迅速有效的各种信息通信服务。

在信息通信网络中,通过建立网络的图论数学模型进行网络规划和流量优化,是提高和确保网络通信质量的重要手段之一,它涉及网络的拓扑结构、接口协议、资源管理和调度机制,是信息网络进行理论分析、结构调整、性能优化、资源融合的基础。图论作为一种迅速发展的组合优化研究工具,在计算机、信息网络、运筹学、系统工程、物理学、电子学、生物学、化学和心理学等领域中都有着广泛的应用,因此越来越受到关注和重视。在信息网络优化研究中,我们可以图论模型来求解通信网络的最佳路由和优化流量分配策略,还可以根据实验结果修正完善图论模型。基于图论的理论方法分析网络性能、规划网络拓扑、优化网络设计、优化流量分配与控制策略、增强网络维护和管理是十分有效和必要的。

本书主要阐述以图论建模的方法来优化网络的路由选择和流量控制方法,采用比较通俗的语言和科学的系统结构,重视基础,强调应用,适应科学研究工作和工程应用要求。全书分为6章。第1章介绍了通信网的基本概念、网络体系结构、路由选择、流量分配和通信网质量指标的基本概念。第2章介绍了通信网理论分析的图论模型、基本概念和用矩阵方法描述抽象网络的方法。第3章讨论了通信网的路由选择和最短路径的概念、确定信息源节点到网络其他节点的最短路径算法及算法复杂性分析、通信网中任意节点之间最短路径算法及通信网路由选择中需要考虑的次短路由和交换中心选择问题,并阐述了稀疏网络路由选择和基于并行运算优化快速路由的方法。第4章分析了通信网的最大流分配问题,阐述了基于分层网阻塞流、基于冗余网的最大流、基于流推进的最大流方法,还研究了一些特殊的混合网络和交换节点处理能力有限的网络最大流分配方法。第5章讨论了最小费用流描述模型、最小费用最大流、最小费用循环流等方法及实现,基于时延约束的最小费用网络网络流方法。第6 章分析了最小树和最优通信网的构造,研究了几种最小树的构造方法、基于最小费用的最优通信网构建方法和基于破圈的最小树构建方法。

近十年来,编者主讲了大学本科通信工程专业的《网络图论》课程,参加了通信系统和通信网络交换测试、网络优化的科学研究及研究生指导工作,参阅了国内外大量的优秀教材和相关研究资料,书写了自己的一些研究成果和教学体会,整理了前后知识点间关系。但由于水平有限,经验不足,书中难免有错误和疏漏不妥之处,恳请读者批评指正。

本书在编写过程中得到了陈勇、张斌和陈春燕的大力支持,他们参与了相关章节的编写、勘误和整理工作。在成书过程中,参考了李建东、周炯槃、郑健体、吕久明、谢政、陈慧开、鲜继清、鲍培明、周根贵、谢金星等学者所编写的教材和研究成果,在这里对本书所有参考文献的作者表示衷心感谢。另外,本书获得了重庆邮电大学出版基金资助,在此一并表示感谢。编者2009年12月第1章通信网概述

光纤通信的出现使大容量的信息传输成为可能;数字移动通信和数字卫星通信技术的发展使通信更具有个性化的特征;通信技术和计算机网络技术的融合使宽带综合业务网络迅速崛起,并使网络充满了智能。信息通信技术成为现代化信息网络的平台和信息产业的重要基础设施,人们对信息化网络提供的服务需求促进了信息通信技术及网络的不断发展。在信息化通信网络中,光纤通信、微波通信、卫星通信和移动通信构成了通信网的传输基础,能够提供语音、数据和图像等各类业务,由电话通信网、数据通信网、移动通信网、有线电视网等业务网组成的高速信息通信网为广大公众提供稳定可靠、迅速有效的各种信息服务。1.1 通信网的基本概念1.1.1 通信的基本概念

通信的目的是为了将消息从发送方传递、交换到接收方,我们通常把参与者按照预先的某种约定将消息从一个地方向另一个地方进行有效的传递、互通和交换称为通信。完成信息的传递和交换要通过一套设备实现,将一个用户的信息传递到另一个用户的全部功能实体称为一个通信系统。如果按通信的业务不同,可将通信系统分为话务(电话业务)通信系统和非电话业务(如电报、传真、广播电视和数据等)通信系统;如果按通信系统的信道中传输的信号特征分,可将通信系统分为模拟通信系统和数字通信系统;如果按调制方式划分,可以分为基带传输系统和频带传输系统;如果按传输介质分类,可以分为有线通信系统和无线通信系统;如果按系统工作波段分类,可以分为长波通信系统、中波通信系统、短波通信系统、微波通信系统、远红外通信系统等。

我们从众多的、不同的具体通信系统中抽象、概括出通信系统的基本模型,如图1-1所示,其基本组成包括信源、变换器、信道、噪声源。反变换器和信宿6个部分。(1)信源:是产生各种信息(如语音、数据、文字和图像等)的信息源。信源发出的信息可以是连续的,也可以是离散信号。在人与人之间进行通信的情况下,信源是指发出信息的人;在机器与机器之间通信的情况下,信源是发生信息的机器,如计算机、电传机或其他设备。不同的信源构成不同形式的通信系统,如对应语音信源的是电话通信系统,对应文字信源的是电报通信系统和传真系统;对应数据信源的是计算机通信系统等。(2)变换器:是将信源发出的信息变换成适合在信道中传输的信号。变换过程包括:将非电信号变换成电信号,然后将电信号进行变换和处理,使它适合在信道中传输。对应不同的信源通信系统,满足不同的通信要求,变换器由不同的电路、器件和系统组成。在模拟电话通信系统中变换器包括送话器放大器、滤波器和调制器等。对于数字电话通信系统,变换器还要增加模/数变换功能,将模拟话音信号变换成数字信号,并进行时分多路复用后进行传输处理。图1-1 通信系统的基本模型(3)信道:是信号传输的通道,是各种传输媒介的总称。信道按传输介质可以分为有线信道和无线信道。在有线信道中,电磁信号(或光信号)被约束在某种看得见、摸得着的有线形介质(导线、电缆、光缆和波导等)上传输;在无线信道中,电磁信号在看不见、摸不着的自由空间(大气层、对流层、电离层等)中传输。按照信道中传输信号的特征还可以分为模拟信道和数字信道。(4)反变换器:是将从信道上接收的信号变换成信息接收者可以接收的信息,其作用正好与变换器相反,起着信号还原和恢复的作用。(5)信宿:是信息的接收者,即信息传送的目的地。它可以与信源对应,是人或机器,实现人—人通信、人—机通信或机—机通信。(6)噪声源:是系统内各种干扰影响的等效结果表示,它不是人为实现的实体,但在实际的通信系统中客观存在。系统的噪声来自系统各个部分,从发出和接收信息的周围环境、各种设备的电子器件,到信道所受到的外部电磁干扰(如闪电、其他系统的高频电磁波等),都会对信号形成噪声影响,如信源处混入的干扰,变换器/反变换器的电子设备中引入干扰,传输信道中电磁感应及接收端设备引入干扰。为了分析方便,将系统内所存在的干扰噪声均折合到信道中,用噪声源表示。

在设计和评价通信系统时,必然涉及通信系统的性能指标,这些指标用来衡量通信系统性能的优劣。通信系统性能指标关系到系统的有效性、可靠性、适应性、标准性、工艺性、经济性和维护使用等。尽管对通信系统有名目繁多的实际要求,但是,从研究消息传输来说,通信的有效性与可靠性是两个最重要的指标。其中,有效性指消息传输的“速度”问题,而可靠性主要指消息传输的“质量”问题。显然,有效性和可靠性是两个相互矛盾的问题,这对矛盾只能依照实际情况实事求是,取得相对的统一。例如:在满足一定可靠指标下,尽量提高消息的传输速度;在维持一定的有效性下,使消息传输质量尽可能提高。

对于模拟通信系统来说,消息传输速度主要决定于消息所含的信息量和对模拟信号的处理,处理的目的在于使单位时间内传送更多的消息。模拟通信系统常用有效传输频带来衡量系统的信息传输有效性。如果某信道允许的传输频带确定,它被每路信号的有效传输频带相除,就可确定信道允许同时传输的路数,这个数目越大,则该通信系统的信息传输有效性就越高。模拟通信系统的可靠性常用系统输出端的信噪比(S/N)来衡量。信噪比的含义是接收端输出的信号平均功率与噪声平均功率之比,信噪比越高,通信质量越好,系统抗干扰的能力越强。反之,质量就差。

对数字通信系统而言,信息传输的有效性通常用信息传输速率简称比特率(Rb)表示,比特率定义为每秒传输二进制码元的个数,单位是bit/s。以二进制数字通信系统为例,码元的状态有“0”和“1”两种,如果每秒传输4800个码元,则该系统比特率(Rb)为4800bit/s。数字通信系统的可靠性常用差错率表示,差错率也称为误码率。误码率是指错误接收的码元数在传输总码元数中所占的比例,即码元在传输系统被传错的概率,用P表示,公式如式1-1。e

误码率的大小与通路特性和信道质量有关。如果通路特性和信道特性都是高质量的,则系统的误码率较低。提高信道的信噪比可使误码率降低;缩短中继站之间的距离,也可以提高信道的信噪比,降低误码率。1.1.2 通信网的构成要素

一个完整的通信网络除了必备的硬件设备外,还要有相应的软件系统。通信网络在硬件方面由传输链路、交换设备和终端设备组成,也称为通信网三要素,如图1-2所示。为了使全网有效、协调地运行,通信网还需要有信令方案、通信协议、网络结构、路由方案、编号方案、计费方案、质量控制指标等软件支撑。图1-2 通信网构成三要素

1.终端设备(通信终端)

终端设备负责信息的发送与接收,是通信网中信息的源点和终点。终端设备的主要功能之一是将待传送的信息与信道上的信号进行相互转换和适配,如发送端将传感器获取的信息转换为在信道上传输的信号,接收端则从线路上接收信号并将之恢复成能被利用的信息;第二个功能是产生和识别网络内所需的信令信号或业务管理等所需的控制信息,以便应答和联系其他设备。最常见的终端设备有电话机、传真机、计算机、视频终端等。

2.传输链路

传输链路是通信网络节点间的连接媒介,是信息或信号的传输通路。它除主要对应于通信系统中的信道部分之外,还包括一部分变换或反变换装置。传输链路包括各种有线信道和无线信道,如电缆、光缆、微波、卫星和其他无线信道。

3.交换设备(交换节点)

交换设备是现代通信网络的核心,它的基本功能是完成接入交换节点链路的汇集、转接接续和资源分配,负责集中、转发终端节点产生的用户信息,实现一个用户与它所要求的另一个用户或多个用户之间的路由选择和呼叫连接。交换设备实现交换功能的常用交换设备有:程控交换机、分组交换机、ATM交换机、路由器、集线器、网关和交叉连接设备等。

不同的通信业务网络对交换设备的性能要求不同。对于电话业务网,对转接交换节点的要求是不允许对通话电流的传输产生时延,因此一般采用电路交换方式;对于计算机通信的数据业务网,由于数据终端或计算机终端可以有不同的速率,为了提高传输链路利用率,可将流入信息进行存储,然后转发到所需要的链路上,这就是存储转发交换方式。1.1.3 通信网的拓扑结构

现代通信网络是一个复杂和庞大的体系,通信网的网络结构(即网络拓扑)是泛指网络节点和传输线路的几何连接形状,关系着网络连通性问题。根据节点(如交换机)连接的不同方法,常见的物理拓扑网络结构有5种:树型结构、星型结构、环型结构、总线型结构和网型结构,如图1-3所示。不同网络形状和结构都有其内部的规律性。复杂的通信网络拓扑结构都是由这5种网络结构再复合组成的。图1-3 通信网的基本网络结构(1)星型网

星型网的中心节点也称为汇接节点,网络若有N个节点,则需要 N−1条链路,除中心节点以外的任意两节点间不直接相连,都必须经过中心节点以辐射状连接。如果把中心节点看作交换局,则周围节点可看成用户终端;如果所有节点都是交换局,则中心节点可称为汇接局。这种结构的优点是:结构简单,链路数少,网络管理方便,组网灵活,便于用户业务汇集,适用于用户接入网。缺点是:任意两个端节点之间的呼叫必须通过中心节点转接,中心节点的信息处理能力和可靠性会影响整个网络,网络的安全性较差。因此,星型网覆盖范围较小,适合于网径较小的接入网或局域网的组网。(2)树型网

树型网也称为分级网或广播网,可以看作是星型网结构的叠加,节点按层次进行链接,信息交换主要在上、下相邻节点间进行。树型网一个分支节点的故障不影响另一分支节点的工作,任何一个节点送出的信息都由根节点接收后重新发送到所有的节点,可以传遍整个网络。树型网的优点是:结构简单,成本低,网络具有一定容错能力,节点扩展较为方便,寻找链路路径也比较方便。缺点是:根节点故障会影响整个网络,网络的安全性和可靠性对根节点依赖程度较大。我国的SDH 主从结构即是树型网, Internet大多采用这种结构。(3)环型网

环型网将所有节点串联相接,而且首尾相连,没有任何开放点时,就形成了所谓环型拓扑。环型网能够保证一个节点发送的信息可以被环上其他节点接收到。优点:可靠性高,具有很强的生存性(抗毁坏性能)和业务疏导能力。缺点:网络中任何节点故障将导致整个系统故障。(4)总线型网

总线型网将节点都连接到一条公共的传输线路上,这条传输线路常称为总线,因此称之为总线型网。这种网络的优点是:增减节点很方便,结构简单,设置的传输链路少,是一种并联的网络。缺点是:网络上任一节点故障会导致整个网络故障。在计算机网络中,10台以下计算机适合用总线型网络,10台以上就容易出故障,维护麻烦。(5)网型网

网型网也称为网状网,当涉及通信的许多节点(不必是全部节点)直接互连时,就构成了网型网。如果涉及通信的所有节点都进行直接互连,则构成理想的网孔形,在非理想的网孔形网络中,不直接相连的两个节点之间要实现连接,必须经由其他节点的连接中转来实现。这种网络结构优点:每两点间有多条路由供选择,可靠性高,克服了网络的信息流瓶颈问题,适合于业务量很大的地区的组网。缺点:网络结构复杂,成本较高。当节点数目增加时,网络的连接支路数将迅速增加,这将增加传输链路的投资费用,这一特点决定了网型网只能局限于节点数较小的网络使用。

上述组网结构各有特点,在实际网络中都得到不同程度的应用。在实际网络中,各局部网也可能采用不同的网络拓扑,例如:本地网(即接入网或用户网)中,采用环型网和星型拓扑结构;在长途网中,采用网型网拓扑比较有利。具体采用何种网络拓扑,应根据网络实际情况而定。1.2 通信网的网络体系结构

现代通信网是一个融合各种新技术的复杂网络,自动化程度高,通信的各方要做到有条不紊地交换信息,网中的所有节点都必须遵守一些预先约定好的规则,通信才能正常进行。比如电话网中约定的信令(signaling),计算机网络中约定的协议(protocol),加上规范的传输标准和质量标准,才能形成一个高效、有条不紊的通信网,通信网的性能和效率,很大程度上也取决于这些约定规则。我们把通信网中为进行数据的交换和传输而建立的规则称为通信协议。通信协议的标准化有助于推动通信网络化的发展,设备能互联互通,系统成为开放的、兼容性好的系统。1.2.1 OSI协议的体系结构

通信协议采用分层结构,把实现通信的网络在功能上看作若干相邻的层,每一层完成其特有的功能。上一层功能都建立在下一层基础上,利用较低层服务,同时为上一层提供服务。网络功能上的分层导致协议的分层,即把复杂的协议分解为一些简单的协议,再组合成总的协议。

实际的通信过程包括路由寻址、比特流传输、比特同步、流量控制、差错控制、信息加密和对话过程管理,信息交换的双方必须有相同(或相应)的功能块才能完成给定的功能。通信网的终端设备、传输设备和交换设备都由很多的厂商提供,为了使网络能在多设备厂商供货情况下实现良好的互通互联,国际标准化组织(International Standardization Organization,ISO)、因特网体系结构委员会(Internet Architecture Board,IAB)、因特网工程任务组(Internet Engineering Task Force,IETF)和国际电联(International Telecommunications Union,ITU)的两个咨询委员会(CCITT和CCIR)在促进网络协议标准化方面做了许多工作,制定了一系列建议。1977年,国际标准化组织ISO提出了开放系统互联(Open Systems Interconnection,OSI)参考模型,要求系统的外部特性必须符合OSI的网络体系结构,而其内部功能不受限制。

OSI协议参考模型分为7层,它们是:应用层、表示层、会话层、传输层、数据链路层和物理层,每一层可以用不同的协议向上层提供服务,同时每一层使其下一层与更高层分隔开,并将这作为开发协议的标准框架,如图1-4所示。

采用分层结构的开放系统互连大大降低了系统间信息传递的复杂性。它上以应用层为界,下以传输媒介为界,对网络中的节点仅起到通信中继和交换的作用,故只有3层。通常把1~3 层称为低层或下 3层,提供远距离通信的功能和网络服务功能,解决数据信息及时正确传送的问题;而把 4~7层称为高层,它是终端需要执行的功能,为终端用户提供服务,因此,高4层提供的功能只与终端用户相关,与网络功能无关。图1-4 OSI通信网中的分层概念

1.物理层

物理层位于OSI模型的最低层,其任务是利用物理媒介为数据链路层提供一个物理连接,以便透明地传输比特流,包括用于建立、保持和释放物理连接的机械、电气、功能和过程特性和手段。简而言之,物理层提供有关同步和全双工比特流在物理媒介上的传输手段。

2.数据链路层

数据链路层利用物理层全双工比特流传输的功能,为克服传输媒介的传输差错问题,保证数据在终端与网络之间或网络相邻节点的数据链路上进行可靠传输,并提供数据链路的建立、保持和拆除功能,包括帧控制(将物理层的比特流分割成帧的方式,如数据成帧,按帧进行发送、接收、同步等)、差错控制(如重发请求,循环冗余校验等)、流量控制(如滑动窗口方式流量控制以防止阻塞)、链路管理(确保链路连接正常)。

3.网络层

网络层提供系统之间的连接,它负责将两个终端系统经过网络节点用数据链路连接起来,为终端选择合适的路由和交换节点,使发送端的分组信息能正确无误地按照地址寻址到目的地,实现两个终端之间段到段的数据透明传送。网络层的功能包括寻址和选择路由、交换的方式、流量控制、顺序控制、差错控制、阻塞和非正常情况处理等。网络层提供的服务使它的上层不需要了解网络内部的数据传输和交换技术。

4.传输层

传输层可以看作是终端用户和网络之间的“联络员”,它利用低 3 层提供的网络服务向高层提供可靠的、保证质量的端到端的透明数据传送功能。它根据发送端与接收端的地址定义一个跨过多个网络的逻辑连接,并完成用户终端的差错纠正和流量控制功能,具体包括为用户提供端到端交换所需的差错控制、数据复接/分接方式、分组顺序控制方式等。

传输层的复杂度与它的低3层所提供的服务水平及它的上层所要求的服务质量有关,低3层提供的传输质量越可靠,传输层的功能就越简化;低3层的服务越糟糕,传输层的工作就越多。

5.会话层

会话层负责控制两个系统的表示层实体之间的对话,提供建立、管理和终止端对端用户间连接和使用连接的方法,以及为它们的数据交换提供必要的手段(如对话方式控制、同步恢复、会话权(核对身份)控制、如何支付费用等)。会话层虽然不参与具体的数据传输,但却对数据传输进行管理。

6.表示层

表示层定义信息的表示方法,解决用户语法和语义表示问题,将欲交换的数据转换成能被各种入网设备及运行的应用程序相互理解的约定格式。表示层的典型服务有数据翻译(信息解码、加密和字符集的翻译)、格式化(数据格式的修改及文本压缩)和语法选择(语法的定义及不同语言之间的转换)等。

7.应用层

应用层是OSI模型的最高层,直接向用户提供服务,提供用户访问OSI环境的手段。应用层提供管理功能和一些公共的应用程序,如用户信息的语义匹配、用户文件传送与控制、事务处理和其他网络管理等功能。1.2.2 TCP/IP协议体系结构

TCP/IP(Transmission Control Protocol/Internet Protocol,传输控制协议/网际协议)体系结构是指能够在多个不同网络间实现的协议簇。该协议簇是在美国国防高级研究计划局(Defense Advanced Research Projects Agency,DARPA)所资助的实验性ARPARNET 分组交换网络、无线电分组网络和卫星分组网络上研究开发成功的。网络部分瘫痪时仍保持较强的工作能力和灵活性。这种应用环境导致了一系列协议的出现,从而使不同类型的终端和网络间能够进行有效通信。实际上,Internet已经成为全球计算机互联的主要体系结构,而TCP/IP协议是 Internet 的代名词,是将异种网络、不同设备互联起来,进行正常数据通信的格式和大家遵守的约定。

TCP/IP 协议包括两部分:传输控制(TCP)协议和网际协议(IP)。TCP/IP 的通信任务组织成 5个相对独立的层次:应用层、传输层、互联网层(对应OSI的网络层)、网络接口层和物理层,其中网络接口层和物理层常称为物理网层。TCP/IP 协议体系结构与OSI 7 层模型的对应关系如图1-5所示。图1-5 TCP/IP 协议体系结构与OSI 7 层模型的对应关系

1.应用层

它使应用程序能够直接运行于传输层之上,直接为用户提供服务。包含的主要协议有文件传输协议(File Transfer Protocol,FTP)、简单邮件传送协议(Simple Mail Transfer Protocol, SMTP)、远程登录协议(Telnet)、域名服务协议(Domain Name Service,DNS)、网络新闻传送协议(Network News Transfer Protocol,NNTP)和超文本传输协议(Hyper Text Transfer Protocol,HTTP)等。

2.传输层

它的主要功能是对应用层传递过来的用户信息分成若干数据报,加上报头,便于端到端的通信。包括的协议有基本字节的面向连接应用层的传输TCP协议,TCP为应用程序之间的数据传输提供可靠连接;面向无连接的用户数据报UDP协议,UDP的传送不保证数据一不到达目的地,也不保证数据报的顺序,不提供重传机制;提供声音传送服务的NVP协议。

3.互联网层

互联网层对应于 OSI 模型的网络层。该层采用的协议称为互联网协议(IP),它提供跨多个网络的寻址选路功能,使IP数据(带有IP地址)从一个网络的主机传到另一网络的主机。包括的协议有网际IP协议;网际控制报文协议ICMP;将IP地址转换成物理网层地址的ARP协议;将物理网地址转换成IP地址的RARP协议。

4.网络接口层

网络接口层对应于OSI模型的数据链路层。接口层负责与物理传输的连接媒介打交道,主要功能是接收数据报,并把接收到的数据报发送到指定的网络中去。该层需要执行不同协议的局域网,通过网关实现协议与TCP/IP的转换,使数据穿过多个互联的网络正确地传输,实现异种网络接入Internet。

5.物理层

物理层利用物理媒介为比特流提供物理连接,一般将网络接口层和物理层统称 TCP/IP协议的物理网。物理网包含的协议有IEEE 802.3以太网;面向连接的X.25 公用数据网及X.75虚通路无连接协议;ARPANET网络;ATM网络;令牌环网等。1.3 通信网路由选择、流量分配与控制

通信网是一个多系统、多设备的复杂庞大的网络,要设计满足服务质量要求的性能指标及实现方案,需要网络设计人员掌握相当的网络理论基础知识和网络分析方法。为通信网网络设计必备的路由选择和流量分配与控制是网络质量的基础保障技术。1.3.1 路由选择

在通信网中,信号从一个地点传送到另一地点时经过的传输路径就称为路由。两点之间的路由可能存在多条,需要进行路由选择。路由算法的主要功能就是引导分组通过通信子网到达正确的目的节点。它包括为不同的源节点和目的节点选择一条传输路径和将用户的信息按选定的路由正确地传送到目的节点两个功能。

路由选择算法是网络层的主要功能,它关心的问题是确定从源到每个目的节点之间的可行路径(路由)。路由选择算法既要使网络的信息通过量(吞吐量)最大,又要使网络的平均分组时延最短。一般要求在轻或中等业务负载情况下,路由算法可以减少每一个分组的平均时延;在高业务负载情况下,算法在保证相同的时延条件下可以增加网络的信息通过量,这使得路由算法通常相当复杂。一个好的路由算法是依赖用户优化的目标函数。一般来说,路由选择算法应该设法满足如下目标中的一个或多个。(1)快速而准确地传送分组数据。路由选择算法必须能够正确地工作,如果网络中存在一条到目的节点的路径,路由选择算法必须能够正确找到这条路径。这就要求网络的各子网节点相互协调,包括同一节点的不同协议层间、不同节点同一层的对等通信协调。(2)路由选择算法能够适应节点或链路的故障及网络拓扑变化。在网络运行的设备和传输线路容易出现故障的情况下,当设备发生故障时,路由算法要对故障业务进行重新配置路径和对系统维持的数据库进行更新。(3)能够适应不断变化的源和目的节点业务量负载。网络的业务量负载是动态变化的,自适应的路由算法能够基于当前的业务负载来调整路径,以达到较高的性能。(4)路由选择算法具有暂时避开分组拥塞的能力。路由选择算法应该避开严重拥塞的链路,并且常常希望平衡每条链路的负载,当网络部分区域拥塞时,路由算法必须能够修正路由。(5)确定网络连接和避免路由环路的能力。路由选择算法为了查找优化的路径,需要了解网络的连通性或可达性信息。大型网络路由算法常采用分布式计算。由于分布式计算中不一致的信息可能会导致网络产生路由环路,因此路由选择算法应该避免持续的环路路由。(6)路由算法具有低开销和易实现特点。路由选择算法一般通过和其他路由算法交换控制信息来获得连通性信息,这些信息是一种带宽使用上的开销,算法应该最小化这种开销。

一个理想的路由算法具有适应网络变化的灵活性、快速收敛性、稳定强壮性、简单易实现、正确完整性、普适用户的公平性和最佳性。一个实际的算法应尽量接近理想算法。路由算法需要在什么时候执行,取决于网络中采用的路由方式。

目前已经有许多种路由选择分类算法,大致可分为确定路由和自适应路由选择算法;也可分类为集中式路由和分布式路由;还可分类为静态路由和动态路由。其中确定路由算法又分为固定路由表的静态路由和洪泛式路由;自适应路由选择算法分为路由控制中心负责的集中式路由、各节点交互确定的分布式路由、各节点单独确定的隔离式路由和混合式路由。

① 静态路由选择算法,也称查表法或固定路由法。网络管理员在路由选择开始前,就已为固定网络建立路由映射表,如果网络管理员不改变它们,这些路由映射表将保持不变,即网络中每一对源节点和目的节点之间的路由都是固定的,无论是数据报还是虚电路,用户的所有分组数据从指定源节点到目的节点沿着相同的路径传送。一般来说,当节点或链路故障时,固定路由算法改进办法是为每个节点提供一个次佳路由,当第一路由失败时启动次佳路由。固定路由选择策略的优点是处理简单,在可靠的中、低等负载稳定的简单网络中可以很好地运行。缺点是缺乏灵活性,不能对网络的拓扑变化做出反应,无法适应网络拥塞和故障情况,不适应大型和易变的网络环境。一般在小规模的专用网络中可采用固定路由算法。

② 洪泛式(flooding)路由选择算法,也称为扩散式路由算法。它的基本思想是让每个节点收到分组后,即将其发往除分组所在节点外的其他相邻节点,相邻的节点再转发向它们的相邻节点,直到分组到达网络所有节点,不需要任何网络信息。可以想象,按照这种算法,网络上的分组会像洪水一样泛滥起来,造成大量的分组冗余,导致网络出现拥塞现象。为了限制分组的传输次数,一般有3种方法:一是在每个分组的头部设计一个计数器,用来统计分组到达节点的数量,当计数器超过一规定值(如端到端最大段数)时,将分组丢弃;二是在每个节点上建立一个分组登记表,不接收重复的分组,同一个分组的副本将经过所有的路径到达目的节点,目的节点接收最先到达的副本,后到达的被丢弃,如节点B从 A接收一个广播分组,则B不会将该分组再转发给A;三是只选择距目标节点近的部分节点发送分组。

洪泛式路由选择算法的优点是具有较强的鲁棒性和很高的可靠性。由于分组要经过源节点到目的节点之间的所有路径,所以即使网络出现严重故障,只要在源节点和目的节点之间至少存在一条路径,分组都会被送达目的节点。同时,所有源节点直接或间接连接的节点都会被访问到,所以洪泛式路由算法被应用于广播。该算法的优点是网络高度稳健,特别适用于可能遭受严重损坏的军事网络,还可用于虚电路路由的初始建立及信息发布;缺点是产生的通信量负载过高,额外开销过大,导致分组排队时延加大。洪泛式路由选择算法适用于规模较小、可靠性要求较高的网络。

③ 自适应路由选择,是指路由选择根据网络状况的变化而动态改变,动态改变路由的依据条件是网络出现的拥塞和故障。当网络中的一部分资源发生了拥塞,分组传送就要尽量绕过拥塞区域,而不是从发生拥塞的区域通过;当网络中的一部分资源出现了故障,分组传送就要避开发生了故障的节点或中继线。实现自适应路由选择必须在节点之间交换网络状态信息,交换的信息越频繁,路由选择依据的条件越及时准确。但是,节点间交换的信息会增加网络的负载,导致网络性能下降,因此需要寻找一个既使网络状态信息能得到及时交互,同时又不增加过多的额外负载的平衡点。虽然使用自适应路由选择会给网络带来额外的通信量开销,并使得路由选择算法复杂,但是由于这种方法能够提高网络的性能,路由选择灵活,所以是目前使用最普通的路由选择策略。

④ 集中式路由算法,是指网络的路由通过路由控制中心计算得到,该中心定期地收集链路的状态信息,如当前运行的相邻节点名称、当前缓冲队列长度等,并据此为每个节点计算一张最佳路由表,更新前次路由,周期性地向网络中各节点公布此路由信息。该算法存在的问题是网络状态信息的实时性差,抗故障能力差,会导致网络出现不稳定的现象,适用于小型网络。

⑤ 分布式路由算法,根据网络中各节点周期地交换网络路由信息和状态信息,独立地计算到达各节点的路由,不断根据网络的新状态更新路由。

⑥ 热土豆算法。通常每个节点要为其连接的各相邻节点建立一个分组队列,各节点收到一个分组后,为了尽快脱手,要将其划分在最短的队列中,而不管该分组的目标节点是什么。热土豆算法仅仅把本节点的信息用于路由选择,属于自适应隔离式路由算法中的一种。

⑦ 最短路由。许多实际的路由算法都基于最短路由,最短指的是源和目的节点之间的最短长度,其中长度可以是物理距离的长短、时延大小、节点队列长度等。最短路由算法通过寻找最佳的相邻节点,并通过该邻节点实现到达目的节点的最短路由。

⑧ 最佳路由。最佳路由是为了克服最短路由存在的两个问题,将最短路由和流量分配相结合的一种路由算法,实现网络的最大吞吐量和最小时延。最短路由算法的缺点:一是每对节点之间仅有一条路由,因而限制了网络的吞吐量;二是路由无法适应业务量的变化。

对于通信网来说,选择哪种路由需要根据网络结构和业务负载变化及性能要求情况而决定,适应不同业务特性动态地、按需地为呼叫连接建立路由。路由选择算法通常与流量分配与控制算法一起相互作用,共同确定网络的信息通过量和时延参数。1.3.2 流量分配与控制

在一个实际的通信网中,每个节点的存储容量、每条传输链路的传输容量和信息处理能力都是有限的,这就决定了网络可以承载的业务量是有限的。当外部输出业务量大于网络能处理的业务量时,或者发送端送出的业务量大于接收端可接纳的业务量时,若不采取流量分配与控制措施,将使出现资源不够的瓶颈链路和节点队列增加,缓冲区耗尽,造成网络的拥塞和网络时延的迅速增加,使网络的吞吐量迅速下降,分组被丢弃或超过时延规定的要求,严重影响网络的性能。当拥塞情况严重时,分组数据在网络中无法传送,不断地被丢弃,引起源节点更多地重发数据,占用的缓冲区得不到释放,引起更多的数据丢失,这种连锁反应很快波及全网,使通信无法进行,从而使网络处于“死锁”(Deadlock)状态。对网络流量是否进行控制,在高负载时对网络性能的影响很大,图1-6表示了拥塞对网络的吞吐量和时延的影响。图1-6 拥塞对网络性能的影响

在图1-6中,网络传送的分组速率是输入负载或分组提交给网络的速率的函数。理想的情况是:只要输入业务负载低于网络容量,网络应传送全部已提交的分组,分组的平均时延主要是传输时延;当输入负载超过网络容量时,网络应继续以最大容量传送分组,但分组在各节点需要排队缓存,平均时延快速增加。实际情况是:当网络无流量控制机制时,只有当输入负载低于某一定值时,网络才能传送全部输入负载,当输入负载的增长超过这一规定值时,网络的实际吞吐量与理想情况开始偏差,分组平均时延增大,随着输入负载的继续增加,无流量控制的网络吞吐量开始下降,时延急剧增加。输入网络的业务量越高,实际传送的业务量越低,足够高的输入负载会导致死锁,网络中几乎没有成功传输的分组。网络采用流量和拥塞控制,保证网络在过负载情况下也能有效工作。但是,网络运行流量控制程序需要一定的额外开销,使受控网络的吞吐量低于无流量控制网络的吞吐量,随着输入负载的增加,吞吐量达到最大,但其最大值还是低于理想情况下网络的吞吐量。

通信网络是一个复杂的信息系统,在网络协议的每层都可能产生流量拥塞和控制管理拥塞的策略。物理层提供网络最基本的可用资源,如各种传输媒介的容量、差错率、带宽和传信速率等;数据链路层提供业务故障重传策略、乱序分组的缓存策略、控制应答的策略和流量控制策略;网络层提供子网内信息的传送方式、分组排队和服务策略、分组拥塞丢弃的策略、路由选择算法和分组寿命管理;传输层提供数据重传策略、乱序缓存策略、应答策略、流量控制策略和定时确定。

防止拥塞和死锁的办法是制定网络的交通规则,进行流量控制。流量控制可以使用网络的数据发送和处理速度平滑均匀,是解决网络资源有限的一个有效手段。进行流量控制的基本策略是要么增加用户可用资源,要么限制用户资源需求。1.4 通信网的质量要求

通信网关心的主要问题是如何快速而准确地将消息传送到目的方。用户的信息常常要跨越多个网络,数据比特如何在不同的传输媒介上传输?如何检测和纠正比特传输错误?如何保证对比特流进行分段(组帧)以达到最佳的性能?我们不仅要关心通信网中两个相邻节点之间的链路传输的可靠性和有效性,还要关心穿越不同传输媒介的网络的任意两个节点之间传输的可靠性和有效性。为了使通信网能快速、有效、可靠地传递信息,通常对通信网提出接通的任意性与快速性、信号传输的透明性与传输质量的一致性、网络的可靠性与经济合理性这3项要求。

1.接通的任意性与快速性

接通的任意性与快速性,是指网络能够实现任意转接和快速接通。影响接通的任意性与快速性的主要因素包括:

● 通信网的拓扑结构不合理会增加转接次数,使阻塞率上升、时延增大;

● 通信网的网络资源不足造成增加阻塞概率;

● 通信网的可靠性降低,会造成传输链路或交换设备出现故障,甚至丧失其应有的功能。

2.信号传输的透明性与传输质量的一致性

信号传输的透明性是指在规定的业务范围内对用户信息不加任何限制,都可以在网内传输;传输质量的一致性是指网内任何两个用户通信时,应具有相同或相仿的传输质量,而与用户之间的距离、环境和所处位置无关。传输质量主要包括接续质量和信息质量,其中接续质量表示通信接通的难易和使用的优劣程度,具体指标主要有呼损率、时延、设备故障率等,信息质量是信号经过网络传输后到达接续终端的优劣程度,受到终端、信道失真和噪声的限制,具体指标主要有数据通信的比特误码率、语音通信的响度当量等,不同的通信业务具有不同的质量标准。通信网的传输质量直接影响通信的效果。因此要制定传输质量标准并进行合理分配,使网中的各部分均满足传输质量指标的要求。

3.网络的高可靠性与经济合理性

通信网应具有较高的可靠性,任何时候都不希望网络发生故障或通信中断。因此,通信网中的交换设备、传输设备、组网结构都要采取多种措施确保其高可靠性;对于网络内的关键设备及模块,还制定了相关的可靠性指标,如平均系统中断时间、平均故障间隔时间(两个相邻故障间隔时间的平均值)等。通信网的组建还要考虑建设费用和日后的维护费用是否经济可行。因此,提高可靠性往往要影响其经济合理性,应根据实际需要在可靠性与经济性之间取得折衷和平衡,处理好两者关系。

以上是对通信网的基本要求。对于不同业务的通信网,上述各项指标的具体内容和含义将有所差别。电话通信网的服务质量表明用户对电话网提供的服务性能达到满意的程度,是各种服务性能的综合体现。电话网的性能要求主要包括接续质量、传输质量和稳定质量。其中,接续电话通信网的接续质量是指用户通话被接通的速度和难易程度,常用呼损率和接续时延表示;传输质量是用户接收到的语音信号的清楚逼真程度,常用响度、清晰度和逼真度来衡量;通信网的稳定质量是指当传输、交换等设备发生故障和话务异常时可以维持正常业务的程度,度量电话通信网可靠性指标,包括失效率(设备或系统工作 t 时间后,单位时间内发生故障的概率)、可用度、平均故障间隔时间和平均修复时间等。

同时,通信网在组网结构、信令方式、编号计划、计费制度、网络管理模式方面,都要考虑适应未来新业务引入和新技术发展。传统的通信网是为支持单一业务而设计的,不能适应新业务和新技术的发展,而面向未来的下一代网络应能适应不断发展的通信技术和还未知的新业务应用。第2章通信网图论基础

通信网是一个由多系统、多设备和传输系统构成的复杂且庞大的网络,要设计能够满足有效性和可靠性能指标的网络,要求设计人员掌握相当的网络理论基础和网络分析方法。通信网的拓扑结构不但影响网络造价和维护费用,还对满足网络的各种性能指标起着重要作用。通信网拓扑结构及优化也是通信网规划和设计中的重要问题。通信网由终端节点、交换节点和传输链路组成,从数学模型上来说就是一个图论的问题。图论作为组合数学的分支。近年来,生产管理、军事、交通运输、计算机和通信网络等方面的大量问题的出现,大大促进了图论的发展。特别是电子计算机的大量应用,使大规模问题的求解成为可能。图论近年日益应用于各种电网络、通信网络、交通运输网络、传输网络,电路设计、数据结构、故障诊断、人工智能、模式识别、地图着色、情报检索等,广泛应用于物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论,也应于社会科学与经济管理等学科领域,如语言学、社会结构、经济学、动力学、遗传学。本章从通信网的需要出发来认识图论的基础知识和表示方法,是后续章节讨论最短路径和流量问题及优化的必备基础。2.1 抽象图和网络的基本概念2.1.1 抽象图的定义

抽象图(graph)用节点和边来反映实际网络中的具体事物和事物间相互关系,而连线的长短曲直不影响我们要研究的事物或对象之间的关系。

在通信网络中,用节点表示通信站,边表示通信站间的通信线路,就可构成一个反映通信站间通信通路连接情况的抽象图;用节点表示端点设备和交换设备,边表示传输线路,就构成一个通信网抽象图。若某航空公司要为国内几个重要城市提供服务,该航空公司有一张航空线路图,当用点表示城市,如果两个城市之间有该航空公司的直达航班,那么航空线路图中就有一条线来连接这两个城市,这样得到的图就是反映航空线路的抽象图。在化学应用中,抽象图可以对原子结构进行建模,用节点抽象原子,用边来抽象原子间的化学键。在商业应用中,仓库和零售店进行建模,节点代表仓库或零售店,边代表每个仓库或零售店间的关联。抽象图还用于考试安排、比赛安排、遗传、任务分配、资金分配和城市规划等。

抽象图一般记为:G(V,E)或 G(V(G),E(G)),简记为 G。其中,V或 V(G)是节点的集合(vertex set),V={V ,V ,…,V },12n节点对应于网络中的具体事物,在图中用小黑点或小圆点表示点;E 或E(G)是边或点序对表示的边集合(edge set),E={e ,e ,…,e },12b或用有序二元组表示边集,E={(V,V),(V,V),…,(V,V)},1213km边对应于网络中具体事物间某种关联的关系,图中用连续曲线或直线表示,其长度形状与连通关系无关。在抽象图的节点集合与边集合中,V 集可任意给定,而 E 集合只是代表 V 集合中二个元素之间的关系。如果边 e 与节点 (V ,V ) 相对应,则称 V 、V 是 e 的端点,kijijk记为 e = (V , V ),称节点 V 、V 与边 e 关联;若 V = V ,两个kijijkij节点是同一端点,则称 e 为自环。当 V对V有某种关系等价于V对Vkijji有某种关系,则称抽象图为无向图,无向图的几何表示方式是边上无方向箭头;反之,称为有向图,有向图的边上有方向箭头。边有起点和终点之分。例如:在程度流程图、状态转移图、电路的电流网络和信号流图中,V可以转移到V,但不一定意味着V可以转移到V,这ijji样的关系是有方向的,需要用有向图表示。图2-1是某无向抽象图的几何表示。

在图2-1 中,抽象图的节点集合V = {V ,V ,V , V ,V ,12345V };边集合E = {e ,e ,e ,e ,e ,e ,e ,e,e,e},60123456789或E={(V,V),(V,V),(V,V),(V,V),(V,V),(V,1211221523343V),(V,V), (V,V),(V,V),(V,V)}。646455611图2-1 无向抽象图的几何表示

抽象图只规定了拓扑特性而并不考虑具体几何特性,边的形状和长短不影响图的拓扑特性。在实际网络中,边的长短值对网络的特性有影响,就需要对节点或边赋值,这样的图称为加权图。若对图G (V,E) 中的每一条边都赋以一个实数p ,则称图G为有权图或加权图, kp称为边e的权值。根据研究需要,权值可以表示不同的含义。通信kk网中,节点代表交换局,边代表信道,这时节点的权值为该交换局的造价、交换容量等,边的权值可以为该信道的造价、容量、长度和时延等。图2-2是一个加权图。图2-2 加权图

在描述抽象图时,常需要用到下列的一些术语。环(loop),也称圈或自回路,指两端点相同的边,在图2-1中,边e就是该图的9环。重边(multi-edges),也称或并联边、平行边,是指两点间有多条边存在。若点i,j间有k条边存在,一般记为:(i,j),(i,j),…, 12(i,j),其中 k≥2。边与连接它的点互称为关联(incident)。连接一k条边的两节点称为邻接(adjacent),与节点i邻接的节点称为节点i的邻接节点,如果有两个节点在图G中不邻接,就称它们是独立的。没有任何边的图称为空图(empty graph),记为∅。只有一个节点的图称为平凡图(trivial graph),对应地,其他所有的图都称为非平凡图。无环且无重边的图称为简单图(simple graph)。平凡图不一定是简单图(有自环的平凡图就不是)。节点集V 和边集E 有限集合的图称为有限图(finite graph),否则称为无限图(infinite graph)。本书仅限于有限图的研究和讨论。

在研究和描述图的性质及图的局部结构中,子图占有重要的地位,下面引入子图、补图、生成树和补树的概念。

1.子图

子图(subgraph):G 和 G 均为图,且 V (G ) ⊆ V (G),E (G ) sss⊆ E (G),则称 G 是 G 的子图,记为G ⊆ G。ss

真子图(proper subgraph):若G ⊂ G,且G ≠ G,称G 为G 的sss真子图,记为G ⊂ G。s

生成子图(spanning subgraph):若G 是G的子图,且V (G ) = ssV(G),则称G 为G的生成子图。s

导出子图(induceed subgraph):又称区域子图,若图G 的子节点集V ⊆ V(G),由两端点均在V 中边的全体为边集的子图就称为图ssG 的导出图,记为G (V )。s【例2-1】:如图2-3所示,已知图G及其子图G和G,判断哪个是12导出子图?图2-3 图G及子图

解:图G 的节点集合V(G ) = {V ,V ,V },在原图G 中仅节11245点V 、V 、V 所关联的所有边 (V ,V )、(V ,V )、(V ,V ),245242545由于图G 没有包括边 (V ,V ),因此 G 不是G 的导出子图。而G14512包括了图G中节点V、V、V关联的所有边,G是G导出子图。2452

若两个子图没有共同的边,则这两个子图是边不相接的子图;若两个子图没有共同的节点,则这两个子图称为节点不相接的子图。显然,两个节点不相接的子图必定是边不相接子图。但是反过来,边不相接的子图可能是节点相接的子图。如图2-1中的子图E(G)={(V, a2V ),(V ,V ),(V ,V )},另一个子图E(G ) = {(V ,V ),(V ,33445b464V )},这两个子图有公共边(V , V ),因此称为边相接子图。图5462-1 的子图 {(V ,V ),(V ,V ),(V ,V )}和{(V ,V ),(V , 343646455V )} 是边不相接子图,但它们有公共节点4,因此是节点相接的子图。6

由图G的相互独立(边的两个不同节点不邻接)的边组成子集合称图G的匹配,其中边数最大的匹配称为最大匹配,它们都是图G的子图。

2.补图

若G为简单图,且为图G的子图,满足下列条件的子图就称为Gss的补图。

①E={uv|节点u,v在G中邻接,在G中不邻接},即属于G、s但不属于G的子图G边的集合。s

②V={u|不属于G的节点及与E的边关联的节点集s合}。

图G和图称为互补。显然,图G和边不相接,但不一定节ss点不相接。对图G来说,空图的补图是G本身,而G的补图是空图。【例2-2】:如图2-4所示,已知图G和它的子图G,求G的补图。ss

解:在图2-4(b)中,补图的边集E={(2,5),(2,4)};节点集V={2,4,5};比较原图G,G的补图几何形状s如图2-4(c)所示。图2-4 图G及补图 s

3.生成树图

树图,作为一类特殊的图,是边数最小的连通图,它在计算机科学和最优网络研究领域具有广泛的应用。树图概念是基尔霍夫在解决电路理论中求解联立方程问题时首先被提出来的,可惜他的发现超前于时代,长期没有被重视。树与图中其他一些基本概念,如回路、割集等有着密切关系,是图论中比较活跃的研究领域。现在,树的概念已经越来越广泛地被应用到各个学科领域。下面就生成树的概念和它们的性质进行讨论。

当且仅当一个图的生成子图是连通图且不含回路时,这个生成子图称为生成树(tree),如图2-5所示。树图的每一条边称为树枝(branch)。图2-5 连通图G及生成树T

图2-5中,图(a)是连通图,但含有回路,因此它不是树图;图(b)是图(a)的一个连通且不含回路的生成子图,因此,它是图(a)的生成树图。生成树的每一个顶点都是割点,一个生成树具有下列特征。(1)若图T是生成树,则任意两顶点间必有一条且仅有一条通路。由于生成树图一定是连通的,所以树中任意两顶点间必有通路,如果两顶点间有两条不同的通路存在,则必将出现回路,此与树的定义矛盾。(2)在生成树中不相邻的两个顶点间添上一条边,则恰好得到一条回路。(3)设生成树T含有n个顶点,那么它的边数为n−1。(4)生成树图T连通且其任意一条边均为割边。如果在图G中去掉一条边后,图的连通子图数增加,则此边称为图T的割边(cutedge)。(5)生成树是连通且无回路的图,同时,生成树是二分图。

根据生成树图定义可知,连通图G的生成树不是唯一的。在图2-6中,图G中就有8棵生成树,我们仅画出了其中的4棵生成树。

计算图的生成树各边的加权值和,得到的一个和最小的生成树称为最小重量生成树。图2-6 图G及其生成树

一个连通图有许多不同的生成树,一个图的全部互异的生成树的个数通常是一个很大的数目。对于通信网来说,利用生成树来实现广播是比较经济的,但每一条链路的成本或时延是不同的,这时就要考虑树中各链路的重量(成本或时延),最小重量生成树是广播最经济的方案。

4.补树

图G中一棵生成树T的补图,称为补树。其中,补树的边称为弦或连枝(cotree)。

若一个连通图G含有n节点,b条边,则其生成树T的边数为n−1条树枝;补树的边数为b − (n−1) 条连枝。

由于图G的生成树T的边集是连通图G的全部顶点边数最少的集合,因此,在生成树图T中加进一条连枝,将产生一个回路,称为图G关于生成树T的一个基本回路,图G关于生成树T 可生成b − (n−1) 个基本回路。

5.生成树的距离和中心

在一个连通路中,节点i与j之间的距离d (i,j) 是它们之间最短路径的段数,即最短路径的边数。距离的定义也可以扩展到一般连通图的定义。在生成树图中,由于任意两点之间只有一条路径,因此距离的确定要容易很多。如图2-6 的生成树T 中,d(1,2) = 1,d(1,3) 1= 2, d(1,4) = 3,d(2,3) = 1,d(2,4) = 2,d(3,4) = 1。

在一般连通图中,确定两节点的最短路径却要复杂一些。在图2-7中,节点1和2之间的一部分路径为a→e,a→c→f,b→c→e,b→f,b→g→f和b→g→l→m等。找出所有路径后,才可以比较得到最短的路径有两条,即a→e和b→f,每条路径的距离为两段边构成,即最

试读结束[说明:试读内容隐藏了图片]

下载完整电子书


相关推荐

最新文章


© 2020 txtepub下载