k树的完美消除序列

Perfect Elimination Orderings of k-Trees

摘要: 弦图的完美消除序列可应用于用高斯消去法求解稀疏正定线性方程组的研究，并且弦图的完美消除序列在多个学科均有应用。本文主要研究弦图的子类——k树的完美消除序列，首先证明了k树的完美消除序列可以通过k度点来刻画。其次证明了k树T_k(n)的节点按照完美消除序列排序后满足：1) ；2) 。最后证明了k树完美消除序列与k树构造过程之间以互逆的方式一一对应。此外，本文也将前述证明应用于k树的识别，给出了相应的算法。

Abstract: The perfect elimination orderings of chordal graphs can be applied to the study of solving sparse positive definite systems of linear equations by Gaussian elimination method, and the perfect elim-ination orderings of chordal graphs is applied in many disciplines. In this paper, we mainly study the perfect elimination orderings of k-trees, a subclass of chordal graphs. First, we prove that the perfect elimination orderings of k-trees can be characterized by vertices with k degrees. Secondly, it is proved that the vertices of k-trees which are sorted according to the perfect elimination orderings satisfy: 1) ; 2) . Finally, this paper proves that the perfect elimination orderings of k-trees corresponds to the construction process of k-trees in a reciprocal way. In addition, this paper also applies the above proofs to the recognition of k-trees and gives the corresponding algorithm.