图的最优标号的临界性、可分解性及有关问题

摘要

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

目录

文摘

英文文摘

郑重声明

第一章绪论

第二章4-割宽临界树

第三章图的最小填充问题的分解定理

第四章k-树补图的最小填充和树宽

第五章弦图的补图的填充

第六章一些特殊图类的最小填充、侧廓和扩充侧廓

第七章图的min-max型填充问题

第八章图的一类边搜索顺序问题

参考文献

附录 博士期间完成的学术论文

致谢