互连网络结构性质及优化设计研究

The topological structures of networks highly influence the network efficiency, the reliability and the costs of systems. This project studies the following scientific problems in the topological structure properties of networks and their optimal design by effectively using and integrating the mathematical tools in Graph Theory, Algebra, Number Theory and Coding Theory. (1) Structural properties of networks will be studied by introducing methods from Graph Theory, in particular Hamiltonian properties of faulty networks; (2) topological parameters (such as the eigenvalues of the graph adjacent matrices, the eigenvalues of Laplacian matrices, the eigenvalues of signless Laplacian matrices and the expansion rates of graphs) of network systems will be deeply investigated by integrating algebraic methods; (3) the optimal design of networks and the solvability problems of network coding will be studied using Number Theory methods. Computational methods for the problems listed above and their complexity analysis will also be addressed in this project.

网络的拓扑结构对网络的性能、系统可靠性及费用都有重大影响。本项目充分利用图论、代数、数论、编码等数学知识，研究网络拓扑图的结构性质和优化设计中的如下科学问题：(1)通过引入图论中的方法，研究网络图的各种结构性质，特别是障碍网络的哈密尔顿性质；(2)结合代数的方法，深入研究网络系统的各类拓扑参数(如图的邻接矩阵特征值、拉普拉斯矩阵特征值、无符号拉普拉斯矩阵特征值、expansion rate等)的极值及其极图；(3)利用数论、编码的理论方法，研究网络优化设计及网络编码的可解性问题。本课题还研究与上述问题相关联的各种实用性算法及算法复杂性分析。

通过探索图的结构性质以及图的结构与各种参数之间的内在联系，充分利用图论、代数、数论、编码等数学知识，我们对网络拓扑图的结构性质和优化设计中的某些问题进行了研究，取得的成果主要包括：（1）给出了网络系统的各类拓扑参数的上、下界，并刻划了达到这些界的极图；解决了Hansen 和Lucas在2010年提出的有关无符号Laplacian谱半径的两个猜想。（2）给出了猜数的上、下界；构造了一系列具有高猜数、低度数的循环凯莱图。（3）对障碍网络的性能进行研究，给出某些特殊网络的诊断度。（4）利用有限域的相关知识，构造了一类新的代数Cayley图和Wenger图。（5）对超网络的拓扑图进行研究，获得了初步的结论。..依托本项目，我们已发表SCI检索的学术论文20篇，EI检索论文1篇，已接收的SCI论文6篇，另外，还有13篇完成论文已投稿.