互连网络中构造点不相交路径（即并行路）是并行与分布式系统设计与实现的基本问题之一。根据Menger的定理，连通度为k的网络中任两不同节点之间存在至少有k条并行路。对于一般的网络，找出其中两节点间最大数目的并行路一般使用时间复杂度为O（N3）的最大流方法，其中Ⅳ是网络的规模。如果进一步要求所构造的并行路的最大长度或平均长度达到最小，则问题是NP-hard的。评价并行路构造算法的性能指标通常包括时间复杂度和所得并行路的长度。　　 OTIS（Optical Transpose Interconnection Systems）网络--也称作Swapped网络，是一类两层结构的网络，可使用任意图作为因子网络来构建复合网络。因子网络之间的简单交换互连规则使得OTIS网络具有规则性、模块化、容错性、算法高效等优点，因而近年来受到广泛关注，是少数被实现的互连网络体系结构之一。为了弥补OTIS网络结构的不对称性，肖文俊教授最近提出了一类新的两层复合网络即Biswapped网络（简称为BSN）。BSN中因子网络之间的互连规则与OTIS网络中的类似，但要更为一致，这使得在许多方面BSN的性能更好。针对OTIS网络和BSN这些一般复合网络方案的性能分析结论和设计的算法适用于这类网络中的每个具体网络。　　 目前，OTIS网络的研究集中于OTIS网络如何继承其因子网络的特性（如Hamilton圈性等）以及如何利用因子网络中的算法来设计OTIS网络中的相应算法。Sahni和Parhami等人在这方面做了许多研究。Day和Al-Ayyoub的最新研究表明，极大容错的因子网络构建的OTIS网络也是极大容错的，并根据因子网络中并行路的构造得到相应OTIS网络中的并行路的构造。　　 本文旨在获得OTIS网络的容错性和并行路构造算法的普遍性结果，即得到与因子网络无关的一般容错性质和有效构造并行路的一般方法。基本研究思路就是利用OTIS网络的互连规则，直接构造OTIS网络中任两不同节点之间的最大数目的并行路，由此得出任意OTIS网络的连通度（容错性）和构造并行路的有效算法，最后将这些研究推广到BSN上。论文主要研究工作如下：　　 1、提出构造两点间最大数目并行路的一般方法，由此证明连通OTIS网络一定是极大容错的，而与因子网络的容错性无关。所得结论及算法具有理论意义。其一，极大容错性的证明及相应的并行路构造方法具有一般性，适用于由任意的连通因子网络构建的OTIS网络，这改进并推广了前人的相关结论及算法。其二，确定了任意OTIS网络的连通度。其三，首次表明OTIS网络享有某种与因子网络无关的新的理想特性（如极大容错性），这与以往文献中集中于研究OTIS网络如何继承因子网络的理想特性是完全不同的。此外，为了进一步探讨OTIS网络的容错性，本文中还引入比极大容错性更强的一致极大容错性的概念，并获得了OTIS网络是一致极大容错的充要条件。　　 2、分别设计了在任意的连通OTIS网络中构造点到点（Node-to-Node）并行路和点到点集（Node-to-Set）并行路的一般算法。对算法时间复杂度和所构造的并行路长度进行理论分析，表明这些算法是有效的，具有实用价值。　　 3、证明BSN继承因子网络的点传递性，这推广了BSN继承因子网络的Cayley图特性的结论；证明任意的连通BSN具有一致极大容错性，设计了点到点（Node-to-Node）并行路的一般算法。　　 4、以图同态和同构为工具，研究了BSN、OTIS网络、笛卡尔积网络结构间的关系。