论文部分内容阅读
图的嵌入问题是衡量一个互连网络的中心问题之一，它的重要性在于我们可以将关于客图的已有算法应用到主图中．环和线性阵列由于通信成本低廉，因而是并行处理和分布计算中的两个基本网络结构．一个网络若含有哈密尔顿圈或哈密尔顿路，就能够有效模拟许多为环和线性阵列设计的算法，因此有效的圈或路嵌入是设计网络拓扑结构的基本要求．大型系统在使用过程中它的某些连线或结点难免发生故障，因此在并行计算中，一个互连网络的容错能力是一个关键性的因素．研究存在故障的系统具有重要的实际意义．
超立方体和蜂窝矩形环托是两种常见的互联网络拓扑结构．N维超立方体(记为Qn)是含有2n个顶点的n正则二部图，蜂窝矩形环托(honeycomb rectangulartorus，记为HReT(m，n))是由环托(torus，一种网络拓扑结构，即两个圈的笛卡尔乘积)适当删除一些边后得到的3正则图．它们都具有许多优良的拓扑性质，已被应用于并行处理和分布计算系统中．
本文研究了以下两个问题：
(1)在有故障边的超立方体中通过给定线性森林(即每个分支是路的子图)的无故障圈的嵌入问题；
(2)在有故障边的蜂窝矩形环托HReT(m，n)中的无故障哈密尔顿圈嵌入和蜂窝矩形环托HReT(m，n)中哈密尔顿可迹性(Hamiltonian-laceability)问题，并得到了以下结果：
1、在超立方体中通过给定3条边的圈嵌入；
2、在有故障边的超立方体中通过给定线性森林的无故障圈嵌入；
3、在有故障边的蜂窝矩形环托HReT(m，n)中的无故障哈密尔顿圈嵌入；
4、蜂窝矩形环托HReT(m，n)的强哈密尔顿可迹性．