（应用数学专业论文）光纤网络的弧负载指标及波长分配问题.pdf

中文摘要 摘要 光纤网络是当今及未来信息网络的核心技术之一，主要适用于可视 电话、远程教育、远程医疗、家庭办公等新型业务。光纤网络可用一个 弧对称( 即图中有一条从u n v 的弧当且仅当存在一条从”到 的弧) 的有 向连通图表示，其路由集是满足所有业务需求集的有向传输路径的集 合。给定一个路由集r ，其点( 或弧1 负载指标( f o r w a r d i n gi n d e x ) 定义为兄中 通过每个顶点( 或弧) 的路径数目的最大值。进一步地，图g 的点( 或弧) 负 载指标为满足业务需求集的所有可能路由集的点( 或弧) 负载指标的最小 值，记为( g ) ( 或亓( g ) ) 。光网络中的路由问题( t h er o u t i n gp r o b l e m ) 是指 构造一个路由集，使得此路由集的弧负载指标达到最少。给定网络的一 个业务需求集，我们需要在各需求集之间建立一个光通道，并为其分配 一定的波长，使得通过同一条弧上的任何两个光通道分配不同的波长， e x ( r ) 为所需的最小的波长数目。令x ( v ) = 吨n x ( r ) ，则波长分配问 题( t h ew a v e l e n g t ha s s i g n m e n tp r o b l e m ) 就是要构造一个路由集和波长分配 方案，使其所用的波长数达到x ( g ) 。考虑到波长资源的有限性，因此优 化光通道的路由和波长分配方案成为网络设计的核心问题。已证实确 定x ( r ) 是一个n p - - 完全问题，但对一些特殊图如树、圈，其波长数目是 可确定。 本文主要考虑弧负载指标。首先给出一般图在点负载指标、最大度、 最小度等条件下，弧负载指标的上、下界。接着给出2 连通图的弧负载 指标的一个上界。进一步地，还研究了直径为2 的2 一连通图弧负载指标， 证n g ( c ) 竹一2 ( 其中礼为顶点数) 。文章还构造出折叠立方体的路由方 案，由此计算出折叠立方体的弧负载指标。利用该路由方案，确定了 当n 为偶数时，折叠立方体的波长数。 关键词：弧负载指标；折叠立方体；波长分配 英文摘要 a b s t r a c t o p t i c a ln e t w o r ki se m e r g i n ga sk e yt e c h n o l o g yi nc o m m u n i c a t i o nn e t w o r k s a n di se x p e c t e dt od o m i n a t em a n ya p p l i c a t i o n s ，s u c ha sv i d e oc o n f e r e n c ee e m - m u n i c a t i o n s ，s c i e n t i f i cv i s u a l i z a t i o n ，r e a l - t i m em e d i c a li m a g i n g ，h i g h - s p e e ds u p e r _ c o m p u t i n ga n dd i s t r i b u t e dc o m p u t i n g a no p t i c a ln e t w o r ki sd e f i n e da sas y m - m e t r i cd i r e c t e d ( i e t h e r ei sa l la r ef r o mav e r t e xut ovi fa n do n l yi ft h e r ei s a na r cf r o mvt o “) c o n n e c t e dg r a p ha n dar o u t i n gc o n s i s t so fac l a s so fp a t h s c o n n e c t i n ge v e r yp a i ro fv e r t i c e si nt h er e q u e s t g i v e nar o u t i n gr ，t h ev e r t e x ( o r a r c ) 一f o r w a r d i n gi n d e xi st h em a x i m u mn u m b e r o fp a t h sp a a s i n gt h r o u g ha n yv e r - r e x ( o ra r c ) i nr t h em i n i m u mv e r t e x ( o ra r c ) f o r w a r d i n gi n d e x o v e ra l lp o s s i b l e r o u t i n g so fag r a p hgi sc a u e dt h ev e r t e x ( o ra r c ) 一f o r w a r d i n gi n d e xo fga n dd e - n o t e db yf ( g ) ( o r 膏( g ) ) t h er o u t i n gp r o b l e mi st od e s i g nar o u t i n gt or o u t et h e r e q u e s ts u c ht h a tt h er o u t i n gn f i n i m i z e st h ea r c f o r w a r d i n gi n d e x aw a v e l e n g t h a s s i g n m e n to far o u t i n gr i st oa s s i g nac o l o rt oe a c hp a t hi nrs u c ht h a tt w o p a t h ss h a r i n ga na r eh a v ed i s t i n c tc o l o r sa n dt h em i n i m u mn u m b e ro fc o l o r so v e r a l la s s i g n m e n t si sd e n o t e db y ) ( ( 冗) l e tx ( a ) = 唾n x ( r ) ：ri sar o u t i n go fg t h ew a v e l e n g t ha s s i g n m e n tp r o b l e mi st oc o n s t r u c tar o u t i n ga n da w a v e l e n g t h a s s i g n m e n tw h i c hm e e t st h ei n d e xx ( g ) ，i nt h i sp a p e r ，w eo n l yc o n s i d e rt h e a l l - t o - a l ln e t w o r k s i ti sw e l l - k n o w nt h a tt h ep r o b l e mo fd e t e r m i n i n gx ( r ) i s n p - c o m p t e t e h o w e v e r ，i ti ss o l v a b l ef o rs o m es p e c i a lg r a p h ss u c ha st r e e s ，r i n g s e t c f i r s t ，w eg i v es o m eb o u n d sf o rt h ea r c - r e r w a r d i n gi n d e xi nt e r m so ft h e v e r t e x - f o r w a r d i n gi n d e x ，m a x i m u md e g r e e ，m i n i m u md e g r e e ，d i a m e t e r ，c o n n e c t i v i t ya n d t h es u mo fd i s t a n c e sb e t w e e nt w ov e r t i c e s w ea l s ow o r ko u tt h ea r c - f o r w a r d i n g i n d e xo ft h ef o l d e dh y p e r c u b e f u r t h e r m o r e ，w h e n 竹i se v e n ，t h ei n d e xx ( g ) f o r t h ef o l d e dh y p e r c u b ei sd e t e r m i n e d k e yw o r d s ：a r c - f o r w a r d i n gi n d e x ；f o l d e dh y p e r e u b e ；w a v e l e n g t ha s s i g n m e n t i i 厦门大学学位论文原创性声明 兹呈交的学位论文，是本人在导师指导下独立完成的研究成 果。本人在论文写作中参考的其他个人或集体的研究成果，均在 文中以明确方式标明。本人依法享有和承担由此论文产生的权利 和责任。 声明人( 签名) ：嘧丽姗 枷6 年r 月f d 日 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规定。厦 门大学有权保留并向国家主管部门或其指定机构送交论文的纸 质版和电子版，有权将学位论文用于非赢利目的的少量复制并允 许论文进入学校图书馆被查阅，有权将学位论文的内容编入有关 数据库进行检索，有权将学位论文的标题和摘要汇编出版。保密 的学位论文在解密后适月j 本规定。 本学位论文属于 l 、保密() ，在年解密后适用本授权书。 2 、不保密( ) ( 请在以上相应括号内打“4 ”) 作者签名： 寿，丽螂 导师签名： 日期：州年，月o 日 日期：年月 臼 第蘸g l 言 第一章引言 2 l 世纪是一个以网络为核心的信息时代，人们对信息的需求与日俱 增。各类新型业务，诸如远程教育、远程医疗、可视电话、家庭购物、 家庭办公等正在蓬勃发展，所有这些都必须依靠完善的网络。而正是这 些与日俱增的需求量导致原有网络的“枯竭”，人们呼唤着新一代网络 全光网络的诞生，光纤网络是未来信息网络的核心l 一3 1 。 光纤网络( o p t i c a ln e t w o r k ) 以光节点取代原有网络的电节点，并用光 纤将光节点互连成网，即在光域中完成信号的传输、交换等功能，克服 了原有网络在传送和交换时的电子瓶颈，减少了信息传输的拥塞，大 大提高了网络的吞吐量【4 】。这里的光网络，是指以光纤为传输媒介的通 信网络。当前信息传输系统有两大核心技术，光纤通信和无线通信。 光纤通信一一极大带宽；无线通信一一无处不在。光纤通信具有频带 宽，容量大的特点。单模光纤在1 2 0 0 n m 至1 6 0 0 n m 波长范围内衰耗很低， 一般在0 3 d b k m 左右，频带超过5 0 t h z 。这一频带宽度超过了目前世界 上所有通信技术使用到频带好几个数量级。技术上，设最高频谱效率 为0 s b s h z ，可安排5 0 0 路4 0 g b s ，光纤容量可达2 0 t b s 。因此，一根光 缆( 多纤) 的总容量可达p b s 量级( 1 p = 1 0 0 0 t 一1 0 1 5 ) 。所以说，光纤是保 证通信大容量扩展的最佳媒介。 光波分复用光网络是目前较为成熟的光网络。光波分复用技术( w d m ： w a v e l e n g t hd i v i s i o nm u l t i p l e x i n g ) 是在一根光纤中同时传输多波长光信号 的一项技术。其基本原理是在发送端将不同波长的光信号组合起来( 复 用) ，并耦合到光缆线路上的同一光纤中进行传输，在接收端又将组合 波长的光信号分开f 解复用) ，并作进一步处理，恢复出原信号送入不同 的终端5 1 。w d m 技术充分利用了光纤的巨大带宽资源，使一根光纤的 传输容量比单波长传输增加几倍至几十倍，从而增加光纤的传输容量， 降低成本，具有很大豹应用价值和经济价值。w d m 光通信最初用于增 加通信网络容量以满足互联网用户不断增长的需求，为了进一步增加容 量，沿传输链路的光一电一光转换需要进一步减少，因而推动了全光网的 第一章引言 发展。既然是波长通道而不是电子编码报头沿着通信网络进行必要的交 换和路由，所以w d m 成为这种发展的中心。本文中所讨论的光网络均 为w d m 网络。波分复用( w d m ) 光网络是一项极具潜力的技术，它可 满足未来用户对高容量带宽的需求。根据所支持的业务量类型，w d m 光 网络可分为光路交换的光网络和分组交换的光网络6 1 。 1 光路交换的w d m 光网络；在光路交换的光网络中，通过波长路由器 在接人节点间建立光通路，业务量经由光通路传送。目前，日本、美国 及欧洲的一些发达国家都已建立了采用光路交换技术的w d m 试验网， 如l o n d o nf i b r en e t w o r k ，欧洲r a c e s 1 划的多波长传送网( m w t n ) 等。 光路交换的w d m 网有两种主要的拓扑结构，一是广播式星型光网络， 另一是波长选路的光网络。广播式的星型网络是在网络的发送侧的每一 端口提供一个单独的光频率，在网络的中心采用光的星型耦合器将所有 的传输信号合并，然后再将这些广播式的信号混合后送入所有接收侧的 端口中。通常在接收端采用可调谐的接收设备，以便能够动态接入所需 波长。广播式星型网的优点是它能够对不同调制格式的信号“透明”， 信号的格式由不同节点间的发送设备和接收设备来决定，而光选路只经 广播方式简单完成，因此，不同速率和不同格式的信号可同时在一个网 络中共存。广播式星型网络的缺点主要是费用高、功率浪费和网络节点 的最大数受限于可利用的波长数目等。一般来说，星型网络主要适用于 对本地和市域计算机网进行互连，而不适合在大规模的干线网上采用。 波长选路的光网络是指每一光通道分配一个单一的波长，由于在实际中 可获波长数有限，同一波长只能用在不同光纤的路由中，波长争用问题 只能利用通路以及相应的传送资源的合理分配来解决。目前，波长选路 的交叉连接还不能进行网络的完全重组，只能在输出和输入复用器间建 立连接，使输出复用器的人口保持同一波长，这对于常出现的业务转换 并不十分灵活。为了提高网络的灵活性，波长选路的光网络将在选路设 备中使用波长转换器来进行网络动态重组，它可以最大限度地再利用有 限的可获通道数。然而，光的波长转换器还没有完全研制成功，因此目 前的波长转换还采用光一电转换和再生装置。在实际中，很多光路交换 的w d m 网络的设计，将广播式的星型网络和波长选路的光网络结合使 用，以通过波长再利用来增加阀络的可扩展度。广播式的星型嘲络通常 2 第一尊引言 用于本地网中，波长选路的网络比较适合用于广域网中。 2 分组交换的w d m 光网络；分组业务具有很大的突发性，如果用光路 交换的方式处理将会造成资源的浪费。在这种情况下，采用光分组交 换将是最为理想的选择，它将大大提高链路的利用率。在分组交换网 络里，每个分组都必须包含自己的选路信息，通常是放在信头中。交 换机根据信头信息发送信号，而其它的信息如净荷则不需由交换机处 理。光交换机通常是分布存储式的交换机。光的分组交换一般有两种方 法。种是比特序列分组交换( b s p s ) ；另一种是并行比特分组交换 ( b p p s ) 。b s p s 由电分组交换直接演化而来。二进制的比特序列分组交 换是最简单的分组交换方式。对于一个结定波长波道的分组交换，信头 采用二进制比特顺序编码，通常使用开关信号。如果将这些二进制的比 特序列分组交换信道进行波分复用，可以增加传输带宽，因为多个分组 信号可以同时在不同的波道上传送。不过，这些通道信号必须在进入交 换机之前解复用以便进行选路，然后在交换机输出端再复用。b p p s 可以 采用两种编码技术来实现，一是副载波复用，另一是多波长的b p p s 。在 这两种情况中，并行比特分组交换的编码技术采用同一光纤中的不同波 道来传送信头和负载信息，可保证负载和信头并行传送，因此可增加网 络的吞吐量。多波长的分组交换比较适合于光网络。首先，它可采用简 单的无源光滤波器从分组信号中提取信头；其次，在交换机内对信头进 行处理，使得分组路由对负载是透明的。第三，由于每波长使用单独的 光源，信头和负载光源是分开的，因此没有功率损失。目前，由于一些 技术限制，光分组交换一时还难于实现。根据现有的技术条件，光分组 交换所需的光存储器、信头识别和处理装置还不可能在光域内完成。可 调谐光源的反应时间为毫秒级，还不能满足分组交换的需求。 光网络主要由光节点、光链路、光网络管理单元构成 1 ，7 】，如图1 中 的( a ) 所示。 光节点主要由接入节点和光交换节点两种类型构成，其主要工作 是按其所选择的路由，建立各输入端和输出端之间的全光连接，将 输入端的光信息在所建立的全光通道上无阻塞地达到指定的任意输 出端。光链路是光传输介质，每条链路蕴涵着一定数量的波长。光 3 铸路 路 图1 饴路 网络单元主要是指网络的物理拓扑结构，反映节点和链路构成的不同 方式。主要拓扑结构有线型、星型、树型、环型和网状型，分别示于 图2 的( a ) 、( b ) 、( c ) 、( d ) 、( e ) 。 一缶 ( a ) 树型( b ) 星型( c ) 树型 椤 ( d ) 环型 ( e ) 网状型 图2 现阶段全光传送网的研究与试验主要是以w d m 技术为核心，对波分 复用的传输、交换和联网技术进行研究与试验。在传输方面，将掺饵光 纤放大器( e d f a ) 用了二波分复用传输系统，使大容量长距离全光传输 4 第一章引言 成为可能。在交换技术方面，传统传送网的电路、分组交换也逐渐被空 分、时分的光路交换方式替代。在联网技术方面，基于v c d m 的全光传送 网与现有的s d h 网已实现了很好的互联，i po v e rw d m 技术也在积极地发 展之中f 8 1 。这一切都为我们展现了w d m 全光传送网的美好前景。 未来骨干网络将在网络带宽、可扩展性、生存性和运行成本等方面提 出更高的要求，网络朝着宽带化发展，以保证低成本的高带宽传送；同 时，网络也将朝着数据化( 特别是i p ) 方向发展，使之逐渐成为未来所 有业务的共载体。宽带光网技术结合了波长路由光交换技术和波分复用 光传输技术，在光域实现高速信息流的传输、交换、故障监测和恢复等 功能，建立端到端的光通道，被誉为2 1 世纪真正的高速信息公路。 根据2 l 世纪信息通信业务的发展趋势，可以概要地看出下一代信息通 信网的一些特征： 以数据( i p ) 业务为中心，包括本身就是数据型的业务以及由非数据 业务转换成数据形式的业务； 数据业务呈指数形上升： 网络应能经济有效地适应：由技术业务的多样化造成的业务信号的多 样性，以及对带宽需求的难预测性。 结合基于w d m 的光传送网的特点，下一代信息通信网的网络架构应 由两部分组成： 具超宽传送潜力、对信号透明的核心平台，即以w d m 技术形成光网 络： 能适于多种业务的外层( 边缘) 网络，即能把各种用户的业务信号与 核心平台连接起来的i p 业务层。 根据下一代信息网络的特征和网络架构的特点，下一代信息网络的 垂直结构由业务层、a t m 层、a d m 层和光传送层构成；而下一代信息网 络的水平结构由核心网和边缘网组成。根据“十五”规划，我国未来 的电信网络结构将由d w d m 光传送网构成核心网络，由s d h 网、分组网 和w d m 环网构成省内城域网，由多元化发展的宽带接入、综合业务接 入等向用户延伸。“十五”规划还将探索我国实现3 t 网的可能性，投入 了大量的资金，力求实现技术突破，实现预期目标。对传输链路而言， 一5 一 第一章引言 最有希望突破t b i t s 的传输容量( 可能达到1 6 t b i t s ) 。对传送节点而 言，也有希望突破t b i t s 拘节点容量，电传送节点可望达到1 2 8t b i t s ， 而光传送节点可望达n 25 5 t b i t s 。对业务节点而言，实现难度最大， 将成为网络传输容量的瓶颈；但希望仍在，需要有创新思路和创新技 术。相信不远的将来我国骨干网将逐渐为以w d m 光传送网技术为基础的 基于互联网业务的光网络所取代。 6 第章光网络的弧负载指标 第二章光网络的弧负载指标 2 1 预备知识 光纤网络可用组合图论中对称的有向图g = ( k a ) 表示，其中顶 点集y ( g ) 是网络中节点的集合，弧集a ( g ) 代表所有链路的集合f 1 ，9 1 1 1 。若g 中有一条从u 到”的链路，当且仅当存在一条从”到也的链路， 用( ，v ) i g 从u 到”的链路，具体的转化可见图( 1 ) ，其中图( b ) 为网络( a ) 的图 表示。注意：图论中的名词弧与网络中的术语链路是同一概念。从节 点x 到y 的光通道或路 扫( d i p a t h ) ，记作b 掣) ，是指信息从节点z 到掣之 问的有向传输路径f 1 ，9 ，1 0 。而光网络中信息的传送是通过每条链路上 蕴含的波长来传送。一个光通道就对应一个波长，不同节点闻的光通道 要分配不同的波长，且信息从源点到宿点的过程中，波长一直保持不 变，中间的链路根据波长来区分不同的连接。由于波长通道的固定性和 连续性，当建立新的连接时，只有分配的某一波长在连接通路的所有链 路上都未被占用时，连接才能建立。即使该波长只是在通路上的某一段 链路上被占用，连接仍无法建立，通道就出现阻塞的情况。信息需从节 点传到 ，称为牡， 之间的业务需求( r e q u e s t ) ，记作( u ，w ) 1 ，9 ，1 0 】。业务需 求( ，”) 的建立需要在u ，可之间的物理网卜选择一条光通道，荠为其分配。一 定的波长，用丑记需求的集合。在不引起混淆的情况下r 1 旦可表示路由的 集合。根据业务需求的不同，网络可分为三类f 1 ，1 1 2 1 ： o n e - t o - a l l ：即信源v 的信息需传送到图g 的每个顶点，其需求集为r = ( u ，w ) i 叫v ( c ) b o n e - t o - m a n y ：即信源 的信息需传送到集合的每个顶点，其需求集 为r = ，w ) i 叫w y ( g ) ) ； a l l - t o - a l l ：即图中每个顶点 的信息需传送到图g 的其它顶点，其需求 集为r = f ，u ) iu ，口y ( g ) ，札”，； 考虑到波氏资源的有限性及提高网络的阻塞性能，优化光通道的选路 和波长分配( r w a ：r o u t i n ga n dw a v e l e n g t ha s s i g n m e n t ) 方案成为通道设计t 的核心问题。路由选择和波长允配是独立的两个问题，但如果已经给出 7 笫尊光刚络的弧负载指标 所有需要的光通道的路由选择，那么可以计算出通过每条链路的通道数 量。而最大的通道数量即可作为波长数目的一个下限。因此，有必要引 入以下定义来确定路由的通道数量。 定义2 1 ： f 1 3 _ 1 5 1 顶点”在路由集r 中的负载o o a ) ，记为( g ，r ，”) ， 指r 中通过顶点”，且不以口为端点的路径数目。而最大的点负载称为 网络( g ，r ) 的点负载指标( t h ev e r t e x - f o r w a r d i n gi n d e x ) ，记为f ( g ，r ) 。由此 推知，( g ，r ) = m s xf ( g ，r ，u ) 。由于满足需求集的路由集不唯一，从而 导致网络的点负载指标不唯一，称最小的点负载指标为图g 的点负载指 标，记为( g ) 。由定义可知，f ( g ) = 驰( g ，r ) 。 n 类似地，对g 中的链路也有同样的定义： 定义2 2 ： f 1 ，1 1 1 链路e 在路由集r 中的负载，记为开( g ，r ，e ) ，指r 中 通过链路e 的路径数日。而最大的链路负载称为网络( g ，r ) 的弧负 载指标( t h ea r c - f o r w a r d i n gi n d e x ) ，记为齐( g ，r ) 。由此推知，存( g ，r ) = m d , x 亓( g ，r ，e ) 。称最小的满足需求集的网络的弧负载指标为图c 的弧负 e e a ( g ) 载指标，记为亓( g ) 。由定义可知，亓( g ) = n d n 亓( g ，r ) 。 儿 若将网络中两条方向不同的链路( 乱，u ) 与( ”，u ) 记为一条边删时，即不 考虑链路的方向，又可产生一个新的定义。m c h e y d e m a n n ，j cm e y e r a n dd s o t t e a u ( 1 9 8 9 ) 提出： 定义2 3 ：f 1 3 - l 翻边e 在路由集r 中的负载为r 中通过边e 的路径 数目，记作7 r ( g ，r ，e ) 。而最大的边负载称为网络( g ，r ) 的边负载 指标( t h ef a g e - f o r w a r d i n gi n d e x ) ，记为7 r ( g ，r ) 。由此推知，r ( g ，r ) = m a x7 r ( g ，r ，e ) ( e ( g ) 为图g 的边集) 。称最小的边负载指标为图g 的边负 载指标，记为”( g ) 。由定义可知，7 r ( g ) = m i n7 r ( c ，r ) 。 f i 若路由集的每条路径都是最短路径，则用记路由集。相应地， 分别用e r a ( g ) 、亓。( g ) 、仃。( g ) 记最短路由集条件下，图g 的点负载指标、 弧负载指标、边负载指标。山上述定义易知，( g ) s ( g ) 、亓( g ) i ( g ) 、7 r ( g ) 7 r 。( g ) 、亓( g ) 7 r ( g ) 2 亓( g ) 。 有关点负载指标及边负载指标已有的结论，可具体见文献f 1 3 ，1 6 1 9 1 。 8 第_ 章光刚络的弧负载指标 2 2 弧负载指标的界 以下考虑的光网络均为a u - t o a u 网络。 定理2 1 ：g 是一非空简单连通图，阶数为n ，、6 分别表示g 的顶点 的最大度、最小度，则 ! ，! 二! 攀亓( g ) ( g ) + ( 礼一6 ) ， 且上式对最短路由集也成立。 证明： ( 1 ) 任给顶点”y ( g ) ，考虑形式为e = ( ”，u ) ( 其中u 为u 的邻 点1 的弧。显然，每条通过顶点”的路径必对此类型弧产生一个负载， 共有( g ，r ，u ) 个负载。另外每条以”为起点的路径也对它产生负载，共 有协一1 ) 条路径。由此推知，对于任一路由集冗， ( g ，r ，u ) + 一1 ) = ：膏( g ，r ，e ) 兰x g ( g ，r ) e = ( ，u ) 不妨设路由集凰满足亓( g ，凰) = 亓( g ) ，则对g 的任一顶点”，都有 f ( g ，j 动，u ) + n 一1 膏( g ) ， 所以 ( g ) + ( n 一1 ) 曼亓( g ) ( 2 ) 现置e = ( “，u ) ，则路由集r 中e 的负载开( g ，r ，e ) 必不超过( g ，r ， ) 与通 过e 且以钉为终点的路径数目之和。由于”的邻点( 除了点秕外) 到”的路径必 不通过e ，故后者的数日至多有礼一d ( ”) ，从而有 亓( g ，r ，e ) f ( g ，r ，口) + 礼一d ( 廿) ， 故有 亓( g ，r ，e ) 茎( g ，冗) + 佗一6 同样地，不妨设路由集r o 满足 ( g ，r o ) = ( g ) ，则有 亓( g ，凰，e ) ( g ) + ( n d ) ， 进一步地 齐( g ) ( g ) + ( 托5 ) 由于上述证明过程与路径是否是最短路由集无关，故定理对最短路由集 也成立。 q 第_ 瞥光网络的弧负载指标 定理2 2 ：f 1 3 g 奠j - - n 阶简单连通图，则 ：( d ) 一1 ) 岛( g ) 茎( 礼一1 ) ( 他一2 ) ， ( 21 ) 一“协壬“ 且( 2 1 1 式中前两个等式成立当且仅当g 中存在一个最短路由集r ，且r 对 任一顶点的负载均相同，其d p d ( u ，t ，) 是顶点u 与”之间的距离。 定理2 3 ：g = ( va ) 是一礼阶简单连通图，则 南莓至d ( 刚) 武g ) 引g ) 俐1 ， ( 2 。2 ) 且f 2 2 1 式中前两个等式成立当且仅当存在个最短路由集r ，且r 对每条 弧的负载均相同。 证明：先证蒜( g ) 【扣2 j 。 任取g 的两个顶点“，且e = ( 口) a ( g ) ，定义y ( g ) 的一个分类如 下： a = z v ( c ) ：d ( z ，) d ( ，盯) j ； b = z y ( v ) ：d ( x ，口) d ( z ，钍) ) ； c = 。v ( g ) ：d ( x ，t ) = d ( z ，可) 显然札a 瓯t ，b o 且a 、b 、g 为y ( g ) 的个分划。进一步地，最 短路由集扛一可) 通过e 必须满足z a 且b 。故推出 邗e ) i a 忙i ( 垃笋) 2 i n 2 ， 因而有亓m ( g ) i i 礼2 i 。 由于任一路径冗( u 一”) 产生的弧负荷必大于或等于d ( u ，。) ，则路由 集r 所产生的总负荷必满足下式 武g ，冗，e ) d ( u ，口) 。 ( 2 3 ) e a ( g ) “ 由弧指标的定义可推出 亓( g ，r ) 南d ( 让，廿) ， ( 2 4 ) 故有 积g ) 南莓薹d ( ”) ( 2 5 ) 1 0 第二：章光网络的弧负载指标 式子( 2 3 ) 等号成立当且仅当r 是最短路由集。而式子( 2 4 ) 等号成立当且仅 当r 对每弧的负荷相同。由此推知：( 2 2 ) 式中的前两个等式成立当且仅 当r 是最短路由集，且_ r 对每弧的负荷相同。故命题得证。 u 定理2 4 ：g 是一n 阶2 _ 连通图，则亓( g ) s 亓m ( g ) s 【；n 2 一；+ j 。 证明：任给链路e = ( v ) a ( g ) ，定义y ( g ) 的个分类如下： a = z v ( c ) ：d ( z ，“) d ( z ， ) ) ； b = z ev ( g ) ：d ( z ， ) 1 + d ( o ，u ) + d ( u ，“) = 1 + d ，功+ d ( ，u ) 。而1 + d ( n ， ) + d ( 口，u ) y 日p , a n v 的经过链路e 的路径的 长度，由于路径是最短的，故路径j k ( n ”) 必不通过链路e 。类似地， 也可推出，任给b b ，路径。( u 6 ) 必不通过链路e 。所以r ( a ，b ) 中 至少有o + p 条路径不通过链路e 。这也暗示 亓m ( g ，e ) n p a 一卢i 竹2 一礼 i 礼2 一；+ i 故命题成立。 口 第一带光剐络的弧负载指标 定理2 5 ： ( i ) g 是一礼阶简单连通图，且直径为2 ，则亓( g ) s 元。( g ) s 几一l 。 ( i i ) g t 黾n 阶直径：哭j 2 1 4 j 2 一连通简单图，则亓( g ) 曼亓。( g ) n 一2 。 证明： 不妨设弧e = ( “，”) a ( g ) 和最短路由集满足( g ) = 亓( g ，蜀。，e ) 。同样地，定义y ( g ) 的一个分类如下： a = z v ( a ) ：d ( x ，牡) d ( 。，口) ) ； b = z v ( a ) ：d ( z ，v ) n 一2 ，由( i ) 知元。( g ) s 礼一1 ，故* ( g ) = e ( a ，e ) = 礼一1 。又因为亓( g ，e ) f a f + f b f 一1 礼一1 ，由此推 知：i a i + i b i = n 或c = g ，即任顶点叫( 除了u ，v n 点外) ，岛。( u w ) 或( w u ) 有且仅有一条路径通过e 。因为g 是2 一连通的，则必存 在x a 一 u ) ，y b 一扣) 且( 。，y ) a ( g ) 。定义： q 1 = ( 珏7 f “7 z ，路径。恤一“7 ) 通过链路( “，z ) ； 1 2 第：章光刚络的弧负载指标 q 2 = iz 7 u ，路径r 。( 一一z ) 通过链路( u ，z ) ) ； q 3 = 可，| 矿 ，路径r 。国一矿) 通过链路( y ，u ) ) ； q 4 = ”7 it ，y ，路径。( u 7 一”) 通过链路( y ，”) ) 可以证明 ( q lu q 2 ) n ( q 3 u q 4 ) = a 其实只需要证明q 1nq 3 = o 和q lnq 4 = 巧。若q 1nq 4 o ，即存 在w q 1n 酝，则d ( 珏，w ) = d ( 口，w ) = 2 与c = g 矛盾。故q lnq 4 = o 。 若q 1n q 3 g ，同样存在w q 1n q 3 ，则( 叫， ) a ( g ) 。又因为兄。( 一 叫) 不通过( u ，。) 与任一顶点 ，f k ( u 叫) 或r m ( 训”) 有且仅有一条路 径通过e 矛盾，故假设不成立，所以有( q luq 2 ) n ( q 3uq 4 ) = g 。 假设礼l = l q l u q 2 1 ，n 2 = l q 3 u q 4 。由性质可知：e ( c ，u ，z ) ) 凡l + 1 ，亓( g ，r 。，( y ，口) ) n 2 + 1 。又因为( q 1 u q 2 ) n ( q a u q 4 ) = a ，则有n l + n 2 n 。故可推出 亓( g ，j 宅m ，( 钍，z ) ) + 膏( g ，冗m ，( 兰，咎 ) 扎l + 1 2 2 + 2 n + 2 由此可知：亓( g ，( “，z ) ) n 一3 或亓( g ，( y ，”) ) n 一3 ，不妨 设亓( g ，( u ，z ) ) sn 一3 。另外，容易得知：亓( g ，r m ，( z ，9 ) ) 礼一3 。 构造一个新的最短路由集：路径碳( u 一们为姓一z y ，其 余路径不变。易知：亓( g ，碳，( u ， ) ) n 2 ，亓( g ，碳，( u ，z ) ) n 一2 。 则元。( g ，瓦) n 2 与假设矛盾。故命题成立。 n 2 3 折叠立方体的弧负载指标 所谓折叠伽方体( t h ef o l d e dn - h y p e r c u b e ) 是指这样的图，它的顶点 是0 和1 组成的有序札元数组，两个顶点相邻当且仅当它们恰有一个坐 标不同或所有的坐标都不同，用f h ( n ) 表示f 2 0 1 0 现置任一顶点x = z 1 z 。，并用x ( i ) 或z l 瓦z 。记与x 的第i 位坐标不同，其余坐 标不变的顶点。更一般地，用x ( i l ，i 2 ，i k ) 记与x 的第i l ，i 2 ，旗坐标 不同，其余相同的顶点。特殊地，用叉记与x 的所有坐标都不同的顶点。 定理2 6 ：若n 4 ，则亓( f 日( n ) ) = 2 ”1 i ( f ； ) i 。 1 3 第一二章光州络的弧负载指标 证明：任选两个不同的顶点x = x l x 2 z 。，y = 可l y 2 y n 且定义 x ，y = i 吼一玑i i = 1 不妨假设y = x ( l ，i 2 ，- i 女) ，矿= x ( j l , j 2 ，a ) ，易知 j 1 ，力，一，血) = 1 ，2 ，礼) 0 1 ，i 2 ，如) ，其中2 1 i 2 如j 1 j 2 詈，共有p i l ) 路径。 8 j + l 则弧e 的负载 雄，= 霎( 佗n i 萎，( 几j1 ) = 2 n - i _ ( 札i1 ) = 2 n - 1 _ 狲 情形击弧的形式为e = ( a ，才) ，其中a = 口1 n ，。路径r 一y ) 通 过e 当且仅当且x = x l z 2 。，y = a l a 2 一a n 且 x y g ，则弧e 的负载 徘卜i 熹。( 笏2 褂1 n i ) 一韵2 n - 1 _ 撼 利用定理2 3 ，可容易得知：当几为偶数，亓( f 日( 礼) ) = 2 ”1 一i5 ( ；) i 。 第章光蚓络的弧负载指标 现考虑他为奇数的情形。 规定：当 x ，y 茎学( o rh x ，y 字) ，路径n ( x y ) 与h x ，y 曼暑( o r x ，y 墨) 且n 为偶数的路径方案相同。现只剩t h x y = 学的情形。 令s 为集合 l ，2 ，竹 的所有警一元子集，显然r s f 一( 墨) 。任选一个元 素口= n ，i 2 ，i 华) s 和整数t 1 ，2 ，n ) ，用+ t 记0 l + t 一1 ，i 2 + t 一1 ， 咝+ t 一1 ，这里加法取模礼加法。定义s 的一个等价关系c 一： a 一当且仪当存在一个整数t l ，2 ，n l ，使得n ，= 口+ t 。 这个等价关系导致s 的一个分划，不妨设s = s lu 函u u ，其 中每个& 都是一个类，由等价关系可知每个& 都有礼个元素，则m = ：( 牟) 。不妨设子集 1 ，2 ，警) s m ，并设o t = 1 ，2 ，警 + i ，i = 1 ，2 i 一，n 。令： 若m = 2 k 掣t 2 r ；- - i ，羹篙0 若一 lu 。，若m = 2 七； s 2 2 蚕如u ：i l l 若若n n ：= 4 4 危h 一+ 。l ，若m ：。足+ ，； 任取顶点x 和y = x ( i 1 ，i 2 ，i 班) ，由这两个顶点可唯一确定一个圈 c ( x ，y ) ：x x ( i l ) 一x ( i l ，i 2 ，掣) ( = y ) 一y y ( j 掣) 一。一y ( j l ，j 掣) = x 若 i l ，i 2 ，i 掣 s 1 ，则定义路径n ( x y ) 为： x x ( i l ) 一一x ( i l ，i 2 ，一，i 华) ( = y ) ； 若 i 1 ，i 2 ，i 华) s 2 ，则定义路径r ( x y ) 为： x = y ( j l ，血，j 犁) 一一y 0 掣) 一y y ( 2 6 ) ( 2 6 ) 也可写成 x x 0 1 ) 一一x 1 ，出，j a 丢) ( = y ) 一y 通过e 述的路径方案，可算出距离为盟警的所有点对对每弧的负载。同样 地，按弧的形式可分为两种情形： 1 5 q 吾哟 ，ll-c1【 u 一 一 岛 。u!亘。u：亘 ，-l_lij(1_lll | | s 第：章光嘲络的弧负载指标 若e = ( a ，才) ， 且仅当f t l ，i 2 其中a = a l a 2 o 。，则路径义一x ( i l ，i 2 ，i 半) 通过e 当 若e = ( a ，a ( j ) ) ， 当 i 学 s 2 且j = x ( i l 川i 2 i ) o s 1 ，x b l b j l a j a j + l i i ) d s 2 ，x b l 6 j l a j a j + l 换句话说，在i ) d o ，a = n i l ，i 2 类似地，在i i ) 中，n = i 1 ，i 2 ， ，i 咝) 。可知 若m = 2 k ； ) j ，若n = 4 + 1 】1 ，若n = 4 h 一1 a 。，n x - - - - - 4x ( n ) 通过( a ，a ( ) ) 当且仅 a n ，x ( ) a l- a 1 一l 巧6 j + 1 - k ； n