最优标号与最优嵌入问题是组合最优化学科非常活跃的一个研究课题.,它具有很强的应用性,并且包含一系列内容相当丰富的理论问题.该文的研究与其中的两个问题有关.由以下两部分组成:(1)一些图的填充问题,(2)一些图的树宽问题.1一些图的填充问题填充问题具有强烈的实际背景.在实际中经常要处理一个稀疏的对称正定方阵的线性方程组Ax=b的求解问题,其中A为稀疏的,即其中非零元较少,大部分是零.在运用Gauss消去法或Cholesky分解法求解时,消去过程中有的零元会变为非零元,这称为矩阵的填充.如果消元顺序不当,填充的非零元越来越多,增加了存贮量,便会影响运算速度,降低工作效率.所以在消元过程中,需要确定适当的消元顺序,使填充的非零元较少.这称为矩阵的填充优化问题.由于正定对称矩阵与一个图相对应,由此导出了图的填充问题.2.一些图的树宽问题.树宽问题是Robertson和Seymour在建立图的minor理论时提出的两个概念之一[6-7].刘振宏和王常藩从算法复杂性的估计中提出了另一参数"核密度"[8].杨爱民和林诒勋在文[9]又证明核密度就是树宽,它们相应于矩阵的消去过程的波前宽度.这个问题同样是围绕着计算复杂性、算法理论、特殊图结果、运算性质等方面进行.S.Arnborg, D.Corneil和A.Proskurowski于1987年证明了树宽问题的NP-完全性[15],文[9]中推得确定弦图的树宽是多项式可解的.关于特殊图的结果,图论工作者已经涉足此领域,但与其它标号问题相比,结果还不多.对于一些已知结构的图,也可以利用分解、约化定理来确定其树宽,而且若知道其下界,又能构造一种标号,使其达到下界值,则此图的树宽也能确定.