随着计算机科学技术的高速发展,对计算机的计算和存储能力提出了更高的要求,并行计算机系统应运而生.并行计算机系统的并行度和高性能,很大程度上依赖其互连网络,因此容错性高的互连网络对开发更好的并行计算机系统尤为重要.互连网络的容错性取决于其拓扑结构,而互连网络的拓扑结构通常被模型化为图,图的顶点代表处理机,图的边代表处理机之间的连接关系.在此意义之下,互连网络的容错性问题可转化为图的结构性质研究.图的连通度是经典的图结构参数,也是衡量互连网络容错性的经典参数.但在实际应用中,一个处理机的所有邻点同时发生故障的可能性很小,而且当网络不连通时,经典连通度不能反映剩余网络的结构性质,因此,经典连通度在某种程度上往往会低估网络的容错性水平.为此,学者们推广了经典连通度概念,提出了广义连通度、h-额外连通度、h-分支连通度和结构连通度等既考虑网络连通性又考虑网络弹性的图结构参数,这些参数能够更好地估计互连网络的容错性水平.本文利用反证法、归纳法和图结构分析等方法,研究广义连通度、h-额外连通度、h-分支连通度和结构连通度参数的值、界、极值问题以及其逆问题.具体工作如下:研究了一般图的h-分支连通度,计算了路、圈、轮图、完全二部图和完全多部图的h-分支连通度的值;基于一般图的h-分支连通度的单调性,给出了一般图和树的h-分支连通度的界;研究了给定h-分支连通度的一般图和树的逆问题;讨论了h-分支连通度的极值问题,得到了三类极值参数s（n,k）、f（n,k）和g（n,k）的结果.超立方体图是并行计算机系统的互连网络基本拓扑结构之一,许多复杂网络结构都是在超立方体图基础之上,通过乘积操作或扩展变形得到的.立方体连通循环图和分层超立方体图是将超立方体图的每个顶点分别替换成圈和超立方体图变形得到网络拓扑结构,它们不仅继承了超立方体的正则性、对称性和高容错性等特征,而且具有更优化的网络通信能力和小的固定顶点度等性质,这些拓扑结构极大提高了互连网络的性能.本文通过分析立方体连通循环图和分层超立方体图的结构及其性质,得到了立方体连通循环图和分层超立方体图的广义4-连通度的值.大规模和超大规模网络拓扑结构可以通过图变换得到,Mycielskian图是一种通过图变换得到的图,它是具有任意大色数但不含三角形的图类.本文通过分析Mycielskian图的构造特征,研究了 Mycielskian图的h-额外连通度和结构连通度,得到了 Mycielskian图与其原图的h-额外连通度和结构连通度的关系.本文的研究结果不仅在设计更高性能的并行计算机系统具有显著实际意义,也在提高其互连网络的容错性、经济性和安全性方面具有重要理论价值.