决定超大型并行分布式系统性能最主要的因素是各个处理器之间连接的拓扑结构,称为互连网络,简称网络.网络的拓扑结构可以用图来表示：处理器或者存储器用顶点来表示,处理器或者存储器之间的连接用边来表示.因此图论在设计网络和分析网络性能方面的优势是自然的和有力的.本文主要用图论的方法研究了平衡超立方图的一些网络性质和匹配排除及其相关问题的计算复杂性.本文共分为六章.第一章首先介绍了互连网络和图论中的一些基本概念和符号.然后我们介绍了匹配排除集、条件匹配排除集和反凯库勒集的概念.接下来我们给出了计算复杂性的一些基本概念和术语.紧接着我们给出了平衡超立方的定义、研究背景和一些性质.最后我们给出了本文的主要研究结果.第二章我们研究了匹配排除问题、反凯库勒问题、条件匹配排除问题和s-限制匹配排除问题的计算复杂性.由定义,我们表明有完美匹配的二部图上的匹配排除问题和一类称作完美匹配最小障碍集问题(minimum blocker perfect matching problem)是等价的.根据二部图上的完美匹配最小障碍集问题是NP-完全的,我们证明了二部图上的匹配排除问题也是NP-完全的.我们将二部图上的匹配排除问题通过多项式时间归约为反凯库勒问题,从而证明了二部图上的反凯库勒问题也是NP-完全的.进而,我们得到条件匹配排除问题也是NP-完全的.作为条件匹配排除数定义的推广我们提出了s-限制匹配排除数(s是正整数)的概念.同时,我们也证明了二部图上的s-限制匹配排除问题是NP-完全的.在第三章,我们研究了平衡超立方的匹配排除数和条件匹配排除数.我们得到了对于所有的正整数n,平衡超立方BHn的匹配排除数的大小均为2n,并且BHn的每个大小为2n的匹配排除集都是平凡的.进一步地,我们得到了平衡超立方的条件匹配排除数是4n-2.第四章提出了平衡超立方BEn的一个Cayley图模型,从而证明了BHn是Cayley图.这个结果推广了之前BHn是点传递的这一结果.基于此Cayley图模型,我们给出了BHn的一个最短路路由算法,第五章研究了平衡超立方BHn的限制连通性方面的一些性质.我们得到了当n≥2时,BHn的2-限制点连通度和2-限制边连通度分别为4n-2和4n-4.进一步地,我们得到了BHn的3-限制边连通度为6n-4.第六章研究了平衡超立方BHn的一类Hamiltonian路嵌入问题.由BHn是Hamiltonian laceahle的和双泛连通的,我们得到了BHn是超Hamiltonian laceable的.