互连网络拓扑结构是计算机系统或通信系统中元件之间的连接方式，它是决定该系统性能的重要因素之一.一个互连网络的拓扑结构可以被模拟成一个无向图G=（V,E）.这时，图G中的顶点代表网络中的元件，G中的边表示元件之间的通信连线.网络的拓扑结构决定着该网络的性能.一个图的连通度和边连通度是衡量该互连网络可靠性和容错性的重要参数.而且图的连通度和边连通度越大，它所模拟的互连网络的可靠性越高.但是，这两个参数有明显的缺陷.因为它们假设与同一个顶点相邻的所有顶点或所有边可能同时故障.然而，这在网络的实际应用中几乎是不可能的.为了正确地度量网络的容错性，除了连通度和边连通度，更多新的参数被提出，例如：额外连通度和额外边连通度.对于一个非负整数g，图G的g-额外连通度κ_g（G）（g-额外边连通度λ_g（G））是最小点数（边数），这个数目的点集（边集）从G中移走会导致剩下的图不连通且每个连通分支至少有g+1个顶点.可嵌入性是度量网络优劣的一个重要性能，一个网络是否具有泛圈性可以度量该网络是否可以嵌入任意长度的圈.泛连通性是泛圈性的深化.如果一个网络是泛连通的，则一定是泛圈的.本文主要研究几个著名网络的容错性和泛连通性，全文共分四章.第一章介绍了本文用到的一些图与网络的基本概念，度量互连网络的可靠性和容错性的几个参数，泛连通性的定义以及几个著名的网络的定义.第二章研究kⁿ-hypermesh网络和n-维spined cube网络的额外连通度和额外边连通度.首先证明了kⁿ-hypermesh网络的1-额外连通度和2-额外连通度分别为κ1(HM_n,k)=2n（k-1）-k （n≥3, k≥3）和κ₂(HM_n,k)=3n（k-1）-2k-1（n≥4, k≥4）.然后证明了SQn的1-额外连通度和1-额外边连通度均为2n-2（n≥3）.第三章通过引入图的t-最小簇度（记为δ_t（G））这个概念.确定了超立方体Q_n的t-最小簇度.即：当1≤t≤n+1时，δ_t（Q_n）=tn-2（t-1）-1/2（t-1）（t-2）.然后又讨论了故障立方体的结构，并证明了，在一个n-维立方体Qn中，当0≤t≤n-3时，对于一个故障集F且|F|<δ_t+1（Q_n），Q_n-F有一个大连通分支且剩下所有小连通分支总共至多有t个顶点.第四章研究了kⁿ-hypermesh网络HM_n,k的泛连通性.证明了HM_n,k是泛连通的.即对任意两个不同顶点x,y∈V （HMn,k），它们之间存在从d（x, y）到l≤kⁿ-1的每个长度的（x, y）-路，其中d（x, y）是x和y之间的距离.根据这个结论以及边泛圈和点泛圈的定义得，HM_n,k既是边泛圈的又是点泛圈的.利用这个结论得到3-元n-立方体是泛连通的，边泛圈和点泛圈的，这个是S.-Y. Hsien等在一篇文章中证明的主要结论.