当今的超级计算机包括成千上万的处理器,它们都是大规模并行系统。互连网络是设计超级计算机过程中必不可少的组成部分,在很大程度上决定并行计算机的性能。在选择互连网络时,如何选择一个合适且高效的互连网络拓扑结构是现在急需解决的问题。在这样的背景下,广大学者相继设计了各式各样的网络拓扑结构。但是如何衡量一个网络的优劣,且衡量这个网络拓扑结构优劣需要参考什么参数的问题相继出现。人们希望通过比较这些互连网络拓扑结构图的相关参数来找出一种较优的互连方式,从而设计出更好的计算机系统。消圈数,也称反馈数,是衡量网络拓扑结构性能优劣的重要参数之一。它作为图论研究中最经典的问题之一,已经在计算机科学、互连网络和通信等领域中有极其重要的应用。求解图的消圈数问题属于NP-hard问题。但到目前为止已经给出消圈数的图类还较少,甚至已给出较好消圈数界的图类也不多。尤其是一些较复杂的图类(包括有重要应用前景的互连网络拓扑结构图)的消圈数问题还有待进一步解决。本文将求解图的消圈数问题转化为构造图的含有尽可能多的顶点的可递推无圈子图的问题,采用数学构造与计算机分支限界搜索交互的方法,通过反复交互来完成数学构造,最后用数学方法证明结论,给出待解决图类消圈数的精确值或者更紧的界。研究了平衡超立方体网络、Kn(?)del图和Goldberg Snarks及其相关图消圈数,分别给出了它们消圈数较紧的界。(1)利用平衡超立方体网络BHn顶点递推结构和边集性质,通过三分离集的方法,得出了平衡超立方体网络可递推的无圈子图顶点集函数,基于这些函数,给出了平衡超立方体网络消圈数紧的界:[22n-1(1-1/2n-1)+1/2n-1]≤f(BHn)≤22n-22n-1-2n+1(2)利用Kn(?)del图的循环结构,通过设计的分支限界条件,找到了 Kn(?)del图度为5时带循环节的无圈子图顶点集的构造方法,基于这些顶点集,给出了 Kn(?)del图度为5时的消圈数紧的界:[3n+2/8]≤f(W5,n)≤[3n+6/3](3)利用Goldberg Snarks及其相关图的循环结构的构图特点,构造了无圈导出子图顶点集,得到了 Goldberg Snarks及其相关图的消圈数的精确值为:f(n)=2n+1