互连网络拓扑结构图的反馈数、算法及应用研究

本项目是研究互连网络拓扑结构图的反馈数问题，它是计算机科学与组合数学和图论交叉的研究课题。图的反馈数问题来源于实际问题，在诸多领域如预防计算机死锁，互连网避免广播风暴以及电子电路检测等问题中有着广泛的应用。已经被证明求图的反馈数问题是NP困难问题，研究它对解决一般NP困难问题有借鉴意义。. 本项目旨在研制出较好的计算图的反馈数的算法，并以此研究与互连网络拓扑结构相关图的反馈数；确定与互连网络拓扑结构相关图的反馈数的紧的上下界；同时研究一般图的反馈数尽可能紧的上下界；从而能更好的解决与反馈数有关的实际问题。. 本项目的研究将丰富利用计算机算法解决图论问题的理论成果，对互连网络拓扑结构相关图的反馈数的研究结果对互连网络的设计、网络性能的定量分析和评估起着重要的理论指导作用，也为下一代超大规模超级计算机系统的互连网络的设计提供进一步的理论依据。

本项目是研究互连网络拓扑结构图的反馈数问题，它是计算机科学与组合数学和图论交叉的研究课题。图的反馈数问题来源于实际问题，在诸多领域如预防计算机死锁，互连网络避免广播风暴以及电子电路检测等问题中有着广泛的应用。求图的反馈数问题已被证明是NP困难问题，其每一个进展都十分艰辛。研究它对解决一般NP困难问题有借鉴意义。　　　　.本项目旨在研制出较好的计算图的反馈数的算法，并以此研究与互连网络拓扑结构相关图的反馈数；确定与互连网络拓扑结构相关图的反馈数的紧的上下界；同时研究一般图的反馈数尽可能紧的上下界，从而能更好的解决与反馈数有关的实际问题..本项目已经研制出计算互连网络拓扑结构图的反馈数算法；对与互连网络拓扑结构设计方法(笛卡儿乘积方法、线图方法、Cayley方法)密切相关的几个重要的图类的反馈数进行了研究，得到了如下结果：.(1)研究出与笛卡儿乘积方法相关的图类: 局部扭立方体网络LTQn、交叉立方体网络CQn、增广立方体网络AQn反馈数的上下界； .(2)研究出与Cayley方法相关的图类：冒泡排序图Bubble-sort graph 、交错群图Alternating group graph 、(n,k)-星图、(n,k)-arrangement图的反馈数的上下界；.(3)研究出与线图方法相关的图类：Kautz 有向图 、Kautz无向图UK(d,n)、Generalized Kautz有向图反馈数紧的上下界； .(4)研究出与亚循环图相关的图类：广义彼特森图Pertersen graph P(n,k)、Flower Snark相关图、Knodel图W3,n、W4,n和部分循环图Cn(1,k)的反馈数的精确值；.(5)研究出一般r-正则图G中给定围长为g的条件下的反馈数的上界，以及k-正则图二部图G的反馈数的上界。.本项目的研究结果丰富了利用计算机算法解决图论问题的理论成果，对互连网络的设计、网络性能的定量分析和评估起到重要的理论指导作用，也为下一代超大规模超级计算机系统的互连网络的设计提供进一步的理论依据。