论文部分内容阅读
光纤网络是当今及未来信息网络的核心技术之一,主要适用于可视电话、远程教育、远程医疗、家庭办公等新型业务。光纤网络可用一个弧对称(即图中有一条从u到v的弧当且仅当存在一条从v到u的弧)的有向连通图表示,其路由集是满足所有业务需求集的有向传输路径的集合。给定一个路由集R,其点(或弧)负载指标(Forwarding Index)定义为R中通过每个顶点(或弧)的路径数目的最大值。进一步地,图G的点(或弧)负载指标为满足业务需求集的所有可能路由集的点(或弧)负载指标的最小值,记为ξ(G)(或π(G))。光网络中的路由问题(The Routing Problem)是指构造一个路由集,使得此路由集的弧负载指标达到最少。给定网络的一个业务需求集,我们需要在各需求集之间建立一个光通道,并为其分配一定的波长,使得通过同一条弧上的任何两个光通道分配不同的波长,记χ(R)为所需的最小的波长数目。令χ(G) = min {χ(R)},则波长分配问题(The Wavelength Assignment Problem)就是要构造一个路由集和波长分配方案,使其所用的波长数达到χ(G)。考虑到波长资源的有限性,因此优化光通道的路由和波长分配方案成为网络设计的核心问题。已证实确定χ(R)是一个NP―完全问题,但对一些特殊图如树、圈,其波长数目是可确定。本文主要考虑弧负载指标。首先给出一般图在点负载指标、最大度、最小度等条件下,弧负载指标的上、下界。接着给出2-连通图的弧负载指标的一个上界。进一步地,还研究了直径为2的2-连通图弧负载指标,证明π(G)≤n－2(其中n为顶点数)。文章还构造出折叠立方体的路由方案,由此计算出折叠立方体的弧负载指标。利用该路由方案,确定了当n为偶数时,折叠立方体的波长数。