中文摘要：

互连网络及其路由选择的容错性是当今互连网络研究中的一个重要问题和热点问题。由于网络中的路由选择是预先设计的，当网络的某些结点和（或）连线发生故障时，用预先设计的路由选择来传输数据势必导致传输延迟问题。为了度量路由选择的优劣，研究者提出幸存路由图的概念，其直径恰好反映了数据传输延迟时间的长短。当路由选择限定为图的边集时，幸存路由图的直径就是大家熟知的容错直径。本项目主要针对于当今互连网络设计三种重要方法- - 笛卡儿乘积图、线图、Cayley图以及目前超级计算机普遍采用的超立方体网络的潜在替代者- - 超立方体网络的某些变形网络（如交叉超立方体、折叠超立方体等），研究幸存路由图的直径（包括容错直径）的上界或精确值，考虑基于限制连通度的互连网络及路由选择的容错性，并探讨一般的容错网络的路由选择算法。研究成果将为设计高性能超级并行系统、分析和评估系统性能提供理论依据，具有理论前瞻性和应用价值。

结论摘要：

本项目研究互连网络及其路由选择的容错性的问题。得到某些给定条件的笛卡儿乘积图关于最短路由选择的幸存路径图的直径的上界；得到三类图的边容错直径的上界；得到k元n维立方体的某些容错泛圈性；得到n维煎饼图的某些限制边容错性。此外，刻画了某些图类中具有最小Hosoya指数的图；给出某些图类中零阶广义Randic指数紧的界；得到煎饼图的（条件）匹配排除数；还得到谱矩方面的一些结果。部分研究成果将为设计高性能超级并行系统、分析和评估系统性能提供理论依据，具有理论前瞻性和应用价值；部分研究成果丰富了图论领域的理论。本项目共完成学术论文10余篇，其中发表8篇（SCI收录6篇，EI收录1篇，另有1篇被SCI来源刊物接受）。依托项目，培养硕士生25人（其中14人已获得硕士学位，11人在读）。