论文部分内容阅读
泛连通性和不交路覆盖是互连网络中的两个重要问题.泛连通性意味着有各种长度的路的嵌入,可以有效模拟在线性阵列上设计的许多种算法.不交路覆盖意味着所有的结点都可以参与并行路的数据路由。
折叠超方体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是泛连通的。