论文部分内容阅读
书嵌入数是对图进行分类的一个拓扑标准，通常来说，计算一个图的书嵌入数及给出一种嵌入实例都是NP完全问题。针对Rivas-Eddy（R＆E）类中RNA分子的二级结构图，从二级结构图的语法出发，通过其交叉关系图的点着色，构造性地得到了RNA分子二级结构图书嵌入的具体实现方法，完成了对RNA分子二级结构的书嵌入分类。该方法具有多项式时间复杂性，为求解NP完全问题提供了有益的参考。