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

张建秀，李 晶，田小润

(太原科技大学 应用科学学院，太原030024)

随着当前信息量的日益增加，在太空、国防、科技等各个领域已经出现了大量具有挑战性的应用问题，因此大规模并行计算机系统应用而生，为大规模并行计算机系统设计更高效更可靠的互连网络成为网络设计者们不断追求的目标。环面网络作为大规模并行计算机的互连网络，近年来受到广泛关注[1]。

哈密尔顿圈和路的存在问题是互连网络研究中的经典问题。关于二维环面网络(即Torus网络)的哈密尔顿性质，学者们已经得到很多相关成果：设F是Torus网络中的故障集合，Kim和Park在2000年证明了当F是故障点集且|F|≤1时，Torus(m,n)，其中m,n≥4是偶数，是偶哈密尔顿连通的[2]。2003年，Park和Kim推广了这一结论，证明了当F是故障点集或边集且|F|≤1时，Torus(m,n)，其中m,n≥4是偶数，是偶哈密尔顿蕾丝的[3]。 Xiang等人[4]证明了当F是故障边集且|F|≤3时，如果Torus(m,n)-F中没有1度点，Torus(m,n)(m,n≥3)是哈密尔顿的。2017年，Li等人将故障边集的数目再次提高，得到结论：当F是故障边集且|F|≤4时，如果Torus(m,n)-F中没有1度点也没有f4圈，则Torus(m,n)(m,n≥5)仍然是哈密尔顿的[5-6]。然而，在上面的研究中，随着故障边数的增加，学者们都假设Torus(m,n)-F中没有1度点，对存在1度点的情形，没有文献讨论此时网络中哈密尔顿圈和路的存在问题。本文将对这一情形进行详细地讨论。

1 预备知识

一个二维m×n环面(简记为Torus(m,n)，其中m,n均为偶数)的顶点集为V={vij|1≤i≤m,1≤j≤n}，边集为E={Er∪Ec}，其Er={(vij,vi,j+1)|1≤i≤m,1≤j

图1 Torus(4,6)Fig.1 Torus(4,6)

图2 Row-Torus(4,6)和Gird-Torus(4,6)Fig.2 Row-Torus(4,6)and Gird-Torus(4,6)

令G=Torus(m,n)，定义R(i)与C(j)分别为第i行、第j列的点导出的G的子图，即R(i)=G〈{vij|1≤j≤n}〉、C(j)=G〈{vij|1≤i≤m}〉.令R(i:i′)=G〈{vkj|i≤k≤i',1≤j≤n}〉，否则R(i,i′)=∅.同样地，令C(j:j′)=G〈{vik|1≤i≤m,j≤k≤j′}〉，否则C(j,j')=∅.包含Torus(m,n)的每个顶点的路称为Torus(m,n)的Hamilton路；类似地，Torus(m,n)的Hamilton圈是指包含Torus(m,n)的每一个顶点的圈。……