网络拓扑结构图的消圈数及其算法研究

The decycling number(or feedback number) is an important performance parameter of network topology structure. It can measure the ability of a multi-core system to recover from a deadlock and to avoid broadcast storm. Some important applications of the problem are in order to make more efficient use of the available bandwidth wavelength converters, in attacking networks to seek for the minimum attack vertex sets, et al. Determing the decycling number of graph is NP-hard problem. In this project, we will focus on the decycling number of graph which related to interconnection network topology structure design method. This project will develop better algorithm for calculating the decycling number of graph according to the characteristics of these graphs. We will research on the recursive infinite constructor of acyclic subset which contains vertices as much as possible by the less vertices.By the branch and bound method, we will use the way to construct basis acyclic subgraph with appropriate scale and regular size and obtain tight bounder or exact values of the decycling number for these graphs. The aim of this project is developping better algorithm for calculating the decycling number of graph according to the characteristics of these graphs and give their exacted value or tigher bound. Then we will develop new method and new technology of decycling number. The research will not only provide the further theoretical for the next generation of very large scale super-computer system design of interconnection networks, but also provide references for solving other NP-hard problems. Thus, the research of this project will abundant in theory produce of utilizing computer algorithm to solve the problem in graph theory.

图的消圈数(反馈数)是衡量网络拓扑结构的重要性能参数，它可以衡量多核系统的规避死锁能力和规避广播风暴的能力、在光纤网络中波长转换器的安装问题、选择最小攻击点集问题等领域也有着广泛应用。确定图的消圈数问题是NP困难问题。本项目着重研究与互连网络拓扑结构设计方法相关的图的消圈数，根据这些图类特点研制较好的计算图的消圈数算法；对顶点数比较少的图探讨无圈子图顶点尽可能多的可递推的无限极的构造函数；探索分支限界条件构造规模适当且有规律的基础无圈子图以求取图消圈数的精确值或者比较紧的界。本项目的目标是根据这些图类特点研制较好的计算图的消圈数算法，给出它们的精确值或更好的界，并探索消圈数研究的新方法和新技术。本项目对网络拓扑图消圈数的研究将为下一代超大规模超级计算机系统的互连网络的设计提供更多的理论依据，同时也为解决其他NP困难问题提供重要的借鉴，从而进一步丰富利用计算机算法解决图论问题的理论。

多核技术的发展使得现行的硬件技术构造大规模计算机互连网络和并行超级计算机系统成为可能。如何选择一个合适和理想的互连网络拓扑结构成为建造超级计算机系统的关键。图的消圈数(反馈数)是衡量网络拓扑结构的重要性能参数，它可以衡量多核系统的规避死锁能力和规避广播风暴的能力、在光纤网络中波长转换器的安装问题、选择最小攻击点集问题等领域也有着广泛应用。确定图的消圈数问题是NP困难问题。本项目着重研究与互连网络拓扑结构设计方法相关的图的消圈数，将求解图的消圈数问题转化为构造图的含有尽可能多的顶点的可递推无圈子图的问题，从而给出待解决图类消圈数的精确值或者更紧的界。对待解决各类图，探索出的构造图的含有尽可能多的顶点并且可递推无圈子图点集的回溯算法中的合适的分支限界条件，为提高算法速度奠定基础。基于所探索出来分支限界条件，进一步改进构造图的含有尽可能多的顶点并且可递推无圈子图点集的回溯算法，利用该算法给出待解决的网络拓扑结构图的消圈数的精确值或者更紧的界。本项目进一步丰富利用计算机算法解决图论问题的理论，为更精确的度量超级并行计算机的结构和性能提供理论依据，对互连网络的优化设计、量化分析和性能评估将起到重要的指导作用，同时对于解决一般NP-hard问题起到借鉴意义。