超立方体及其变型的交叉数算法及应用研究

图的交叉数是衡量图的非平面性的一个重要指标。研究互连网络图的交叉数有助于确定网络交叉数和为制定该网络的VLSI线路所需要的平面布局二者之间的关系，以降低芯片造价。确定一个图的交叉数是NP困难问题，研究它对解决一般NP困难问题有重要的借鉴意义。.本课题将计算机构造证明与数学证明有效结合，对互连网络图――超立方体及其三种变型交叉立方体、纽立方体、M?bius立方体的交叉数进行研究，研制出较好的计算基于超立方体及其变型的互连网络图的交叉数上界的算法，以此为基础探索基于超立方体及其变型的互连网络图的交叉数性质。.本项目的研究将丰富利用计算机算法解决图论问题的理论成果，对图的交叉数在互连网络拓扑设计、电子线路板设计等领域的研究有重要的理论意义和应用价值。