De Brujin图和Kautz图的交叉数算法及应用研究

The crossing number of a graph is an important topological graph invariant, which is also an important measure of measuring the non-planarity of graphs. The crossing number of graphs have a wide range of applications in various aspects such as design of network topological structure, wiring of electronic circuit board and drawing of biological engineering DNA. Determining the crossing number of a graph is a NP-hard problem and it is of important significance to solve the general NP problem. This project intends to make a study on the crossing number of de Brujin graphs and Kautz graphs, to give better algorithms to calculate the crossing numbers and upper bounds of network topology graphs, and then to study on the properties of crossing numbers of general network topology graphs. Research on the crossing number of a graph in this project is of important theoretical significance and practical application value in various fields.

图的交叉数是图的一个重要的拓扑不变量，是衡量图的非平面性的一个重要量度。图的交叉数在网络拓扑结构设计、电路板的布线及生物工程DNA的图示等方面都有广泛的应用。确定一个图的交叉数是NP困难问题，研究它对解决一般NP困难问题有重要的借鉴意义。本项目拟对de Brujin图和Kautz图的交叉数进行研究，并给出较好的计算网络拓扑结构图的交叉数及其上界的算法，在此基础上研究一般网络拓扑图的交叉数的性质。本项目的研究对图的交叉数在网络拓扑设计、电路板设计等领域的研究有重要的理论意义和应用价值。

图的交叉数是图的一个拓扑不变量，它是衡量图的非平面性的一个重要量度，在实际中有广泛的应用，如电子线路板设计中的布线问题、草图识别与重画问题、网络拓扑结构设计等。利用计算机对图进行研究的重要性是显而易见的。确定一个图的交叉数是NP困难问题，研究它对解决一般NP困难问题有重要的借鉴意义。本项目综合使用了算法、图论以及组合数学的工具对几类重要的网络拓扑图的交叉数及相关的组合数进行了研究，并取得了一些成果。这包括给出n-dimensional folder hypercubes 与n-dimensional locally twisted cube 的交叉数的上界；确定了crossed cube，locally twisted cube，Mobius cube 在阶不超过4 时的交叉数；在 Erdos 和 Guy 于上世纪70年代提出来的超立方体交叉数的一个公开问题的研究上取得重要进展。