论文部分内容阅读
图的最优标号是图论及组合最优化中涉及顺序结构的一个专题，最优标号问题的研究内容，大致可分为算法性质及结构性质两方面．算法性质是指计算复杂性、多项式算法及近似算法的设计与分析等；结构性质包括参数的上下界、极值与极图、临界图结构、可分解性、特殊图表达式等．本学位论文主要围绕l临界图结构及可分解性展开研究，同时对特殊图类的表达式及两个新模型进行探讨．在系统地掌握该领域的前沿研究工作的基础上，本学位论文主要取得如下四个方面的创新成果。
1．4-割宽临界树
2．图的填充问题的可分解性
3.特殊图类的参数表达式
4.两个新模型
第一个新模型是min-max型填充问题。第二个新模型是图的一个边搜索顺序问题。