论文部分内容阅读
泛连通性和不交路覆盖是互连网络中的两个重要问题.泛连通性意味着有各种长度的路的嵌入，可以有效模拟在线性阵列上设计的许多种算法.不交路覆盖意味着所有的结点都可以参与并行路的数据路由。
折叠超方体FQn、k元n方体Qkn和完全多部图Kn，n，…，n是三类重要的网络拓扑结构，它们在并行处理和分布计算中具有广泛的应用.本文研究含有故障边的折叠超方体FQn、k元n方体Qkn中的不交路覆盖和完全多部图Kn，n，…，n的泛连通性。
在这篇论文中，得到的主要结果如下：
1.设n(≥3)是奇数，1≤k≤n，Fe()E(FQn)并且|Fe|≤n-k.假设S(T)是FQn的一个包含k个黑点的集(白点的集)，则FQn-Fe有一个多对多k不交(S，T)-路覆盖，并且|Fe|的上界n-k是最优的。
2.当n≥2时，设x1、y1、x2、y2是Q6n中任意四个顶点，这里x1和x2是黑点，y1和y2是白点，则在Q6n中存在两条顶点不交的路P1和P2覆盖Q6n，这里P1是x1～y1路，P2是x2～y2路。
3.当n≥2时，在完全二部图Kn，n中，若故障边数|Fe|≤n-2，则Kn，n-Fe是偶泛连通的，并且|Fe|的上界n-2是最优的。
4.完全k(k≥3)部图Kn，n，…，n是泛连通的。