【作者】 陈美润；

【导师】 钱建国；

【作者基本信息】 厦门大学 ， 应用数学， 2006， 硕士

【摘要】 全光纤网络可定义为弧对称的有向图G(即α是G的一条弧当且仅当它的反向α^-1也是G的一条弧)。设R_f（G）是G的一个f-容错路由集（f-fault tolerant routing）。R_f（G）中通过弧α的有向路的数目定义为弧α的负载，G中的最大弧负载定义为在R_f（G）下G的负载，记为π（R_f（G））。G的f-容错弧负载是指在所有路由集R_f（G）下G的负载的最小值，记为π_f（G），即π_f（G）=（?）π（R_f（G））。称一个路由集R_f（G）为最优的（optimal）如果它满足等式π（R_f（G））=π_f（G）。称路由集R_f（G）为均匀的（balanced）如果在R_f（G）下G中任意两条弧的负载之差至多为1。称一个最优均匀的路由集R_f（G）为平衡的（leveled）如果它的每个子路由集都是最优均匀的。 本文讨论一些特殊图类的容错路由问题及其π_f指标。首先考虑每个部都含有m个点的完全n部图K_{n，m}的容错路由集，其中n=p^r，p为素数。当m=2时，K_{n，m}便为我们熟知的鸡尾酒图CP（n），此时给出了CP（n）的一组（2n-3）-容错平衡的路由集并由此确定其相应的π_f（CP（n））指标。当n=3时，K_{n，m}为完全三部图且每个部都含有m个点，我们也给出了K_{3，m}的一组（2m-1）-容错平衡的路由集及相应的π_f(K_{3，m}指标。其次构造了Q_n和FH（n）的容错平衡路由集，其相应的f-容错弧负载指标也得到了确定。最后，沿用Arvind Gupta等所采用的设计理论方法，构造了K_n×K_n的一组（2n-3）-容错平衡的路由集并由此给出指标π_f（K_n×K_n）的值。更多还原

【Abstract】 An all-optical network can be modelled as a symmetric directed graph G, i.e., if an arc （u,v）∈A（G） then （v,u）∈ A（G）. We use R_f（G） to denote an f-fault tolerant routing of G and π（R_f（G）） to denote the maximum load on its arcs induced by the routing R_f（G）.The f-tolerant arc-forwarding index π_f（G） of G is defined to be .We say that a routing R_f（G） is optimal if its load achieves the f-tolerant arc-forwarding index π_f（G）; and it is balanced if the difference between loads of any two arcs is at most one. We say that an optimal balanced routing R_f（G） is leveled if each of its subroutings is also optimal and balanced.In this paper, we first construct an f-fault tolerant routings for K_{n,m}, where K_{n,m} is the complete n-partite graph with each partition part containing exactly m vertices and where, n is a prime power. In particular, if m = 2 or n = 3, these routings are shown to be leveled and, consequently, the corresponding π_f indexes for these graphs are determined. We also construct the leveled f-fault tolerant routings for hypercube Q_n, folded hypercube FH（n） and product graph K_n ×K_n, respectively. Furthermore, the corresponding π_f indexes of these graphs are given.更多还原