网络拓扑结构图的交叉数、算法及其应用研究

The crossing number cr(G) is an important topological invariant of graph, is an impordent scale to measure the graph non planarity. The research for the crossing number of network topology is helpful for determining the crossing number of network, improving the layout of a VLSI circuit for that network, improving the performance of chips, reducing the cost of chips. Determining the crossing number of graph is NP-hard, the reserch on it can provede important experience for solving genernal NP-hard problems. . This project will develop better algorithm for calculating the crossing number of network topology and the algorithm for calculating the upper bound of the crossing number of network topology. Research on the crossing number of graphs related to three main design methods (Cartesian product method, Line graph method and Cayley method) of network topology by utilizing these algorithm, and research character of the crossing number of gerernal network topology upon this.. The research of this project will abundant in theory produce of utilizing computer algorithm to solve the problem in graph theory and will provide more solid theory foundation for practical application of Internet and Internet of things. Meanwhile, the research work will make contributions to cultivating young backbone teachers in minority nationality areas.

图G的交叉数cr(G)是图的重要拓扑不变量，是图的非平面性的重要度量尺度。对网络拓扑结构图的交叉数的研究有助于确定网络交叉数，改善该网络的VLSI线路的平面布局，进而提高芯片性能，降低芯片造价。确定图的交叉数问题是NP困难问题，研究它对解决一般NP困难问题可提供重要的借鉴。. 本项目将研制出更好的计算网络拓扑结构图的交叉数算法与计算网络拓扑结构图的交叉数上界的算法。利用这些算法对3种主要网络拓扑结构设计方法----笛卡尔乘积方法、线图方法、Cayley方法的相关图的交叉数进行研究，并以此研究一般网络拓扑结构图的交叉数的性质。. 本项目的研究将丰富利用计算机算法解决图论问题的理论成果，将为互联网，物联网等实际应用提供更加坚实的理论基础，并为培养从事该领域研究的少数民族地区青年骨干教师做出一定贡献。

图的交叉数问题是在实际应用中提出的，在计算几何学、超大规模集成电路设计以及计算机科学理论研究等方面有着广泛的应用。.图的交叉数问题研究的是如何把图画在一个平面上，使其交叉的数目最少。长期以来，图的交叉数的研究主要采用纯数学方法，在解决一些特殊图和简单图的交叉数方面取得了一些成果。但随着所研究图的增大，可能的画法急剧增长，研究也越来越困难。因此，迫切希望有较好的计算机算法用以计算图的交叉数。. 本项目研制出了更好的计算网络拓扑结构图的交叉数算法与计算网络拓扑结构图的交叉数的上界的算法，并利用这些算法对3种主要网络拓扑结构设计方法--笛卡尔乘积方法、线图方法、Cayley方法的相关图的交叉数进行研究，并以此研究一般网络拓扑结构图的交叉数的性质。对网络拓扑结构图的交叉数的研究有助于确定网络交叉数，改善该网络的VLSI线路的平面布局，进而提高芯片性能，降低芯片造价。.本项目已经研制出了计算n阶网络拓扑结构图的交叉数的上界的算法；研制出了更好的计算顶点数较少(n<=20)的网络拓扑结构图的交叉数算法；研制出了计算顶点数较多（20<|V|<=100）的网络拓扑结构图的交叉数上界的算法。对与互连网络拓扑结构设计方法密切相关的几个重要的图类的交叉数进行了研究，得到了如下结果：. (1) 运用设计的算法，研究了笛卡儿乘积图类Km×Pn和Km,n×Pl 图、Km×Cn和 Km,n×Cl 图的交叉数。 . (2) 运用设计的算法，研究了Cayley图类薄饼图Pn的交叉数。. (3) 运用设计的算法，研究了超立方体变型网络图类局部扭立方体网络LTQn、 交叉立方体网络CQn、莫比乌斯立方体网络MQn、折叠超立方体网络 FQn、平衡超立方体网络BHn、扭立方体TQn的交叉数。 .相关的学术论文28篇已发表和录用在Discrete Applied Mathematics、IEEE ACCESS等重要期刊上，其中被SCI收录16篇、被EI收录4篇。.本项目的研究将丰富利用计算机算法解决图论问题的理论成果，将为互联网，物联网等实际应用提供更加坚实的理论基础，并为培养从事该领域研究的少数民族地区青年骨干教师做出一定贡献。