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

项目名称： De Brujin图和Kautz图的交叉数算法及应用研究

项目编号： No.61303023

项目类型： 青年科学基金项目

立项/批准年度： 2014

项目学科： 自动化技术、计算机技术

项目作者： 王浩丽

作者单位： 天津师范大学

项目金额： 22万元

中文摘要： 图的交叉数是图的一个重要的拓扑不变量，是衡量图的非平面性的一个重要量度。图的交叉数在网络拓扑结构设计、电路板的布线及生物工程DNA的图示等方面都有广泛的应用。确定一个图的交叉数是NP困难问题，研究它对解决一般NP困难问题有重要的借鉴意义。本项目拟对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.

英文关键词： Crossing number；Network topology structure；；；