超立方体及其变形的标号着色算法与应用研究

图的标号着色来自频道分配问题，在计算机和网络技术中有着广泛的应用。它是NP困难问题，研究它对解决一般的NP困难问题有重要意义。. 本项目将计算机构造和数学证明相结合，研究超立方体及其变形- - 交叉立方体、扭立方体和M?bius立方体的标号着色，研制出较好的计算超立方体及其变形的标号着色数的算法和计算超立方体及其变形的标号着色数上界的算法，以此为基础探索出一条解决基于超立方体及其变形的互连网络图的标号着色问题的有效途径，为基于超立方体及其变形的互连网络图的标号着色的实际应用提供理论基础，也为其他图簇的标号着色的求解提供借鉴。. 本项目的研究将发展图的标号着色理论，丰富用计算机算法解决图论问题的成果。

本项目将计算机搜索和数学证明相结合，研究了超立方体及其变形的标号着色，研制出了较好的计算超立方体及其变形的标号着色数的算法和计算超立方体及其变形的标号着色数上界的算法，计算出了n较小时的超立方体变形的(2,1)色数、超立方体的(d,1)全色数；n较大时超立方体的(2,1)色数更好的界。同时将这种算法应用到其他图类的研究当中，计算出了Flower snark 及其相关图、n较小时Knödel图WΔ,n 的色数；也对超立方体及其变形的其他图论性质进行了研究，并取得了较好的成果。.本项目的研究丰富了用计算机算法解决图论问题的理论成果，为基于超立方体及其变形的互连网络图的标号着色的实际应用提供更加坚实的理论基础，也有助于我们将来在该领域取得更多的成果。