随着信息化社会的飞速发展,高性能计算已成为继理论科学和实验科学之后科学研究的第三大支柱。从战略高度上讲,高性能计算技术是一个国家综合国力的表现,并在社会生活的各个方面都占有不可或缺的重要地位。高性能计算机的性能在很大程度上取决于其系统内部处理器之间的连接方式(互连网络)。互连网络可以表示为一个简单图G=(V(G),E(G)),其中V(G)是G中的非空顶点集合,表示互连网络中的处理器集合,E(G)则是G中的边集合,表示各个处理器之间的链路集合。互连网络的不相交路径覆盖问题不仅对于代码优化和软件测试有着十分显著的作用,而且已经广泛地应用到了数据库设计,无线传感器网络的拓扑控制和超大规模集成电路的设计等领域。在互连网络中,不相交路径覆盖不仅可以提高广播通讯的效率,而且还在提高数据收集和分发效率方面起着重要的作用。例如在网格网络中利用不相交路径覆盖进行广播通讯,我们不仅可以加快通讯的速度而且仅需要对每台处理器访问一次。随着互连网络的不断扩大,网络中的处理器数量也越来越多。当一个大型多处理器并行计算机系统投入使用之后,发生故障是不可避免的。因此,近年来互连网络的容错性研究已经成为了一个重要的研究课题。哈密顿性质在信息通讯中具有重要作用,例如哈密顿路可用于一类通讯系统中,用来减少拥塞和死锁。此外,哈密顿性质还可应用在互连网络的故障诊断中,通过减少故障诊断的次数来提高故障诊断的效率。然而由于各种网络的结构不同,并非任意的一个网络都存在哈密顿路径。因此,我们退而求其次,转而寻找网络中的最长路径。网格网络是较早研究的拓扑结构之一,并且现在仍然是最为重要的和最有吸引力的网络模型之一。且有结构简单、规则及良好的可扩展性与易于设计超大规模集成电路的特性。环绕网络是一种完全对称直连网络拓扑,具有很多优秀的网络特性,如规则对称性,路径多样性以及良好的扩展性,因此广泛应用于许多商用系统中。本文在传统生成连通度和生成交织度的基础上,提出了增强生成连通度和增强生成交织度的概念,求出了二维网格网络的增强生成交织度。同时讨论二维环绕网络中任意两个不同部的顶点间4~*-容器中最长路径长度上限。受到结构连通度和子结构连通度的启发,本文讨论了环绕网络中顶点出现大面积故障或者某个顶点及其邻居顶点发生故障的情况下,任意两个无故障顶点之间的最长无故障路径性质,以及当网格网络中顶点出现大面积故障时的任意两个无故障顶点之间的最长无故障路径性质。并且基于大面积顶点发生故障和某个顶点及其邻居顶点发生故障两种情形给出了环绕网络中的容错最长无故障路径路由算法。结果表明,在耗时以及路径长度上都有很好的表现。