具有故障边的二维环面网络的哈密尔顿路

作者：张建秀; 李晶; 田小润

来源：太原科技大学学报, 2021, 42(06): 491-495.

• 互连网络
• 二维环面
• 容错问题
• 哈密尔顿路

二维环面是一类重要的互连网络,被广泛应用到当前大型分布式系统的网络拓扑中。研究具有故障边的二维环面网络Torus(m,n)上的哈密尔顿路问题,并证明了以下结论:(1)设F是二部图环网Torus(m,n)(m,n≥4是偶数)的故障边集,u和v是不同部中的两个顶点。若|F|≤4,u为Torus(m,n)-F中的唯一1度顶点且(u,v)?E(Torus(m,n)-F),则Torus(m,n)-F中存在哈密尔顿路连接u和v.(2)设F是环网Torus(m,n)(m,n≥6是偶数)的故障边集。若|F|≤5,u为Torus(m,n)-F中的唯一1度顶点,则点u至少有两个邻点与u之间有哈密尔顿路,并且这些邻点与u以故障边在Torus(m,n)中连接。

• 单位
  太原科技大学