几类互连网络拓扑结构图的交叉数算法及其应用研究

图G的交叉数cr(G)是图的一个拓扑不变量，它是衡量图的非平面性的一个重要量度。研究互连网络拓扑结构图的交叉数有助于确定网络交叉数和为制定该网络的VLSI线路所需要的平面布局二者之间的关系，以降低芯片造价。确定一个图的交叉数是NP困难问题，研究它对解决一般NP困难问题有重要的借鉴意义。. 本项目将研究几类重要互联网络拓扑结构图(包括n-维星图Sn、薄饼图 Pn、冒泡排序图Bn、排列图An,k、交错群图AGn、(n,k)-星图Sn,k)的交叉数，以此研究一般互联网络拓扑结构图的交叉数的性质；同时，研制出较好的计算互联网络拓扑结构图的交叉数算法与计算互联网络拓扑结构图的交叉数的上界的算法。.本项目的研究将丰富利用计算机算法解决图论问题的理论成果，对图的交叉数在互联网络的拓扑设计、电子线路板的设计等领域的研究有重要的理论意义和应用价值。

图G的交叉数cr(G)是图的一个拓扑不变量，它是衡量图的非平面性的一个重要量度。交叉数的研究是拓扑图论的一个中心问题，在过去的三十年里，包括Erdos, Guy, Turan, Tutte 等在内的一批著名的数学家都对图的交叉数进行过深入的研究。过去的研究成果表明，图的交叉数的研究在离散及计算几何领域有重要的应用，而且在超大规模集成电路和网络布线问题方面也有重要的应用。研究互连网络拓扑结构图的交叉数有助于确定网络交叉数和为制定该网络的VLSI线路所需要的平面布局二者之间的关系，以降低芯片造价。确定一个图的交叉数是NP困难问题，研究它对解决一般NP困难问题有重要的借鉴意义。 .本项目研究了几类重要互联网络拓扑结构图(包括n-维星图Sn、薄饼图 Pn、冒泡排序图Bn、排列图An,k、交错群图AGn、(n,k)-星图Sn,k)的交叉数，以此研究一般互联网络拓扑结构图的交叉数的性质；同时，研制出了较好的计算互联网络拓扑结构图的交叉数算法与计算互联网络拓扑结构图的交叉数上界的算法。.本项目的研究丰富了利用计算机算法解决图论问题的理论成果，对图的交叉数在互联网络的拓扑设计、电子线路板的设计等领域的研究有重要的理论意义和应用价值，为后续研究以及更为复杂的互连网络拓扑图的交叉数性质的研究提供了有效途径和研究方法，为图的交叉数问题在互连网络的实际应用提供更坚实的理论基础。