几类k元n维互连网络的交叉数算法研究及应用

Network topology is one of crucial factors for interconnection networks since it determines the performance of a network. The crossing number of a network is directly related with the layout of the network. Determining the crossing number of a graph is NP-hard. Therefore, the researches on crossing number might provide a effective method to study NP-hard problems. Combined the computer aided design and mathematical method, the project is to study the crossing numbers of several representative types of k ary n dimensional interconnection networks- - k ary n cube, augmented k ary n cube, k ary n dimensional butterfly network, k ary n dimensional shuffle/exchange network and k ary n dimensional De Bruijn network..The main works of the project are: (1) Designing effecitive computing strategy, and develop an algorithm to compute the upper bound of the crossing numbers of the networks mentioned above. (2) Analysing the properties of the networks, to construct drawings that could be well extended and be easily applied to the real network. (3) Proposing new methods to prove the lower bounds of the crossing numbers of the networks, where new crossing grouping techniques and new functions to counting the number of crossings might be studied. .In a word, the project will study the crossing numbers of the k ary n dimensional interconnection networks comprehensively and systematicly. The research will enrich the field that using the computer algorithms to solve some hard problem in graph theory. The research is of great signification to applying the achivement in crossing number to the design of the topological structure of a network or a circuit.

互连网络拓扑结构决定着高性能计算系统和网络的通讯性能，其交叉数与网络布局的计算机辅助设计直接相关。确定一个图的交叉数是NP困难问题，研究它对解决一般NP困难问题有重要借鉴意义。本课题将计算机构造与数学证明相结合，研究几类典型的互连网络：k元n维立方体、Augmented k元n维立方体、k元n维蝶形网、混洗交换网和DeBruijn网的交叉数性质。(1)设计有效的计算策略，研制计算k元n维互连网络交叉数上界的算法；(2)利用计算结果，分析网络特征，构造扩展性和实用性好的平面布局画法；(3)给出有效的交叉数分组统计技术，结合网络拓扑属性，发展新的交叉数下界证明方法。在k元n维互连网络的交叉数问题方面开展系统全面的研究，探索大规模互连网络的交叉数研究方法。本项目研究将丰富利用计算机算法解决图论问题的理论成果，对交叉数在互连网络拓扑设计、电子线路板设计等领域的研究有重要理论意义和应用。

随着信息技术的飞速发展，可供研究的领域数据越来越丰富，大规模网络的理论研究、算法设计、应用实施和平台架构为基于大数据的定量化分析提供了研究基础，推动了系统生物学、社会学、心理学、管理学等多个学科发展。.互连网络拓扑结构决定着高性能计算系统和网络的通讯性能，其交叉数与网络布局的计算机辅助设计直接相关。确定一个图的交叉数是NP困难问题，本项目对k元n维立方体网络的交叉数问题展开研究。计算n和k较小时，k元n维立方体的全局交叉数，设计了有效的分支限界策略，以有效的过滤同构子图，平衡子图的删边数和中间子图数之间的计算时间代价，计算了k不大于4，n不大于9时的k元n维立方体的交叉数。并将此结果用于计算小规模De Bruijn图的交叉数问题。互连网络顶点数随着n和k的增大呈指数增长，交叉点数等拓扑属性值也急剧增长。对n，k进一步增大时， k元n维立方体、De Bruijn图等互连网络图的交叉数及画法布局复杂度急剧增大，计算全局交叉数更加困难。因此转而考虑网络的局部拓扑属性，计算网络中的重要节点，围绕这些关键节点构造了局部网络的具有较好交叉点数的好的画法。基于此，我们对k元n维立方体及其相关网络在n、k进一步增大的交叉数上界进行了计算，给出了一种具有较少交叉点数的局部子网络的画法以及将局部子画法组合成整个网络具有较少交叉点数的好的画法。.此外，课题结合大规模复杂网络的网络聚集系数、特征路径长度、网络集簇性质、模块性等拓扑属性，将网络节点重要性的评估方法和图的同构判定方法应用于Web服务发现问题、图聚类算法及复杂网络建模等问题中，设计开发了一个大规模网络数据处理平台。