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.

1. 引言

弦图自20世纪50年代产生于稀疏线性系统的研究中，其历史与半定优化的历史有重要关联。Parter S曾将图的“弦化¹”与求解线性方程组的高斯消去法对应起来，由图“弦化”的复杂性来估计求解线性方程组的复杂性 [1]。弦图的概念被提出来后，许多学者研究发现弦图的应用与变量消除相辅相成，任意图的变量消除过程都可以对应其“弦化”过程。变量消除在许多应用中是一种自然的方法，基于不同形式的变量消除的各种算法可以通过图中节点的删除来描述和分析，这在一定程度上解释了弦图研究的学科多样性。之后Rose D J对弦图上的变量消除以及弦图的特殊性质做了一个介绍，给出了弦图完美消除序列的概念，弦图上的完美消除序列可以在不引入填充边的情况下完成变量消除 [2]。弦图变量消除的其中一个应用是概率图模型，在概率图模型上，概率计算可以以变量消除的形式出现，而在以弦图为模型的概率计算中，弦图的完美消除序列就是计算代价最小的变量消除推理的消除顺序，这也说明了关于完美消除序列的研究意义 [3]。

近年来，大量学者发现以弦图为研究对象时，图论问题会变得更加容易解决，于是，学者们开始在弦图上讨论图论中的组合问题：最大团、最大独立集、k着色等；同时，基于弦图结构的研究也获得了一些进展，Rouzbahani Malayeri M已经证明了弦图的二项式边理想的正则性上界 [4]，Arvind V已经证明弦图GI (graph isomorphism，图同构)问题的复杂性以叶龄为参数 [5]；并且，弦图子类在图论问题上的表现也是近年的热点问题，Liu C H已经给出了罗马支配问题在强弦图上的线性时间算法 [6]，Uehara R已经证明GI问题在弦二部图和强弦图上是GI完全的 [7]；此外，弦图在许多领域都有应用，包括编译器构造和数据库 [8]。

k树是弦图的一个特殊子类，同时k树作为树这一概念的扩展，可以作为很多图论问题的模型，而k树本身的特殊结构在约束满足问题，组合问题等问题上存在多项式时间算法。目前对于k树的研究主要集中于部分k树(树宽由k限定的图)，Telle J A已经将部分k树上的算法设计应用于顶点划分问题，得到了以树宽为时间复杂性参数的算法 [9]。k树作为有特殊结构的弦图子类，在某些问题上会比弦图发挥更好的性能，后续可以进一步研究。

本文启发于Rose D J在文献 [2] 里提出的“k树是弦图的一个子类”，于是，“具有特殊结构的弦图子类——k树的完美消除序列的特殊性质”成为了一个研究方向。本文主要证明了以下结果：

定理1 任取k树，其完美消除序列可通过迭代地删除其中的k度点来刻画(即首先删除中的一个k度点，得到，再删去中的一个k度点，得到，重复该操作，直至所得图为k个节点，最后按任意顺序删除这k个节点，该删除顺序就是其完美消除序列)。

定理2 任取k树及的序列，标记X为，则是的完美消除序列，当且仅当满足：

1)时，，即与里的一个k团中的每一个节点均连接；

2)时，，即是团。

定理2给出了k树完美消除序列的特点，k树的节点按照完美消除序列排序后满足1) ；2)，由此可知k树的所有完美消除序列都满足定理1中的k度点的删除顺序，换而言之，通过定理1节点删除的方式可以找到k树的所有完美消除序列。

定理3 k树的完美消除序列集合与构造过程集合之间存在双射，且两个集合的元素之间以互为逆序的方式一一对应。

定理3给出了k树的完美消除序列与构造过程之间的关系。根据定理3的结论，可以从完美消除序列的角度去分析k树的构造过程，可以通过刻画k树的完美消除序列来刻画k树的构造过程，也可以通过计算k树完美消除序列的个数来计算k树构造过程的个数。

2. 基础知识

本文用来表示一个无向图，其中，X是一个非空有限的节点集合，E是X中成对节点的集合，E中节点对由无向边连接(本文基于无向图进行讨论，后续简称无向图为图)。在图中，任取一个含于X的非空节点集合C，如果C里任意两个节点都在G中连接，则称C为一个团(后续简称k个节点构成的团为k团)，如果X里任意两个节点都在G中连接，则称G为完全图。

一个双射被叫做图G的序列，令是的逆映射，定义为节点x对应的序列号。可以根据序列标记点集X，并且得到点集X的一个表示:。在图中，如果对每一个，都有，即，则称为G的一条路径。在图中，如果节点与节点可以通过一条路径连接，则称与连通，如果点集X里任意两个节点都连通，则称图G为连通图(本文基于连通图进行讨论)，如果路径满足，则称为图G的一个环，且环长为，以下基于环长给出弦图的定义。

定义1 [3] 令是图中的一个环，环中的一条弦是连接两个不连贯节点与的一条边，对，如果任意环有一条弦，那么图G称为弦图。

对于图和子集，有导出子图，其中。对于图以及节点，用表示图G删除节点x及其连接边所得到的图。图的一个割S是使得导出子图有两个及以上连通分支的X的子集，且连通分支可以表示为，导出子图就是图G相对于割S的叶。图G的一个割是使得节点a与节点b分别在不同分支的割，图G的一个极小割是不存在真子集是割的一个割。关于割，Rose D J。已证明以下结果：

定理4 [2] 一个图，G带有割团S和叶，若是的割，则也是图G的割，若是 $L_i$ 的一个极小 $a,b$ 割，则 $S_0$ 也是图G的一个极小 $a,b$ 割。

本文用 $Adj\left(x_i\right)$ 表示节点 $x_i$ 在图G中相邻节点(简称邻节点)的集合，用 $d\left(x_i\right)=\left|Adj\left(x_i\right)\right|$ 表示节点 $x_i$ 在图G中邻节点的个数，并称其为度。用 $MAdj\left(x_i\right)=Adj\left(x_i\right)\cap {\left\{x_j\right\}}_{j=i+1}^n$ 表示节点 $x_i$ 在图G中的单调相邻节点(简称单调邻节点)的集合。在图 $G=\left(X,E\right)$ 中，对任意节点 $x\in X$，其邻节点集合 $Adj\left(x\right)$ 里不相邻的成对节点的集合，表示为 $D\left(x\right)=\left\{\left\{y,z\right\}|y,z\in Adj\left(x\right),y\notin Adj\left(z\right)\right\}$，并称为亏数，而满足 $D\left(x\right)=\varnothing$ 的节点x被称为单纯点。相应的，其单调邻节点集合 $MAdj\left(x\right)$ 里不相邻的成对节点的集合，表示为 $MD\left(x\right)=\left\{\left\{y,z\right\}|y,z\in MAdj\left(x\right),y\notin Adj\left(z\right)\right\}$，并称为单调亏数。

定义2 [2] 取图 $G=\left(X,E\right)$ 的一个序列 $\alpha$， $\alpha$ 标记点集X为 ${\left\{x_i\right\}}_{i=1}^n$，如果满足对任意节点 $x_i\in X$，都有 $MD\left(x_i\right)=\varnothing$，则称序列 $\alpha$ 是图G的一个完美消除序列。

定理5 [2] 一个图 $G=\left(X,E\right)$ 是弦图当且仅当图G存在序列 $\alpha$，使得 $\alpha$ 是G的完美消除序列。

下面给出本文的中心——k树的定义。

定义3 [10] k树的定义如下：

1) k个节点的k树是k个节点的完全图；

2) 给定任意n个节点的k树 $T_k\left(n\right)$，可以通过连接第 $n+1$ 个节点与 $T_k\left(n\right)$ 中某个k团的所有节点，得到 $n+1$ 个节点的k树 $T_k\left(n+1\right)$。

(由k树的递归定义可知，每一个k树都有一个k团作为初始状态，该k团被称为k树的初始团。)

定理6 [10] 一个图 $G=\left(X,E\right)$ 是一个k树当且仅当

1) 图G是连通图；

2) 图G有一个k团但没有 $k+2$ 团；

3) 图G的每一个极小 $a,b$ 割都是一个k团。

3. 定理1和定理2的证明

为了讨论k树的完美消除序列，本文先证明了关于k树和完美消除序列的几个引理。引理2的证明过程对k树的结构有一个初步的分析。引理3进一步分析了完美消除序列在k树上的特点。

引理1一个完全图的任意序列都是其完美消除序列。

证 任取完全图 $G=\left(X,E\right)$，其中 $\left|X\right|=n$，任取X的序列 $\alpha$，由 $\alpha$ 标记X为 ${\left\{x_i\right\}}_{i=1}^n$，易知 $MAdj\left(x_i\right)={\left\{x_j\right\}}_{j=i+1}^n$，于是 $MAdj\left(x_i\right)$ 是个团，从而 $MD\left(x_i\right)=\varnothing$，故 $\alpha$ 是完全图G的完美消除序列。由 $\alpha$ 的任意性，引理得证。

引理2 k树是弦图。

证 任取n个节点的k树 $T_k\left(n\right)=\left(X,E\right)$，令 $T_k\left(k\right),T_k\left(k+1\right),\cdots ,T_k\left(n\right)$ 表示 $T_k\left(n\right)$ 的构造过程，由 $T_k\left(n\right)$ 的构造过程标记X为 ${\left\{x_i\right\}}_{i=1}^n$，其中 $T_k\left(k\right)={\left\{x_i\right\}}_{i=1}^k$ 是k树的初始团， $x_i\left(i>k\right)$ 代表构造 $T_k\left(i\right)$ 时在 $T_k\left(i-1\right)$ 上添加的节点，令 $V_i\left(i>k\right)$ 表示节点 $x_i$ 连接的 $T_k\left(i-1\right)$ 中的k团，且 $y_i=x_{n+1-i}\left(i=1,2,\cdots ,n\right)$，则有

$MAdj\left(y_i\right)=Adj\left(y_i\right)\cap {\left\{y_j\right\}}_{j=i+1}^n=Adj\left(x_{n+1-i}\right)\cap {\left\{x_j\right\}}_{j=1}^{n-i}=\{\begin{array}{l}{\left\{x_j\right\}}_{j=1}^{n-i}\left(n+1-i\le k\right)\\ V_{n+1-i}\left(n+1-i>k\right)\end{array}$.

易知 $MAdj\left(y_i\right)$ 是团，从而 $MD\left(y_i\right)=\varnothing$，由定义2可知 ${\left\{y_i\right\}}_{i=1}^n$ 对应的序列就是k树 $T_k\left(n\right)$ 的完美消除序列，由定理5可知k树是弦图。

引理3在节点个数大于k的k树中，一个节点是单纯点当且仅当它的度为k。

证 任取k树 $T_k\left(n\right)\left(n>k\right)$，当 $n=k+1$ 时，易知 $T_k\left(k+1\right)$ 是个完全图，其节点均为k度，同时均为单纯点，命题成立。下面对 $n>k+1$ 时的情况进行证明。

设k树 $T_k\left(n\right)=\left(X,E\right)$，由 $T_k\left(n\right)$ 的构造过程标记X为 ${\left\{x_i\right\}}_{i=1}^n$，其中 ${\left\{x_i\right\}}_{i=1}^k$ 是k树的初始团，由构造过程可知 ${\left\{x_i\right\}}_{i=1}^{k+1}$ 也是个团。令 $V_i\left(k+2\le i\le n\right)$ 表示引入 $x_i$ 时，与 $x_i$ 相连接的k团。下面将X分为 ${\left\{x_i\right\}}_{i=1}^{k+1}$ 和 ${\left\{x_i\right\}}_{i=k+2}^n$ 分别进行讨论。在 ${\left\{x_i\right\}}_{i=1}^{k+1}$ 里，已知 ${\left\{x_i\right\}}_{i=1}^{k+1}$ 是个团，由 $T_k\left(n\right)$ 的构造过程可知，设节点 $x_p$ 是 ${\left\{x_i\right\}}_{i=1}^{k+1}$

里的k度点，则 $x_p$ 一定不含于后续连接团，即 $x_p\notin {\displaystyle \underset{i=k+2}{\overset{n}{\cup }}{V}_i}$ (因为 ${\left\{x_i\right\}}_{i=1}^{k+1}$ 是个团， $x_p$ 至少有k个邻节点，

若 $x_p$ 含于后续连接团，则其度一定大于k)，于是有 $Adj\left(x_p\right)={\left\{x_i\right\}}_{i=1}^{k+1}-\left\{x_p\right\}$，易知 $Adj\left(x_p\right)$ 是个团，从而 $D\left(x_p\right)=\varnothing$。在 ${\left\{x_i\right\}}_{i=k+2}^n$ 里， ${\left\{x_i\right\}}_{i=k+2}^n$ 里的节点在引入时就已经连接了一个k团，设节点 $x_q$ 是 ${\left\{x_i\right\}}_{i=k+2}^n$ 里

度为k的节点，则 $x_q$ 一定不含于后续连接团，即 $x_q\notin {\displaystyle \underset{i=q+1}{\overset{n}{\cup }}{V}_i}$，于是有 $Adj\left(x_q\right)=V_q$，而 $V_q$ 是引入 $x_q$ 时， $x_q$

所连接的k团，于是 $D\left(x_q\right)=\varnothing$。综上， $T_k\left(n\right)$ 中的k度点x均满足 $D\left(x\right)=\varnothing$，均为单纯点。

反之，由 $T_k\left(n\right)$ 的构造过程易知 $T_k\left(n\right)$ 的任意节点x均满足 $d\left(x\right)\ge k$ (因为 $T_k\left(n\right)$ 的节点集合由构造过程排序后，前 $k+1$ 个节点本身构成了一个 $k+1$ 团，它们的度至少为k，后 $n-k-1$ 个节点，在引入的时候就已经与一个k团相连接，它们的度也至少为k)。假设存在度大于k的单纯点y，那么 $\left\{y\right\}\cup Adj\left(y\right)$ 是个团，且 $\left|\left\{y\right\}\cup Adj\left(y\right)\right|>k+1$，这与定理6中k树没有 $k+2$ 团的性质相矛盾，所以 $T_k\left(n\right)$ 中单纯点的度均为k。

综上，引理得证。

引理4任意节点个数大于k的k树去掉一个k度点还是k树。

证 任取k树 $T_k\left(n\right)\left(n>k\right)$。当 $n=k+1$ 时，易知 $T_k\left(k+1\right)$ 是个完全图，其节点的度均为k， $T_k\left(k+1\right)$ 去掉一个k度点后，变为k个节点的完全图，依旧是k树，命题成立。当 $n>k+1$ 时，设k树 $T_k\left(n\right)=\left(X,E\right)$，由 $T_k\left(n\right)$ 的构造过程标记X为 ${\left\{x_i\right\}}_{i=1}^n$，其中 ${\left\{x_i\right\}}_{i=1}^k$ 是k树的初始团，由构造过程可知 ${\left\{x_i\right\}}_{i=1}^{k+1}$ 也是个团。令 $V_i\left(k+2\le i\le n\right)$ 表示引入 $x_i$ 时，与 $x_i$ 相连接的k团。这里任取 $T_k\left(n\right)$ 中的k度点x，由引理3可知 $D\left(x\right)=\varnothing$， $Adj\left(x\right)$ 是一个k团。令 $G={\left[T_k\left(n\right)\right]}_x$，下面证明图G有以下三个性质：

1) 假设G不连通，则易知G的不连通是由于节点x的删除导致的，所以 $Adj\left(x\right)$ 里至少有两个节点不连通。而 $Adj\left(x\right)$ 是一个k团，里面的节点两两相连，与假设矛盾，所以图G是连通图；

2) 由引理3可知 ${\left\{x_i\right\}}_{i=1}^{k+1}$ 里的k度点不出现在后续连接团里，而 $V_{k+2}\subset {\left\{x_i\right\}}_{i=1}^{k+1}$，所以连接团 $V_{k+2}$ 里没有k度点，即 $x\notin V_{k+2}$，从而G有k大小的团 $V_{k+2}$，图G是k树 $T_k\left(n\right)$ 删除节点x得到的，而 $T_k\left(n\right)$ 作为k树不包含 $k+2$ 大小的团，故G没有 $k+2$ 大小的团；

3) 由割和叶的定义可知，G是相对于割团 $Adj\left(x\right)$ 的叶，由定理4可知G中任意一个极小 $a,b$ 割也是 $T_k\left(n\right)$ 中的极小 $a,b$ 割，而 $T_k\left(n\right)$ 是k树，由定理6可知， $T_k\left(n\right)$ 中的极小 $a,b$ 割均为k团，从而G中的极小 $a,b$ 割也均为k团。

于是，由定理6可知图G是k树。

综上，引理得证。

定理1的证明 任取k树 $T_k\left(n\right)=\left(X,E\right)$。当 $n=k$ 时， $T_k\left(n\right)=T_k\left(k\right)$ 是k个节点的k树，此时 $T_k\left(k\right)$ 是一个完全图，由引理1可知， $T_k\left(k\right)$ 里节点的任意序列都是其完美消除序列，命题成立。

当 $n=k+1$ 时， $T_k\left(n\right)=T_k\left(k+1\right)$ 是 $k+1$ 个节点的k树，由k树的构造过程可知，此时 $T_k\left(k+1\right)$ 的节点集合X是一个 $k+1$ 团，且每个节点的度均为k，任选一个k度点删除，得到一个k团，可以按任意顺序删除这k个节点。这 $k+1$ 个节点的删除顺序就是其完美消除序列，命题成立。

假设 $n=l\left(l\ge k+2\right)$ 时，命题成立。则当 $n=l+1$ 时， $T_k\left(n\right)=T_k\left(l+1\right)$， $\left|X\right|=l+1$，任取 $T_k\left(l+1\right)$ 里的k度点x，由引理3可知 $D\left(x\right)=\varnothing$，由引理4可知 ${\left[T_k\left(l+1\right)\right]}_x$ 是l个节点的k树，于是由假设可知， ${\left[T_k\left(l+1\right)\right]}_x$ 可以通过迭代地删除k度点，直至剩余k个节点，最后按任意顺序删除这k个节点的方式标记 $X-\left\{x\right\}$ 为 ${\left\{y_i\right\}}_{i=1}^l$，且 ${\left\{y_i\right\}}_{i=1}^l$ 对应的序列就是 ${\left[T_k\left(l+1\right)\right]}_x$ 的完美消除序列，满足 $MD\left(y_i\right)=\varnothing$。这里标记 $x=x_1$，标记 $y_i=x_{i+1}\left(1\le i\le l\right)$，则 $X={\left\{x_i\right\}}_{i=1}^{l+1}$，且有1) $MD\left(x_i\right)=MD\left(x\right)=D\left(x\right)=\varnothing \left(i=1\right)$ ；2) $MD\left(x_i\right)=MD\left(y_{i-1}\right)=\varnothing \left(2\le i\le l+1\right)$。由定义2， ${\left\{x_i\right\}}_{i=1}^{l+1}$ 所对应的序列就可以作为 $T_k\left(l+1\right)$ 的完美消除序列。由k度点x选择的任意性和 ${\left\{y_i\right\}}_{i=1}^l$ 序列的构造过程，命题成立。

综上，定理得证。

定理2的证明 首先，设 $x_i$ 满足1) 2)，则按照序列 $\alpha$ 对 $T_k\left(n\right)$ 的节点进行删除时，因为前 $n-k$ 个节点满足 $\left|MAdj\left(x_i\right)\right|=k$，所以每个节点都是作为k度点被删除的，满足定理1中k度点的删除方式，后k个节点的删除也满足定理1中任意顺序的删除方式，于是由定理1可知 $\alpha$ 是 $T_k\left(n\right)$ 的完美消除序列。

反之，设 $\alpha$ 是 $T_k\left(n\right)$ 的完美消除序列，当 $n=k$ 时， $n-k=0$， $T_k\left(n\right)=T_k\left(k\right)$ 是完全图， ${\left\{x_i\right\}}_{i=1}^k$ 是一

个团，对任意 $x_i$ 有 $MAdj\left(x_i\right)={\left\{x_j\right\}}_{j=i+1}^k$，即 $i>0$ 时， $\left|MAdj\left(x_i\right)\right|=k-i$，命题成立。

当 $n=k+1$ 时， $n-k=1$， $T_k\left(n\right)=T_k\left(k+1\right)$，由k树的递归构造可知， $T_k\left(k+1\right)$ 是完全图， ${\left\{x_i\right\}}_{i=1}^{k+1}$ 是

一个团，对任意 $x_i$ 有 $MAdj\left(x_i\right)={\left\{x_j\right\}}_{j=i+1}^{k+1}$，则有：a) $\left|MAdj\left(x_i\right)\right|=k+1-i=k+1-1=k\left(i=1\right)$ ；b) $\left|MAdj\left(x_i\right)\right|=k+1-i\left(i>1\right)$。命题成立。

假设 $n=l\left(l\ge k+2\right)$ 时命题成立。当 $n=l+1$ 时， $n-k=l+1-k$， $T_k\left(n\right)=T_k\left(l+1\right)$， $\alpha$ 标记X为 ${\left\{x_i\right\}}_{i=1}^{l+1}$，则 $D\left(x_1\right)=MD\left(x_1\right)=\varnothing$， $x_1$ 是单纯点，由引理3可知， $x_1$ 是k度点。令 $G={\left[T_k\left(l+1\right)\right]}_{x_1}$，则 $X-\left\{x_1\right\}$ 是图G的节点集合，且由引理4及 $x_1$ 是k度点可知G是k树，令 $y_i=x_{i+1}\left(i=1,2,\cdots ,l\right)$，标记 $X-\left\{x_1\right\}$ 为 ${\left\{y_i\right\}}_{i=1}^l$，则 $MD\left(y_i\right)=MD\left(x_{i+1}\right)=\varnothing$，故 ${\left\{y_i\right\}}_{i=1}^l$ 对应的序列是G的完美消除序列，而G的节点个数为l，则由假设有：(a) $\left|MAdj\left(y_i\right)\right|=k\left(i\le l-k\right)$ ；(b) $\left|MAdj\left(y_i\right)\right|=l-i\left(i>l-k\right)$。对于 ${\left\{x_i\right\}}_{i=1}^{l+1}$ 来讲， $i\le l+1-k$ 时， $i-1\le l-k$，有

$\left|MAdj\left(x_i\right)\right|=\left\{\begin{array}{l}\left|MAdj\left(y_{i-1}\right)\right|=k\left(i\ge 2\right)\\ \left|MAdj\left(x_1\right)\right|=\left|Adj\left(x_1\right)\right|=k\left(i=1\right)\end{array}\right\}=k$.

$i>l+1-k$ 时， $i-1>l-k$，有

$\left|MAdj\left(x_i\right)\right|=\left|MAdj\left(y_{i-1}\right)\right|=l-\left(i-1\right)=l+1-i$.

命题成立。

综上，定理得证。

4. 定理3的证明

一般来说，k树的构造是从k个节点的完全图开始的，本文为了使k树的完美消除序列与构造过程之间的关系有一个更清晰的表达，定义k树的构造从第一个节点开始，下面给出k树构造过程的定义。

定义4对于k树 $T_k\left(n\right)=\left(X,E\right)$，取 $\beta :\left\{1,2,\cdots ,n\right\}\leftrightarrow X$ 是一个双射，且根据 $\beta$ 标记X为 ${\left\{x_i\right\}}_{i=1}^n$，通过以下递归步骤：

1) $i\le k$ 时，分别连接 $x_i$ 与 $x_j\left(j<i\right)$，使 ${\left\{x_j\right\}}_{j=1}^i$ 成为一个团；

2) $i>k$ 时，找 ${\left\{x_j\right\}}_{j=1}^{i-1}$ 中的一个k团 $V_i$，使 $x_i$ 与 $V_i$ 中的每一个节点连接。

得到图G，若 $G=T_k\left(n\right)$，则称 $\beta$ 是 $T_k\left(n\right)$ 的一个构造过程。

(注意，这里的递归步骤也可以看作是 $T_k\left(n\right)$ 边集的一个表达)

定理3的证明令A是 $T_k\left(n\right)$ 的所有完美消除序列的集合， $\forall \alpha \in A$ 是 $T_k\left(n\right)$ 的一个完美消除序列( $\alpha :\left\{1,2,\cdots ,n\right\}\leftrightarrow X$ 是一个双射)。令B是 $T_k\left(n\right)$ 的所有构造过程的集合， $\forall \beta \in B$ 是 $T_k\left(n\right)$ 的一个构造过程。令 $\psi$ 是A到B的一个映射，满足对 $\forall i\in \left\{1,2,\cdots ,n\right\}$， $\forall \alpha \in A$，有 $\psi \left(\alpha \right)\left(i\right)=\alpha \left(n+1-i\right)$，即如果将 $\alpha$ 看作对X的排序，则 $\psi \left(\alpha \right)$ 是相对于 $\alpha$ 的对X的一个逆排序。下面证明 $\psi$ 是一个双射。

$\forall \alpha \in A$， $\alpha$ 标记X为 ${\left\{x_i\right\}}_{i=1}^n$，令 $\beta =\psi \left(\alpha \right)$， $\beta$ 标记X为 ${\left\{y_i\right\}}_{i=1}^n$，由 $\psi$ 的定义可知 $y_i=x_{n+1-i}\left(i=1,2,\cdots ,n\right)$，由 $\alpha$ 是 $T_k\left(n\right)$ 的完美消除序列可知：(1) $i\le n-k$ 时， $x_i$ 与 ${\left\{x_j\right\}}_{j=i+1}^n$ 中的一个k团的每一个节点均连接；(2) $i>n-k$ 时， ${\left\{x_j\right\}}_{j=i}^n$ 是团。相应地， $\beta$ 作为 $\alpha$ 的逆序序列，满足：1) $n+1-i\ge k+1$ 时， $y_{n+1-i}$ 与 ${\left\{y_j\right\}}_{j=1}^{n-i}$ 中的一个k团的每一个节点均连接(即 $p\ge k+1\left(p>k\right)$ 时， $y_p$ 与 ${\left\{y_j\right\}}_{j=1}^{p-1}$ 中的一个k团的每一个节点均连接)；2) $n+1-i<k+1$ 时， ${\left\{y_j\right\}}_{j=1}^{n+1-i}$ 是团(即 $p<k+1\left(p\le k\right)$ 时， ${\left\{y_j\right\}}_{j=1}^p$ 是团)。由定义4可知 $\beta$ 是 $T_k\left(n\right)$ 的一个构造过程，从而有 $\beta =\psi \left(\alpha \right)\in B$。

$\forall \beta \in B$， $\beta$ 标记X为 ${\left\{y_i\right\}}_{i=1}^n$，令 $\alpha :\left\{1,2,\cdots ,n\right\}\leftrightarrow X$ 标记X为 ${\left\{x_i\right\}}_{i=1}^n$，使得X满足 $x_i=y_{n+1-i}\left(i=1,2,\cdots ,n\right)$，由 $\alpha$ 的定义可知 $\alpha$ 与 $\beta$ 互为逆序序列。由 $\beta$ 是 $T_k\left(n\right)$ 的构造过程可知：1) $i\le k$ 时， $y_i$ 与 $y_j\left(j<i\right)$ 相连接， ${\left\{y_j\right\}}_{j=1}^i$ 是团；2) $i>k$ 时， $y_i$ 与 ${\left\{y_j\right\}}_{j=1}^{i-1}$ 中的一个k团的每一个节点均连接。相应地， $\alpha$ 作为 $\beta$ 的逆序序列满足：1) $n+1-i\ge n+1-k$ 时， $x_{n+1-i}$ 与 $x_j\left(j>n+1-i\right)$ 相连接， ${\left\{x_j\right\}}_{j=n+1-i}^n$ 是团(即 $p\ge n+1-k\left(p>n-k\right)$ 时， $x_p$ 与 $x_j\left(j>p\right)$ 相连接， ${\left\{x_j\right\}}_{j=p}^n$ 是团)；2) $n+1-i<n+1-k$ 时， $x_{n+1-i}$ 与 ${\left\{x_j\right\}}_{j=n+1-i+1}^n$ 中的一个k团的每一个节点均连接(即 $p<n+1-k$ $\left(p\le n-k\right)$ 时， $x_p$ 与 ${\left\{x_j\right\}}_{j=p+1}^n$ 中的一个k团的每一个节点均连接)。由定理2可知， $\alpha$ 是 $T_k\left(n\right)$ 的一个完美消除序列，从而， $\forall \beta \in B$， $\exists \alpha \in A$ 使得 $\psi \left(\alpha \right)=\beta$。

由 $\psi$ 的定义， $\psi$ 将一个序列映射为它的逆序序列，所以对 $\forall {\alpha }_1\ne {\alpha }_2$，有 $\psi \left({\alpha }_1\right)\ne \psi \left({\alpha }_2\right)$。

综上，定理得证。

5. k树识别算法

k树识别算法是在弦图识别算法的基础上实现的，先介绍一个弦图识别的算法——MCS (max cardinality search，最大基数搜索)算法 [11]。该算法是弦图识别常用的算法之一(通过最大基数搜索的方式构造序列，并检查该序列是否为一个完美消除序列来判断输入图是否为弦图)。算法如下(算法1)所示：

Algorithm 1. Max-cardinality-search algorithm

算法1. MCS算法

根据k树完美消除序列和构造过程之间一一对应的关系，并且结合k树完美消除序列有关k度点的独特性，给出一个k树的识别算法——先将输入图识别为弦图后，根据其完美消除序列标记其点集，检查是否满足定理2中的结果来确认输入图是否为k树(算法2)。

Algorithm 2. k-trees’ recognition algorithm

算法2. k树的识别算法

6. 结语

本文从k树的递归构造方式入手，证明了作为弦图子类的k树，其完美消除序列具有独特性，可以通过k度点的迭代删除来刻画，k度点的识别相对于单纯点的识别也更加便利。同时，在k树完美消除序列的研究过程中，进一步发现其与k树构造过程之间的关系，k树的每一个完美消除序列都与它的一个构造过程以互为逆序序列的方式一一对应。最后，本文也将k树完美消除序列的独特性应用于k树的识别中，给出了一个k树的识别算法。此外，k树作为有特殊结构的弦图子类，在以弦图为模型的各类问题上会展现更好的性能，后续可以进一步研究。

NOTES

^*通讯作者。

¹“弦化”表示一个无向图通过加边的方式变为弦图的过程。